algorithm - 迷路問題と再帰的バックトラッカー アルゴリズム

Question

再帰的バックトラッカー アルゴリズムを実装して迷路の問題を解決したいのですが、2.3 コマンド (「現在のセルと選択したセルの間の壁を取り除く」) が理解できません。

1. 現在のセルを「訪問済み」としてマーク
2. 現在のセルに訪問されていない隣接セルがある場合
   1. 未訪問の近隣の 1 つをランダムに選択する
   2. 現在のセルをスタックに追加する
   3. 現在のセルと選択したセルの間の壁を取り除く
   4. 選択したセルを現在のセルにする
   5. この関数を再帰的に呼び出す
3. そうしないと
   1. スタックから最後の現在のセルを削除します
   2. この関数の前の実行に戻る

編集 実際、スタックを使用して迷路の問題を解決するアルゴリズムが必要です。

Answer 1

そのアルゴリズムは、迷路ソルバーではなく、迷路ジェネレーターです。アイデアは、ランダムな迷路を作成することです。また、迷路内のすべてのポイントが他のすべてのポイントから到達できるようにします。

ランダムに壁を削除すると、迷路が接続されない可能性があります。再帰的バックトラッキング アルゴリズムは、ランダム ウォークを作成し、そのランダム ウォークに沿って壁を取り除くことでこれを処理します。再帰的なバックトラック部分により、行き止まりに達した場合でも、迷路内のすべてのセルに移動できます。

Answer 2

あなたのアルゴリズムはgodモード用です。普通にやるべき

1. 現在のセルが出口の場合、終了
2. 現在のセルに、まだ訪問されていない、壁ではない隣接セルがある場合
   
   1. 未訪問の非壁隣接 の 1 つをランダムに選択します
   2. 現在のセルをスタックに追加する
   3. なし
   4. 選択したセルを現在のセルにする
   5. この関数を再帰的に呼び出す
3. そうしないと
   
   1. スタックから最後の現在のセルを削除します
   2. この関数の前の実行に戻る

Answer 3

壁を取り除くことは、単に壁を取り除くことを意味します。セルのグリッドから始めます。各セルは 4 つの壁で完全に囲まれています。(2.1) の周りをランダムに移動すると、セルを結合している壁が削除されます。