c++ - 用于 A* 优先级队列的 C++ 集合与向量 + 堆操作

Question

make_heap/push_/pop_什么时候使用 std::set 比使用 std::vector 以及A* 操作中的优先级队列更有效（时间） ？我的猜测是，如果打开列表中的顶点很小，则使用向量是更好的选择。但是有人有这方面的经验吗？

Answer 1

如果我不得不冒险猜测？我猜向量版本可能是一个不错的选择，因为一旦它增长到一定大小，就不会有很多分配。

但我不喜欢猜测。我更喜欢硬数字。尝试两者，个人资料！

Answer 2

1. 对于 A* 搜索，我会使用基于 std::vector 的优先级队列。
2. 但是，从 std::vector 到另一个 STL 容器的实现变化应该是微不足道的，所以我会尝试不同的版本，看看它如何影响算法性能。除了 stl::map，我肯定会尝试 stl::deque。

Answer 3

使用优先队列。基于二进制堆的一个很好（如基于向量的 std 优先级队列）。您可以在 O(n) 时间内构建堆，并且所有相关操作都需要 O(logn)。除此之外，您还可以实现对 a* 有用的减键操作。然而，为 std 队列实现可能会很棘手。使用集合执行此操作的唯一方法是删除元素并以不同的优先级重新插入它。

编辑：您可能想研究使用

std::make_heap

（及相关功能）。这样您就可以访问向量并且可以轻松实现 reduce_key。

编辑 2：我看到你打算使用 make heap，所以你所要做的就是实现减少键。

Answer 4

If you're doing A* pathfinding work, check out the articles in AI Wisdom by Dan Higgins. In there is a description of how to get data structures fast. He mentions a "cheap list" which is like having a hot cache for recent nodes and avoiding a lot of the penalties for pathfinding data structures.

http://introgamedev.com/resource_aiwisdom.html

Answer 5

我不认为用于 A* 搜索的优先级队列的基于向量的数据结构是一个好主意，因为您将不断地在列表中的某处添加单个元素。如果边缘（我假设这就是你的做法）很大并且要在中间添加元素，那么这是非常低效的。

几周前我在 Java 中实现 A* 时，我使用了 Java PriorityQueue，它显然是基于优先级堆的，这似乎是一个很好的方法。我建议set在 C++ 中使用。

编辑：谢谢尼基。我现在了解如何实现二进制堆（使用数组），并且我了解您在问题中实际提出的问题。我怀疑 apriority_queue是最好的选择，尽管（正如伊戈尔所说）将它换成 aset来检查它的性能并不难。我猜想使用二进制堆实现优先级队列（至少在 Java 和 C++ 中）是有原因的。