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

Question

我是第一次开发A*,我使用了priority_queue作为开放集,直到我意识到你需要检查节点是否也在开放集中,而不仅仅是关闭节点.

事实是,你不能迭代一个优先级队列.那么为什么每个人都建议开放集的优先级队列？它还是最好的选择吗？我认为迭代它的唯一方法是制作副本,这样我就可以从中弹出所有内容(成本巨大).

什么是A*上最好的数据结构？

Answer 1

优先级队列(PQ)是抽象数据结构(ADS).实现它们有很多可能性.不幸的是,C++标准库提供的priority_queue相当有限,其他实现更适合实现A*.Spoilers:您可以使用std :: set/multiset而不是std :: priority_queue.但请继续阅读:

那么从优先级队列中实现A*需要的是:

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

任何优先级队列都可以执行1.,但是对于2.,您需要一个"可变"优先级队列.Standard-Lib不能这样做.此外,您需要一种简单的方法来查找优先级队列中的条目,以找出减少密钥的位置(当A*找到更好的路径到已打开的节点时).有两种基本方法:将句柄存储到图形节点中的优先级队列元素(或使用映射来存储每个图形节点的这些句柄) - 或者自己插入图形节点.

对于第一种情况,您存储每个节点的句柄,您可以使用std :: multiset作为优先级队列.std :: multiset :: first()将始终是您的"最低成本"密钥,您可以通过从密钥中删除密钥,更改值并重新插入以及更新句柄来减少密钥.或者,您可以使用Boost.Heap中的可变优先级队列,它直接支持"reduce-key".

对于第二种情况,您需要某种"侵入式"二叉树 - 因为您的寻路节点本身需要位于优先级队列中.如果您不想自己滚动,请参阅Boost.Intrusive中的有序关联容器.