バックトラッキング法を使用した迷路の解決に関する問題

迷路の問題を解くためのバックトラック

はじめに

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

問題の説明

ただ歩き回っていたときにこの問題に遭遇しました。場所を正確に思い出せません。

<code>1   1   1   10   1   0   10   1   0   10   1   1   1</code>

上部は迷路になっており、左上隅が入口で、右下隅が出口です。入口と出口からの脱出（1時間以内に逃げられないとXモンスターに食べられます）。1は通行可能、0は通行不能を意味します。右と右の2方向のみに進むことができます。かわいい子たちの逃げ道をすべて見つけてください。

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

解決方法

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

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

私のアイデア:

• 上の迷路を左上隅が (0,0)、右下隅が (3,3) などと調整します。座標系に点在する
  
• (0,0) から開始
  
• 指定された座標点から開始し、最初に右方向に検索し、1 の場合は続行します下方向に探索する場合は、探索前に探索した座標を記録します。
  
• 座標が(3,3)に等しい場合、このとき、
  境界線を越えない限り、3 番目のステップを繰り返します
• 私の PHP 実装を見てください:

<code><?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</code>

2 階

クレイジー

sqrt 関数の実装はニュートン反復法です

1F

crazyacking

C での sqrt 関数の実装はニュートン反復法です

Re:

ランニングマン

@crazyacking、夜更かし~~