最短路径 - 广度优先搜索

我有一篇文章的任务，绝不是要求任何代码帮助，只是帮助理解如何解决此问题。最短路径 - 广度优先搜索

我们在哪里给了最小的工作材料，而教授只浏览了广度优先搜索的内容。

我们需要通过迷宫找到我们的方式，迷宫被创造出来，并且你的人每次都会落在一个随机空间中。

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

现在我从这个搜索算法理解如下：

树或图形必须在各级搜索
我们需要的路径存储在a queue（FIFO）
然后找到最终路径中的最短路径

我到底该如何处理这类问题？

我们知道开始和结束，再加上我们可以很容易地获得当前块的所有相邻块。

非常感谢。

来源

2015-10-19 Tiaan Swart

如果您不是在寻求代码帮助，那么您来到了错误的网站。 – dursk

嗨@dursk感谢您的贡献，但我相信在这里提出这个问题可以。 –

那么，你应该至少移除python标志。 – dursk

你似乎错过了广度优先搜索的一些细微差别。

树或图形必须水平

这是正确的搜索。虽然你不一定会追踪一组不同的关卡，但你自然会在完成后继续下一个关卡。

我们需要的路径存储在队列（FIFO）

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

然后找出所有路径的最短路径到端项

在具有均匀的边权的曲线图，这是不必要的。你找到的第一条路径是最短的。（请注意均匀边权的要求，这是对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)

还有更多一点如果你想跟踪你遍历的路径，加入到这个框架中，防止你的路径翻倍（在一个无向图中这对于确保终止非常重要），防止重复处理一般节点（如果有周期和你想要终止），跟踪长度等。但这是它的基本框架。

来源

2015-10-19 05:58:40 moreON

这使得更多的意义谢谢！ –

最短路径 - 广度优先搜索

回答

相关问题