如何使用广度优先搜索找到在地图中的最短路径？ [英] How can you use a breadth-first search to find the shortest path in a map?

问题描述

为了简单起见，假设我有图：

 ○○P 2 O |
○○○○○
Ø| Ø| Ø
○○○○○
一○○○○
 

在这我想用一个广度优先搜索从A的最短路径，位置指定的旅行至P |是禁区。我怎样才能达到这个结果呢？我一直看到用于查找某个位置（P在这种情况下）的广度优先搜索，但我还没有看到用来存储路径距离和计算最短的一个（也没有有效的方法，任何实现存储previously前往的地方，并从进一步研究中排除）。此外，什么队列通常建议的图表是必然很大，需要大量的push和pop？

解决方案

广度优先搜索的优点在于它会自动寻找最短路径（你只需要跟踪，你来了，当你访问一个节点从）。 随着广度优先搜索，你总是有最便宜的路径在队列的开头昂贵的底。只要你打你的目标 P ，保证您的路径长度是最小的。

这是的std ::队列是实现它的精美绝伦的选择。

在回应您的评论：您拥有的节点队列 / 顶点的（在你的情况，这些都是你的细胞）。当你访问一个节点，你，你有没有previously访问到队列中添加所有的邻居。为了跟踪哪些节点你已经访问过并在您的路径而来，保留了的std ::阵列 / 的std ::向量从那; 身边，与您的每一个节点中的一个元素。然后，（伪code！）

 采取从队列元v
 对于V的每个邻居x
    如果从那[X]！= NULL
     从那[X] = V
     请将X队列的末尾
 

一旦你打你的目标节点 P ，你可以通过从那找到路径。

For simplicity sake, suppose I have the graph:

O O P O |
O O O O O
O | O | O
O O O O O
A O O O O

In which I want to use a breadth-first search to travel from A to P by the shortest path, where positions designated by | are restricted areas. How can I achieve this result? I've always seen the breadth-first search used to find some location (P in this case), but I haven't seen any implementation used to store path distances and compute the shortest one (nor efficient methods to store previously visited locations and exclude them from further scrutiny). Also, what queue is typically suggested for graphs that are necessarily large and require extensive pushes and pops?

解决方案

The beauty of breadth-first search is that it will automatically find the shortest path (you just need to keep track of where you came from when you visit a node). With a breadth-first search, you always have the cheapest paths at the beginning of the queue and the expensive ones at the end. As soon as you hit your goal P, you are guaranteed that the path length is minimal.

An std::queue is an absolutely fine choice for implementing it.

In response to your comment: You have a queue of nodes / vertices (in your case, these are your cells). When you visit a node, you add all neighbours that you haven't previously visited to the queue. To keep track of which nodes you have visited and where your paths came from, keep an std::array/std::vector wherefrom; around, with one element for each of your nodes. Then (pseudocode!)

take element v from queue
 for each neighbour x of v
    if wherefrom[x] != NULL
     wherefrom[x] = v
     add x to end of queue

Once you hit your target node P, you can just backtrack through wherefrom to find the path.

这篇关于如何使用广度优先搜索找到在地图中的最短路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！