2

我在 openSet 上使用 std::priority_queue 实现 A* 算法。在算法的某个时刻，如维基百科伪代码：

else if tentative_g_score < g_score[neighbor]
    tentative_is_better := true

其次是

if tentative_is_better = true
    came_from[neighbor] := current
    g_score[neighbor] := tentative_g_score
    f_score[neighbor] := g_score[neighbor] + h_score[neighbor]

意味着必须对 priority_queue 执行搜索并更改其中一个元素的值，这是不可能的（据我所知）。

此外，在这一行：

if neighbor not in openset

一个人不能在优先队列上搜索，所以如果不能在优先队列上实现，我通过创建一个 std::set 解决了这个问题，它只告诉我们哪些元素在 openSet 上（这样当我添加/删除一个元素到openSet，我添加/删除到 std::set 和 std::priority_queue)。

所以，我想知道如何避免第一个问题，或者应该将哪个 std::container 真正用于这个特定的（但一般的 A*）实现。

更一般地说，我想知道哪种方法是使用 std 容器的 A* 的有效方法？

4

4 回答 4

2

我之前用 STL 实现了 A* 算法并大致经历了相同的情况。

我最终只使用 std::vector ，使用标准算法，如 push_heap 和 pop_heap （这是 priority_queue 使用的）来保持它们的顺序。

需要明确的是：您应该使用向量来实现它并使用算法来操纵向量并使它们保持良好状态。它比使用某些替代方法更容易并且可能更有效。

更新：

今天我肯定会尝试一些 Boost 容器，比如这些：http: //www.boost.org/doc/libs/1_55_0/doc/html/heap.html但前提是我被允许使用 Boost（比如例如我自己的代码）。

于 2012-05-01T06:53:15.730 回答
1

您可以依靠算法的行为来解决这个问题。使用标准priority_queue，但不是增加/减少键操作，而是将新节点插入优先级队列。两个继任者现在都位于优先级队列中。优先级较高的将被优先考虑，然后扩展并添加到关闭列表中。当具有更高优先级的附加节点被取出时，它已经关闭并因此被丢弃。

于 2014-01-31T18:18:26.267 回答
0

不幸的是，std::容器目前不支持您需要的操作 - 真正需要的是支持decrease/increase_key样式操作的“索引”优先级队列。

一种选择是滚动您自己的容器（基于增强的二进制堆）来执行此操作，如果这听起来工作量太大，您几乎可以通过使用增强的数据结构来伪造它- 这两个选项都在此处std::set进行了更详细的讨论.

正如其他人所说，另一种选择是完全删除优先级队列并尝试维护一个排序的std::vector. O(log(n))这种方法肯定会奏效，并且可能需要您进行最少的编码，但它确实对整个算法的渐近缩放具有重大影响 -在保持排序顺序的同时实现队列的快速更新将不再可能.

希望这可以帮助。

于 2012-05-01T07:25:58.020 回答
0

如果没有decrease_key，您可以将节点重新添加到开放集中。每当你从开放集中弹出一个节点时，检查它的键是否大于该节点的当前分数；如果是，则继续而不处理该节点。这损害了 A* 的效率证明，但实际上这并不是一个严重的问题。

于 2014-01-31T18:17:59.400 回答