2

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

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

我想使用广度优先搜索从 A 到 P 的最短路径，其中由 | 指定的位置 是禁区。我怎样才能达到这个结果？我一直看到用于查找某个位置的广度优先搜索（在这种情况下为 P），但我还没有看到任何用于存储路径距离和计算最短路径距离的实现（也没有有效的方法来存储以前访问过的位置和将他们排除在进一步审查之外）。此外，对于必须很大并且需要大量推送和弹出的图形，通常建议使用什么队列？

4

4 回答 4

6

广度优先搜索的美妙之处在于它会自动找到最短路径（您只需要在访问节点时跟踪您来自哪里）。使用广度优先搜索，您总是在队列的开头找到最便宜的路径，而在最后找到昂贵的路径。一旦你达到你的目标P，你就可以保证路径长度是最小的。

Anstd::queue是实现它的绝对好选择。

回应您的评论：您有一个节点/顶点队列（在您的情况下，这些是您的单元格）。当您访问一个节点时，您会将之前未访问过的所有邻居添加到队列中。要跟踪您访问过哪些节点以及路径来自何处，请在周围保留一个std::array/ std::vector wherefrom;，每个节点都有一个元素。然后（伪代码！）

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

一旦你击中你的目标节点P，你就可以回溯wherefrom找到路径。

于 2013-01-30T01:29:37.123 回答
3

我建议您阅读 Dijkstra 的算法，然后进行 A* 搜索。

这是在 C++ 中解决此问题的简单方法：

  1. 创建一个初始化为 -1 的整数 std::vector（我们称之为“trail”），地图中的每个节点都有一个元素（在您的示例中大小为 25）。这将用于指示已经搜索了哪些节点，以及从哪里搜索了它们。'trail' 值为 -1 的节点尚未被搜索到，而 'trail' 值为 8 的节点已从节点 8 中搜索到。

  2. 创建一个整数的 std::queue（我们称之为“search_queue”）。然后推送包含'A'的节点的ID，并将其'trail'值标记为自身。例如，如果“A”是节点 20，则将 trail[20] 设置为 20；这记录了路径从那个点开始。

  3. 从'search_queue'中弹出最前面的节点，依次查看它的每个邻居，如果他们的trail值为-1，则将他们的id添加到队列中，并且他们不受限制（不包含'|'）。

  4. 重复第 3 步，直到找到“P”（您已达到目标！），或者队列为空（没有有效路径）。

  5. 如果找到“P”，则使用“轨迹”向量将路径追溯到起点——每个节点将指向路径中的前一个节点，直到到达指向自身的节点。那是你开始的地方，所以你现在有一个完整的路径！

您不必计算任何距离，因为呼吸优先搜索的性质保证算法找到的第一个有效路径将是可能的最短路径。

于 2013-01-30T01:49:02.140 回答
2

我假设你有一个带有 APO | 的二维数组。价值观。如果未知，您将需要使用蛮力搜索找到 A。

对于路径，从 A 出发的最短路径可以通过创建一组 1-move 位置（即上方、右侧以及如果允许对角线移动，则可能位于右上方）来找到。当你这样做时，你想跟踪哪些位置已经被访问以避免返回到同一个方块，所以你需要对原始数组做一些事情（例如将访问的位置从“O”更改为“o”）或者有另一个数组只是为了这个。从 1 步位置，您可以创建一组尚未访问过的合法 2 步位置。继续前进，直到找到“P”。

关于容器的选择：使用上面的算法，你不会弹出任何东西——可以只使用一个向量。

作为优化，您可能也想要本地 P 并尝试深度优先遍历两者之间最明显的路径 - 在您的插图案例中 [diagonally-up-right-]-else-up-else-right 与“up " 允许直到您到达目标行，并且 "right" 直到您到达列。也可以做 right-else-up 或代替。

于 2013-01-30T01:44:31.160 回答
0

获得地图后：

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

定义图，1指示是否存在边：

1 1 P 1 0
1 1 1 1 1
1 0 1 0 1
1 1 1 1 1
A 1 1 1 1

在哪里a_ij = 0 iff m_ij = | and elsewhere a_ij = 1

然后运行​​Dijkstra 算法或Bellman-ford 算法。

如果您坚持使用BFS，这里有一个解释为什么它也有效：

寻找最短路径时，广度优先搜索如何工作？

于 2013-01-30T01:33:53.730 回答