最短路径 - 广度优先搜索

Question

我有一篇论文的作业，我绝不是在寻求任何代码帮助，只是帮助理解如何解决这个问题。

我们只给了很少的 material 工作，教授只浏览了广度优先搜索的内容。

我们需要找到穿过迷宫的路，迷宫已经创建，您的人每次都会随机 space 着陆。

当按下键时，当前位置被发送到函数，我们必须从那里使用广度优先搜索来找到最短路径。

现在我从这个搜索算法中了解到以下内容：

必须按级别搜索树或图
我们需要将路径存储在 a queue (FIFO)
然后在所有路径中找到最短路径到最终项目

我该如何处理这类问题？

我们知道开始和结束，而且我们可以很容易地得到当前块的所有邻居块。

非常感谢。

Answer 1

您似乎忽略了广度优先搜索的一些细微差别。

Tree or graph must be searched in levels

这是正确的。虽然您不一定要跟踪一组不同的级别，但您可以在完成一个级别后自然地继续下一个级别。

We need to store the paths in a queue (FIFO)

不是真的。您通常存储未来节点以在队列中探索，而不是整个路径。如果需要，维护路径是一个额外的问题。

Then find the shortest path out of all paths to the end item

在具有均匀边权重的图中，这是不必要的。您找到的第一条路径是最短的。（请注意统一边缘权重的要求，这对于 BFS 是正确的）

目标节点的 BFS 的一般代码如下所示：

q := new Queue
q.enqueue(start)
goal_found := false
while( q is not empty )
    n := q.dequeue()
    if n is goal then
        goal_found := true
        break
    for each neighbour v of n
        q.enqueue(v)

if(goal_found)
    //do something (success)
else
    //do something else (failure)

如果你想跟踪你经过的路径，还有一点要添加到这个骨架，防止在你的路径上加倍返回（在无向图中这对于确保终止非常重要），防止重复处理一般节点（如果有循环并且你想终止则需要），跟踪长度等。但这是它的基本框架。

最短路径 - 广度优先搜索

Shortest Path - Breadth first search

algorithm

queue

breadth-first-search