algorithm - 迷路を解くアルゴリズム。複雑な迷路

Question

迷路を解くアルゴリズムをいくつか見つけました。十分に単純なものは、出口が外側の境界にある場合にのみ適しています (ウォールフォロワー、誓約...)。

境界の形状がランダムで、ゾーンのコストが等しくなく、出口が迷路のどこかにある場合の、より洗練されたアルゴリズムはありますか? （ところで、すべての要素は二次です）

更新: また、迷路がどのように見えるかアプリオリにはわからず、特定の領域しか見ることができません。

Answer 1

紙に見られるような「通常の」2次元迷路を意味する場合は、画像分析を使用してそれらを解決できます。ただし、何らかの形で（2D / 3D）迷路自体に位置していて、抜け道を見つける必要がある場合は、おそらくいくつかの機械学習手法を展開する必要があります。これは、迷路が正確にどのように見えるかわからない場合、つまり、その一部のみを「見る」場合に機能します。

更新：最短経路ファインダーアルゴリズムファミリーとは別に、迷路の中で人間が使用できるように設計された、いわゆるトレモーのアルゴリズムにも関係することができます。これは単純な再帰的バックトラッカーに似ており、すべての迷路の解決策を見つけます。

説明：

通路を歩きながら、後ろに線を引いて道を示します。行き止まりになったら、向きを変えて、来た道に戻ります。今まで訪れたことのないジャンクションに出会ったら、ランダムに新しいパッセージを選んでください。新しい通路を歩​​いていて、以前に訪れたジャンクションに遭遇した場合は、行き止まりのように扱い、元の場所に戻って、円を描いたり、通路を逃したりしないようにします。以前に訪れた（つまり、一度マークされた）通路を歩いていて、ジャンクションに遭遇した場合は、新しい通路がある場合はそれを取り、そうでない場合は「古い」通路を取ります。すべてのパッセージは、空（まだ訪問されていない場合）、1回マーク、または2回マーク（バックトラックを余儀なくされた場合）のいずれかになります。解決策に到達すると、1回だけマークされたパスは、最初に戻る直接の方法を示します。

Answer 2

最短経路アルゴリズムは、出口がどこにあるかに関係なく、出口までの最短経路を見つけます。

コストが等しい場合 - BFSで十分です - それ以外の場合は、最短経路を見つけるためにダイクストラのアルゴリズムまたはA* アルゴリズム[基本的に情報に基づいたダイクストラ] のようなものが必要です。

これらのアルゴリズムを使用するには、迷路をグラフとしてモデル化する必要がありG=(V,E)ますV = { all moveable squares in the maze }。E = {(u,v) | you can move from u to v in a sinlgle step }

正方形のコストがcost(v)各正方形ごとにある場合、重み付け関数が必要になります: w:E->R: 次のように定義します。w(u,v) = cost(v)

Answer 3

Pledge Algorithm は、あなたが話している種類の迷路に役立ちます。以下で構成されています。

ゴールへの一般的な方向がわかっている場合は、方向を選択するのは良いことですが、ランダムな方向でも構いません。北を選んだとしましょう。

障害物にぶつかるまでその方向に進みます。

どのくらい回転するかを追跡しながら、障害物をたどります。たとえば、北に行くと東西の壁にぶつかります。東 (90 d) に曲がり、壁に沿って南 (180 d)、西 (270 d)、そして再び北 (360 d) に曲がります。回転した量が 0 になるまで、壁をたどるのを止めません。つまり、壁が西 (反対方向に回転した 270d)、南 (180d)、東 (90d)、そして最後に北 (0d) になるまで追跡し続けます。 . これで、フォローを停止できます。

障害物にぶつかったときはいつでもそうしてください。やがて迷路の最北端にたどり着きます。間違った方向を選択したためにまだゴールが見つからない場合は、東または南、またはゴールに最も近い方向で再試行してください。