最短路径算法未赋权图

Question

为了提高我的java脚本技能，我正在尝试用js开发一个吃豆人游戏。具有20 x 20的栅格。此网格有0和1，它们表示是否有一面墙或一条路径。现在我想开发一个让恶魔跟随吃豆人的算法。我不确定我应该使用哪种算法。

所以我对函数的输入将是foo(当前位置，吃豆人位置，网格，路径)

var maze = [            [0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0],
                        [0,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0],
                        [0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0],
                        [0,1,0,1,0,1,1,1,1,0,0,1,1,1,1,0,1,0,1,0],
                        [0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0],
                        [0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0],
                        [0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0],
                        [0,1,1,1,1,1,0,0,0,1,1,0,0,0,1,1,1,1,1,0],
                        [0,1,0,0,0,1,1,0,0,1,1,0,0,1,1,0,0,0,1,0],
                        [0,1,0,0,0,0,1,0,0,1,1,0,0,1,0,0,0,0,1,0],
                        [1,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,1,1],
                        [0,1,0,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0,1,0],
                        [0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0],
                        [0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0],
                        [0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0],
                        [0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0],
                        [0,1,0,1,0,1,1,1,1,0,0,1,1,1,1,0,1,0,1,0],
                        [0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0],
                        [0,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0],
                        [0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0]];

Answer 1

对于未加权的图，您有几个用于查找最短路径的选项：

• -最简单的解决方案- BFS是完整的和最优的-它将找到最短路径，如果这样的exist.
• -基本上相同，但从两边做BFS，并在两个BFS相遇时结束。它显著减少了发现的顶点数量。我解释了更多关于如何做到这一点，以及为什么它在this thread.
• Heuristical 中很好-它是一个有见地的算法，因此通常比其他算法更快，但更难编程。使用像manhattan distances.

这样的admissible heuristic function

就我个人而言--我想在这种情况下我会使用BFS --但是从pacman开始，直到你发现所有的“目标”(恶魔的位置)-它会给你从每个恶魔到pacman的最短路径。

请注意，如果你只有几个恶魔和一个大棋盘，做几次A* (每个恶魔一次)可能是一个更好的解决方案。

人们可能应该对它进行基准测试，看看哪一个更好。

Answer 2

如果需要查找从源到所有顶点的最短路径，请从源执行广度优先搜索，并继续将每个顶点的父节点存储在单独的array.Following中。父节点将为您提供从每个顶点到其父节点的路径。

Answer 3

我想Depth-first search也在这里工作。与广度优先搜索相比，在使用DFS时，不需要存储所有的叶节点。但它有时无法找到解决方案。这里的输入不是那么复杂，所以我认为DFS已经足够好了。

此外，A*搜索算法是最好的选择，因为它比不知情的搜索更快，而且总是完整和最优的。它保证了解决方案是最优的。对于复杂的情况，创建一个有效的启发式函数确实是很费钱的。在这里，您可以使用曼哈顿距离或欧几里德距离。