artificial-intelligence - マップを通るパスを見つけるためのアルゴリズム

Question

Xが壁で、*がゴール位置である多次元配列が与えられます。ループに巻き込まれずにパスを見つけるにはどうすればよいですか？

$map=
array( array("X","X"," ","*"),
       array(" ","X"," ","X"),
       array(" "," "," "," "),
       array(" ","X","X"," "));

Answer 1

まず、各セルまたはノードの有効な近隣を提供する関数が必要です。

次に、ゴールへの最短経路を見つけるには、幅優先探索が必要です。開始位置から開始し、ゴールに到達するまでノードを展開すると、最短パス (存在する場合) が常に見つかります。または、ゴールから開始し、マップ全体をカバーするまで拡大することもできます。これにより、すべての開始位置でゴールへの最短経路が得られます (もちろん、これはゴールが動いていない場合にのみ意味があります)。

ループに陥らないようにするための最も重要な側面は、既に展開されているノードのリスト (またはセット、マップなど) を保持することです。

より複雑なマップの場合、または特定のパスに異なる「コスト」がかかる場合は、A* またはダイクストラのアルゴリズムを使用することをお勧めします。