A *什么是开放集合的最佳数据结构？

Question

我第一次开发A *，并且我使用了开放集合的priority_queue，直到我意识到您需要检查节点是否处于开放集合中，而不仅仅是关闭集合。

事情是，你不能迭代优先级队列......所以，为什么大家都推荐一个优先级队列的开放集？它还不是最好的选择吗？我认为迭代它的唯一方法是制作副本，这样我就可以从中弹出一切（巨大的成本）。

在A *上使用的最佳数据结构是什么？

Answer 1

优先级队列（PQ）是一个抽象数据结构（ADS）。有很多可能性来实现它们。不幸的是，C++标准库提供的priority_queue是相当有限的，其他实现对于实现A *更适合。剧透：你可以使用std :: set/multiset而不是std :: priority_queue。但阅读：

那么你从优先级队列需要实现A *是：

1. 可以用最低的成本
2. 节点减少任意元素的成本

任何优先级队列都可以执行1.，但对于2.，您需要一个“可变”优先级队列。标准库不能做到这一点。此外，您需要一种简单的方法来查找优先级队列中的条目，以找出减少键的位置（因为当A *发现到已打开节点的更好路径时）。有两种基本的方法：您可以在图形节点内存储一个优先级队列元素的句柄（或使用映射为每个图形节点存储这些句柄） - 或者您自己插入图形节点。

对于第一种情况，您为每个节点存储句柄，您可以将std :: multiset用于优先级队列。 std :: multiset :: first（）将永远是您的“最低成本”键，您可以通过从集中删除键，更改值并重新插入以及更新句柄来减少键值。或者，您可以使用Boost.Heap中的可变优先级队列，它直接支持“减少键”。

对于第二种情况，您需要某种“侵入式”二叉树 - 因为您的寻路节点本身需要位于优先队列中。如果您不想推出自己的产品，请参阅Boost.Intrusive中的有序关联容器。

Answer 2

的主题是非常大的，我建议如果你想知道不同的可能性，并有一个很好的理解其中的数据结构适合于您的情况您阅读此页： http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html#set-representation

在我的情况下，二进制堆在执行和执行的难度之间取得了很好的平衡，这完全是我所期待的。但也许你正在寻找不同的东西？

文档的其余部分是A *一个很好的参考游戏开发 http://theory.stanford.edu/~amitp/GameProgramming/index.html

Answer 3

他们说的是优先级队列不一定是自带的语言的std :: priority_queue类。如果内置的一个不能满足你自己的需求，或者找到另一个。