8

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

问题是，您不能迭代优先级队列..那么为什么每个人都推荐开放集的优先级队列？它还是最好的选择吗？我认为迭代它的唯一方法是制作一个副本，以便我可以从中弹出所有内容（巨大的成本）。

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

4

3 回答 3

7

优先级队列 (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 中的有序关联容器。

于 2012-09-03T22:54:16.037 回答
3

主题非常大，如果您想了解不同的可能性并很好地了解哪种数据结构适合您的情况，我建议您阅读此页面：http: //theory.stanford.edu/~amitp/GameProgramming/ ImplementationNotes.html#set-representation

就我而言，二叉堆在实现难度和性能之间取得了很好的平衡，这完全是我想要的。但也许你正在寻找不同的东西？

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

于 2012-09-03T20:37:15.333 回答
-1

它们的意思是优先级队列不一定是语言附带的 std::priority_queue 类。如果内置的没有做你需要它来写你自己的，或者找到另一个。

于 2012-09-03T21:46:53.557 回答