A*算法中，什么是最适合用于Open Set的数据结构？

Question

我第一次开发A*算法，我使用优先级队列作为开放集，直到我意识到你需要检查节点是否也在开放集中，而不仅仅是关闭集中。

问题是，你无法遍历优先级队列。那么为什么每个人都建议使用优先级队列作为开放集？它是否仍然是最佳选项？我认为唯一能够遍历它的方法是制作副本，这样我就可以从其中弹出全部元素（代价巨大）。

在A*算法中，最好使用哪种数据结构？

- Icebone1000

---

http://stackoverflow.com/questions/11912736/c-a-star-implementation-determining-whether-a-node-is-already-in-the-priori - Rost

Answer 1

优先队列（PQ）是一种抽象数据结构（ADS）。有许多可能的实现方法。不幸的是，C++标准库提供的priority_queue相当有限，其他实现更适合于实现A*。剧透：您可以使用std::set/multiset代替std::priority_queue。但请继续阅读：

那么你需要从优先队列中获取什么来实现A*：

1. 获取成本最低的节点 2. 降低任意元素的成本

任何优先队列都可以完成第一点，但是对于第二点，您需要一个“可变”优先队列。标准库中的优先队列无法做到这一点。此外，您需要一种简单的方法来在优先队列中查找条目，以查找要降低键的位置（当A*找到已经打开的节点的更好路径时）。有两种基本方法：将优先队列元素的句柄存储在图形节点内（或使用映射为每个图形节点存储这些句柄）-或者插入图形节点本身。

对于第一种情况，在每个节点上存储句柄的情况下，您可以使用std::multiset作为优先队列。 std::multiset::first()将始终是您的“最低成本”键，并且您可以通过将其从集合中删除，更改其值并重新插入，并更新句柄来降低键。或者，您可以使用Boost.Heap中的可变优先队列，它直接支持“降低键”。

对于第二种情况，您需要某种“侵入式”二叉树-因为您的路径查找节点本身需要在优先队列中。如果您不想自己编写代码，请参阅Boost.Intrusive中的有序关联容器。

- ltjax

Answer 2

主题非常广泛，如果您想了解不同的可能性并对哪种数据结构适合您的情况有很好的理解，我建议您阅读此页面： http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html#set-representation 在我的情况下，二叉堆是难度和性能之间的良好平衡，这正是我所追求的。但也许您正在寻找不同的东西？

文档的其余部分是游戏开发中A*算法的非常好的参考。 http://theory.stanford.edu/~amitp/GameProgramming/index.html

- ClemKeirua

Answer 3

他们指的是优先队列，而不一定是语言自带的std::priority_queue类。如果内置的队列无法满足您的需求，请自己编写或找另一个适合的。

- stonemetal