バックトラッキング法を使って迷路問題を解くPHPの詳細解説

この記事では、バックトラッキング手法に基づいて迷路問題を解決するための PHP 手法を主に紹介し、バックトラッキング手法の原理、実装手順、および迷路問題を解決するための関連操作スキルを例の形で詳細に分析します。必要な場合は、この記事の例を参照してください

バックトラック法に基づいて迷路の問題を解決する方法を PHP がどのように実装するかを説明します。詳細は次のとおりです:

はじめに

最近、leetcode でいくつかのアルゴリズムの質問を読みましたが、その中には非常に単純で一般的に使用されているように見えましたが、理解できませんでした。それらを一度に解決する方法、たとえば次のようにします。 sqrt 関数を実装して、配列の配置を見つけます。もちろん、高度な数学が苦手な方にとっては、一見簡単な問題を初めて解くのは難しいでしょう。今日お話しするのは、この問題をすべて解く方法です。この問題を解決する方法 バックトラックの考え方に関しては、この考え方を理解していないと、少し複雑な問題の多くは解決することが困難になります。

問題の説明

この問題は、実際に歩き回っていたときに発生しました。場所を正確に思い出せません。

1 1 1 1
0 1 0 1
0 1 0 1
0 1 1 1

上は迷路、左上隅が入口、右下隅が出口、シャオメン（はい、あなたです）正しく読んでください、長いです（気を失ったシャオミン）入り口から入って出口から逃げます（1時間逃げられないと、に食べられます、シャオメンの可能なすべての逃げ道を見つけてください。）

この質問は非常に単純で、答えはすぐにわかりますが、考えをコードに変換するときにどこから始めればよいかわかりません。

解決方法

この問題に対する 1 つの解決策はバックトラッキング手法です。まずバックトラッキング手法の定義を見てみましょう (Baidu Encyclopedia):

バックトラッキング手法 (探索およびバックトラッキング手法) は一種です。最適探索手法は、ヒューリスティック手法とも呼ばれ、目標を達成するために最適な条件に従って前方探索を行います。しかし、探究が一定の段階に達し、最初の選択が最適ではない、または目標を達成できないことがわかった場合、一歩下がって別の選択をします。うまくいかなかった場合は、戻って再試行するというテクニックです。バックトラック方法と、バックトラック条件を満たす特定の状態にある点を「バックトラックポイント」と呼びます。

私のアイデア:

1. 上の迷路を座標系で左上隅が (0,0)、右下隅が (3,3) で、その他の点が座標系に点在します。 From ( 0,0)
3. 指定された座標点から開始して、1 の場合は右方向に検索し、0 の場合は下方向に検索します。検索する前に、検索した座標を記録します。座標が (3 ,3) に等しい場合は後戻り点であり、境界を越えない限り、この時点で 3 番目のステップを繰り返します

私の PHP 実装を見てください:

<?php
$nums = [
  [1,1,1,1,1,1],
  [0,1,0,1,0,1],
  [0,1,0,1,0,1],
  [0,1,1,1,1,1]
];
function getRet($data, $x, $y, &$result=[], $record)
{
  $snapshort = [];
  $xL = count($data) - 1;
  $yL = count($data[0]) - 1;
  if($x > $xL || $y > $yL) {
    //跑到迷宫不存在的空间了，这种事情绝对不能发生
    return;
  }
  if($data[$x][$y] == "0") {
    //是0的话停止继续前进，退回上一状态
    return;
  } elseif($data[$x][$y] == "1") {
    //是1的话，记录最新的坐标到当前已找到的路径中，继续向前搜索
    //如果到达出口，记录答案并回溯
    $snapshort = array_merge($record, [[$x, $y]]);
    if($x == $xL && $y == $yL) {
      $result[] = array_merge($record, [[$x, $y]]);
      return;
    }
  } else {
    return;
  }
  //向有搜索
  //这里的$snapshort保存当前搜索位置的状态，等到下次回溯到这里的时候会用到
  getRet($data, $x, ++$y, $result, $snapshort);
  //向下搜索
  getRet($data, ++$x, --$y, $result, $snapshort);
}
//看个例子
$result = [];
getRet($nums, 0, 0, $result, []);
foreach ($result as $pos) {
  foreach ($pos as $xy) {
    echo "({$xy[0]},{$xy[1]}) => ";
  }
  echo "end\n";
}

出力結果

(0,0)=>(0,1)=>(0,2)=>(0,3)=>(0,4)=>(0,5)=>(1,5)=>(2,5)=>(3,5)=>end
(0,0)=>(0,1)=>(0,2)=>(0,3)=>(1,3)=>(2,3)=>(3,3)=>(3,4)=>(3,5)=>end
(0,0)=>(0,1)=>(1,1)=>(2,1)=>(3,1)=>(3,2)=>(3,3)=>(3,4)=>(3,5)=>end

以上がバックトラッキング法を使って迷路問題を解くPHPの詳細解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。