プログラミングの理論 迷路を解け

質問

迷路の解き方にはどのようなものがあるか？

2つのアイデアがありますが、あまりエレガントではないと思います。

基本的な状況です。 我々は行列を持っており、この行列の要素は、それが迷路を表すように順序付けされており、1つの方法と1つの出口があります。

私の最初のアイデアは、迷路の中にロボットを送り込み、一辺をたどりながら、迷路の外に出るまで行かせることでした。これは非常に時間のかかるソリューションだと思います。

2つ目は、1がついたアイテムを次々と通過し、行ける場所（上、右、下、左）をチェックし、1つの道を選び、そこで道を進みます。これは1つ目よりもさらに遅いです。

もちろん、2 つのボットをすべての交差点でマルチスレッドにすれば少し速くなりますが、これも最善の方法とは言えません。

ボットを迷路に送り込むためのより良いソリューションが必要です。

EDIT

はじめに 素敵な回答ありがとうございました

質問の2つ目です。 多次元グラフがある場合、どうすればいいのでしょうか？それともJustin L.の回答が使えるのでしょうか？

このケースには最適な方法ではないと思います。

3つ目の質問です。

これらの迷路ソルバーアルゴリズムのうち、どれが最も速いか/速いか？ (純粋に仮説です)

どのように解くのですか？

迷路は木だと思えばいいのです。

     A
    / \
   / \
  B C
 / \ / \
D E F G
   / \ \
  H I J
 / \
L M
   
  ** O

(を表す可能性があります。）

        START
        + +---+---+
        | A C G
    +---+ + + +
    | D B F J
+---+---+ +---+---+
| L H E I
+---+ +---+---+
    | M O
    + +---+
    仕上げ

(ツリー上の左右の順序を無視する)

ここで、各ノードはパスの分岐点である。 D, I, J, L, O は行き止まりで、**がゴールです。 もちろん、実際のツリーでは、各ノードはいくつもの 3 の子を持つ可能性があります。

あなたの目標は今、ゴールを見つけるためにどのノードを横断するかを見つけるだけです。 どんな古い木探索アルゴリズムでもかまいません。

木を見てみると、木の一番深いところにある ** から上に向かってたどるだけで、正しい解答が簡単に見つかります。

A B E H M **

この方法は、次のようになることに注意してください。 わずかながら ループがある場合 (つまり、バックトラックなしで、すでに通過した通路に再び入ることが可能な場合)、このアプローチはより複雑になることに注意してください。 1つの素晴らしい解決策をコメントでチェックしてください。

では、この木に適用される、あなたが言及した最初の解決策を見てみましょう。

あなたの最初の解決策は、基本的に 深さ優先の検索 というのがありますが、これはそんなに悪いものではありません。 これは実はかなり優れた再帰的検索なんです。 基本的には、「常に最初に一番右のアプローチを取る。 もし何もなければ、まっすぐか左に行ける最初の場所まで後退し、それを繰り返すのです。

深さ優先探索は、上記の木をこの順序で探索します。

A B D (backtrack) E H L (backtrack) M ** (backtrack) O (backtrack thrice) I
(backtrack thrice) C F (backtrack) G J

なお、**が見つかればすぐにやめることができます。

しかし、実際に深さ優先探索をコード化する際には 再帰的プログラミング を使うと、すべてがずっと簡単になります。 反復法も使えますし、バックトラックの方法を明示的にプログラムする必要もありません。 リンク先の記事で実装を確認してください。

木を検索するもう一つの方法は ブレッドファースト（Breadth-First というソリューションがありますが、これは深さによってツリーを検索します。 これは上記の木をこの順番で検索します。

A (next level) B C (next level) D E F G (next level)
H I J (next level) L M (next level) ** O

迷路の性質上、幅優先はチェックするノードの平均量がずっと多いことに注意してください。 探索するパスの待ち行列を持ち、各反復で待ち行列からパスを取り出し、1ステップ後に変身できるすべてのパスを取得してそれを爆発させ、それらの新しいパスを待ち行列の最後に置くことによって、幅優先は簡単に実装されます。 コード化するための明示的なコマンドはなく、理解を助けるために存在するだけです。

実際には、全体の ツリーを検索する方法の拡張リストがあります。 . ここでは、最も単純で簡単な方法を2つ紹介しました。

もしあなたの迷路がとてもとても長くて深くて、ループやクレイジーなものがあって、複雑なものであるなら、私は A* アルゴリズムは、業界標準の経路探索アルゴリズムであり、発見的手法による幅優先探索を組み合わせたものです...いわば「インテリジェント幅優先探索」のようなものです。

基本的にはこのように動作します。

1. 1 つのパスをキューに入れます (迷路の中を 1 歩だけまっすぐ歩くパス)。 パスには、現在の長さ + 端からの直線距離 (これは数学的に計算できます) で与えられる "weight" があります。
2. キューから最も低い重みを持つパスをポップします。
3. パスを、1 ステップ後になりうるすべてのパスに爆発させます。(たとえば、パスが Right Left Left Right である場合、壁を通過する不正なものを含めずに、分解されたパスは R L L R R と R L L R L になります)。
4. これらのパスのいずれかにゴールがあれば、Victory! それ以外の場合は
5. 分解されたパスの重みを計算し、それらすべてをキューに戻す（元のパスは含めない）。
6. キューを重みでソートし、最も低いものから順に並べます。 その後、ステップ 2 から繰り返す

そして、それは A* のための業界標準の経路探索アルゴリズムであるため、特別に強調して紹介します。 すべて 経路探索のアプリケーション (マップの端から端への移動、オフロードの道や山を避けての移動など) では、ほぼ業界標準の経路探索アルゴリズムであるためです。 このアルゴリズムが非常にうまく機能するのは 最短距離ヒューリスティック を使用しているためです。 A* が万能なのは、どんな問題でも、利用可能な最短距離ヒューリスティックがあれば（私たちの場合は直線）、それを適用できるからです。

しかし がA*であることに注目することは、大きな価値があります。 ではない が唯一の選択肢であることに留意することは大きな価値があります。

実は、この wikipedia の木構造探索アルゴリズムのカテゴリ には 97 個ものアルゴリズムが掲載されています。(最も優れているのは、やはり このページ にあります)

長くてすみません =P (だらだらと書いてしまいがちなので)