Loading article…
迷路解決アルゴリズムとは、迷路を解くための自動化された方法である。ランダムマウス、壁追従、プレッジ、タリー、トレモーのアルゴリズムは、迷路に関する事前知識を持たない旅行者が迷路内で使用することを想定して設計されている一方、行き止まり埋めアルゴリズムと最短経路アルゴリズムは、迷路全体を一度に見ることができる人またはコンピュータプログラムが使用することを想定して設計されている。
ループを含まない迷路は「単連結」または「完全」迷路として知られており、グラフ理論では木に相当します。迷路解決アルゴリズムはグラフ理論と密接に関連しています。直感的に、迷路内の経路を適切な方法で引っ張ったり伸ばしたりすると、結果として木に似たものを作ることができます。[ 1 ]
この単純な方法は、メモリを必要としないため、知能の低いロボットやマウスでも実行できます。ロボットは分岐点に到達するまで現在の経路を進み、次に進む方向をランダムに決定します。このような方法は最終的には必ず正しい解を見つけますが、アルゴリズムは非常に遅くなる可能性があります。[ 2 ]
迷路を攻略する効果的なルールの1つに、壁に手を触れるルール（左手ルールまたは右手ルールとも呼ばれる）があります。迷路が単純連結、つまりすべての壁が互いに、または迷路の外側の境界に接続されている場合、片方の手を迷路の壁に接触させておくことで、解く人は迷子になることが保証され、別の出口があればそこに到達できます。そうでない場合、アルゴリズムは、その連結された壁のセクションに隣接するすべての通路を少なくとも1回通過した後、入口に戻ります。このアルゴリズムは、深さ優先の順序付き木構造の走査です。
壁に沿って進むことが機能する理由についてのもう1つの視点は、位相幾何学的なものです。壁がつながっている場合、ループまたは円に変形することができます。[ 3 ]すると、壁に沿って進むことは、開始から終了まで円を一周することに帰着します。この考えをさらに深めるために、迷路の壁の連結したコンポーネントをグループ化すると、それらの間の境界が、解が複数ある場合でも、正確に解になることに注目してください。
迷路が単連結でない場合（つまり、始点または終点が通路ループに囲まれた構造の中心にある場合、あるいは経路が互いに交差し、解の経路のそのような部分が通路ループに囲まれている場合）、この方法は必ずしも目標に到達できるとは限りません。
もう一つ注意すべき点は、迷路の入り口から壁沿いの探索を始めるように注意する必要があるということです。迷路が単連結でない場合、迷路内の任意の地点から壁沿いの探索を始めると、入口も出口もない、ループ状にぐるりと回った別の壁に沿って閉じ込められてしまう可能性があります。壁沿いの探索が遅れて始まった場合は、探索を開始した位置をマークするようにしてください。壁沿いの探索は必ず開始地点に戻るため、開始地点に二度遭遇した場合は、迷路が単連結ではないと判断し、まだ探索していない別の壁に切り替えるべきです。別の方法論については、下記の「誓約アルゴリズム」を参照してください。
壁沿い探索は、3D迷路やそれ以上の次元の迷路でも、その高次元通路を2D平面に決定論的に投影できる場合に実行可能です。例えば、3D迷路において「上」の通路が北西方向、「下」の通路が南東方向につながると仮定できる場合、標準的な壁沿い探索ルールを適用できます。ただし、2D迷路とは異なり、どちらの方向が最初に左または右に進むかを判断するために、現在の向きが既知である必要があります。
このアルゴリズムの動作シミュレーションは、こちらでご覧いただけます。
壁が外側の境界に接続されていない（境界が閉じていない）分離迷路は、迷路の入口と出口が迷路の外壁にある限り、壁追従法で解くことができます。しかし、ソルバーが迷路の内部から開始する場合、出口から分離したセクションにいる可能性があり、壁追従者はリングをぐるぐる回り続けます。Pledge アルゴリズム（エクセターの Jon Pledge にちなんで名付けられました）はこの問題を解決できます。[ 4 ] [ 5 ]
障害物を回避するために設計されたプレッジアルゴリズムでは、優先方向として任意に選択された方向に向かって進む必要があります。障害物に遭遇すると、片方の手（例えば右手）を障害物に沿って動かし、回転角度を計測します（時計回りの回転は正、反時計回りの回転は負）。ソルバーが元の優先方向を再び向き、回転角度の合計が0になった時点で、ソルバーは障害物から離れ、元の方向に移動を続けます。
手は、「回転の合計」と「現在の進行方向」の両方がゼロになったときにのみ壁から離れます。これにより、アルゴリズムは大文字の「G」のような形をしたトラップを回避できます。アルゴリズムが最初の壁で左に曲がると仮定すると、壁によって完全に360度回転します。「現在の進行方向」のみを追跡するアルゴリズムは、右下隅の壁から左に進み、左側の湾曲した部分に再びぶつかるため、無限ループに陥ります。Pledgeアルゴリズムは、その時点で「回転の合計」がゼロではないため（360度は0度ではないことに注意）、右端の壁から離れません。壁に沿って一周し、最終的に文字の形のすぐ下の外側で左に進みながら壁から離れます。
このアルゴリズムを使えば、コンパスを持った人が、解く人の初期位置に関係なく、任意の有限二次元迷路の内部の任意の地点から外部の出口までたどり着くことができます。ただし、このアルゴリズムは逆方向、つまり迷路の外部の入口から内部の最終目標地点までたどり着くことには使えません。
シャルル・ピエール・トレモーによって考案されたトレモーのアルゴリズム[ 6 ]は、床に線を引いて経路を示す必要がある迷路からの脱出方法を見つける効率的な方法であり、明確に定義された通路を持つすべての迷路で機能することが保証されています[ 7 ]が、最短経路を見つけることは保証されていません。
通路の入口は、未踏、1回マーク、または2回マークされている。入口をマークすることと、交差点や通路をマークすることは同じではない。なぜなら、交差点には複数の入口があり、通路には両端に入口があるからである。行き止まりは、入口が1つしかない交差点と考えることができる。
このアルゴリズムは以下のルールに従って動作します。
「引き返して戻る」ルールは、ループのある迷路を実質的に単連結迷路に変えます。ループを閉じる経路が見つかった場合、それは行き止まりとみなされ、引き返さなければなりません。このルールがない場合、引き返す代わりに別の任意の入口を選んだ場合、まだ探索していない迷路の部分へのアクセスを遮断してしまう可能性があります。
出口に到達したら、正確に1回だけマークされた入口がスタート地点への戻り道を示します。出口がない場合、この方法ではすべての入口が2回マークされたスタート地点に戻ります。この場合、各通路は正確に2回、つまり各方向に1回ずつ歩かれます。結果として得られる歩行は双方向二重トレースと呼ばれます。[ 8 ]
基本的に、19世紀に発見されたこのアルゴリズムは、約100年後に深さ優先探索として使用されるようになった。[ 9 ] [ 10 ]
1895年にガストン・タリーが『迷路の問題』で発表したタリーのアルゴリズムは、迷路のレイアウトに関する事前知識なしに迷路または連結無向グラフを探索する方法です。探索の進行状況を記録するために迷路のマーキングを使用する点で、トレモーのアルゴリズムと似ています。このアルゴリズムは完全な探索と終了を保証し、各エッジは最大で2回、各方向に1回ずつ探索されます。これは、 MacTutorが「コンピュータ実装に特に適している」と説明した単一のルールとして表現できます。他のすべての出口が探索されるまで、交差点から来た方向と同じ方向に出てはいけません。これは現在、初期の深さ優先探索に似た手順と考えられています。[ 11 ] [ 9 ] [ 12 ]
行き止まり埋めは、迷路を解くためのアルゴリズムで、すべての行き止まりを埋め、正しい経路だけを未埋めのままにします。紙の迷路やコンピュータプログラムで迷路を解くのに使用できますが、この方法は迷路全体を一度に調べるため、未知の迷路の中にいる人には役立ちません。この方法は、
一部の通路は、他の行き止まり通路が先に削除されるまで、行き止まり通路の一部にはならないことに注意してください。行き止まり通路の埋め合わせの動作を示すビデオは右側にあります。
行き止まりの埋め合わせでは、処理の各段階で迷路のトポロジーが維持されるため、開始点と終了点が誤って「切り離される」ことはありません。さらに、結果に行き止まりが含まれることはないため、処理が「早すぎる」停止もありません。したがって、完全な迷路（ループのない迷路）に対して行き止まりの埋め合わせを行った場合、解のみが残ります。部分的に編み込まれた迷路（ループのある迷路）に対して行った場合は、考えられるすべての解が残りますが、それ以上のものは残りません。
迷路全体を俯瞰できる場合、単純な再帰アルゴリズムで終点への到達方法を特定できます。アルゴリズムには開始時のX座標とY座標が与えられます。X座標とY座標が壁面上にない場合、メソッドは隣接するすべてのX座標とY座標を指定して自身を呼び出し、既にそれらの座標を使用していないことを確認します。X座標とY座標が終点の位置にある場合、メソッドの過去の実行結果をすべて正しい経路として保存します。
これは実質的に、グリッドポイントで表現された深さ優先探索です。全知ビューは、記憶によってループに入ることを防ぎます。以下にJavaのサンプルコードを示します。
boolean [][] maze = new boolean [ width ][ height ] ; // 迷路boolean [][] wasHere = new boolean [ width ][ height ] ; boolean [][] correctPath = new boolean [ width ][ height ] ; // 迷路の解int startX , startY ; // 迷路の開始時の X 座標と Y 座標int endX , endY ; // 迷路の終了時の X 座標と Y 座標public void solveMaze () { maze = generateMaze (); // 迷路を作成 (false = パス、true = 壁)// 以下の false への代入は、Java ではデフォルトで配列要素に false を代入するため冗長ですが、他の言語では同じように動作しない可能性があるため含めています。for ( int row = 0 ; row < maze . length ; row ++ ) // ブール配列をデフォルト値に設定しますfor ( int col = 0 ; col < maze [ row ] . length ; col ++ ){ wasHere [ row ] [ col ] = false ; correctPath [ row ] [ col ] = false ; } boolean b = recursiveSolve ( startX , startY ); // パスが true 値で示されるブール配列 (correctPath) が残ります。// b が false の場合、迷路の解はありません} public boolean recursiveSolve ( int x , int y ) { if ( x == endX && y == endY ) return true ; // 終点に到達した場合if ( maze [ x ][ y ] || wasHere [ x ][ y ] ) return false ; // 壁の上にいるか、既にここにいた場合wasHere [ x ][ y ] = true ; if ( x != 0 ) // 左端にいないかチェックif ( recursiveSolve ( x - 1 , y )) { // 左にメソッド 1 を呼び出すcorrectPath [ x ][ y ] = true ; // そのパスの値を true に設定する。return true ; } if ( x != width -1 ) // 右端にないかどうかをチェックif ( recursiveSolve ( x + 1 , y )) { // 右方向にメソッドを1回呼び出すcorrectPath [ x ][ y ] = true ; return true ; } if ( y != 0 ) // 上端にないかどうかをチェックif ( recursiveSolve ( x , y - 1 )) { // 上にメソッドを1回呼び出すcorrectPath [ x ][ y ] = true ; return true ; } if ( y != height - 1 ) // 下端にないかどうかをチェックif ( recursiveSolve ( x , y + 1 )) { // 下にメソッドを1回呼び出すcorrectPath [ x ][ y ] = true ; return true ; } return false ; }迷路ルーティングアルゴリズム[ 13 ]は、迷路内の任意の2地点間の経路を見つけるための低オーバーヘッドな手法です。このアルゴリズムは当初、チップマルチプロセッサ（CMP）の領域向けに提案されましたが、あらゆるグリッドベースの迷路で動作することが保証されています。このアルゴリズムは、グリッド（迷路）内の2地点間の経路を見つけるだけでなく、始点と終点の間に経路がない場合も検出できます。また、このアルゴリズムは、迷路のサイズに関係なく、固定メモリ複雑度で迷路に関する事前知識を持たない内部の旅行者が使用することを想定しており、経路の探索と到達不能な場所の検出には合計4つの変数が必要です。ただし、このアルゴリズムは最短経路を見つけるものではありません。
迷路ルーティングアルゴリズムは、マンハッタン距離（MD）の概念を用い、ある場所から隣接する4つの場所へ移動する際にMDがちょうど1ずつ増減するというグリッドの特性を利用しています。以下は、到達不可能な場所を検出する機能を持たない擬似コードです。
Point src , dst ; // 始点と終点の座標// cur は現在位置の座標も示しますint MD_best = MD ( src , dst ); // dst に最も近い MD を格納します// 生産的なパスとは、dst への MD を小さくするパスですwhile ( cur != dst ) { if (生産的なパスが存在する場合) {生産的なパスを選択します; } else { MD_best = MD ( cur , dst ); curとdstの間に線があると想像します;線の左側/右側の最初のパスを選択します; //左右の選択は、次の手のルールに影響しますwhile ( MD ( cur , dst ) != MD_best ||生産的なパスが存在しない場合) {右手/左手のルールに従います; // 線の選択された側とは反対の方向} }
迷路に複数の解がある場合、解く人はスタートからゴールまでの最短経路を見つけたいと思うかもしれません。最短経路を見つけるためのアルゴリズムはいくつかあり、そのほとんどはグラフ理論に基づいています。そのようなアルゴリズムの1つは幅優先探索を実装することで最短経路を見つけますが、もう1つのA*アルゴリズムはヒューリスティックな手法を使用します。幅優先探索アルゴリズムは、キューを使用して、スタートからゴールに到達するまで距離の昇順でセルを訪問します。訪問された各セルは、スタートからの距離、またはスタートに近い隣接セルがキューに追加された原因を記録しておく必要があります。ゴールの位置が見つかったら、セルの経路を逆方向にたどってスタートに戻ると、それが最短経路になります。最も単純な形式の幅優先探索には、重み付きグラフで最短経路を見つけるなど、制限があります。
集団探索とは、同じ速度で移動する複数の移動エージェントによる未知の環境の探索を指します。このモデルは、特にツリーの場合における迷路解決の並列化可能性を研究するために導入されました[ 14 ]。この研究は、エージェント間の通信モデルに依存します。集中型通信モデルでは、エージェントは常に互いに通信できます。分散型通信モデルでは、エージェントは迷路の壁を読み書きすることによってのみ通信できます。ノードと深さ、 とロボットにおいて、現在の最良のアルゴリズムは集中型通信モデルでは、分散通信モデルにおいて。[ 14 ]
