artificial-intelligence - 通过地图查找路径的算法

Question

给定一个多维数组，其中 X 是墙，* 是目标位置。您如何在不陷入循环的情况下找到路径？

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

Answer 1

首先，您需要一个为每个单元或节点提供有效邻居的函数。

然后，为了找到到达目标的最短路径，应该使用广度优先搜索。如果您从起始位置开始并扩展节点直到达到目标，您将始终找到最短路径（如果有）。或者，您可以从目标开始并扩展，直到覆盖整个地图，您将获得每个起始位置到目标的最短路径（这当然只有在目标不移动时才有意义）。

为了不陷入循环，最重要的方面是保留已扩展节点的列表（或集合、映射或其他）。

对于更复杂的地图，或者当某些路径的不同“成本”发挥作用时，您可能更愿意使用 A* 或 Dijkstra 算法。