algorithm - 统一成本搜索前沿的理想数据结构（优先级队列似乎不够）是什么？

Question

很多时候，我们需要丢弃重复的状态，如统一成本搜索中所述。

  if n is in frontier with higher cost
  replace existing node with n

Priority Queue 不提供用于搜索项目的优先级然后更新它的接口。我很惊讶我找不到任何有关此的资源，请任何人提供帮助。

Answer 1

许多优先队列实现允许保留对队列元素的一些引用，然后使用它来删除/更新该元素。

如果将优先级队列实现为二叉搜索树，则可以轻松保留此类引用。对于二叉堆，这是可能的，但更困难：您需要更新所有元素的引用，移动上堆或下堆。

有优先队列实现，允许在与统一成本搜索等算法一起使用时有效更新元素。请参阅配对堆和斐波那契堆。

Answer 2

您正在寻找优先搜索队列。

优先级搜索队列有效地支持搜索树和优先级队列的操作。绑定是密钥和优先级的产物。绑定可以在队列中插入、删除、修改和查询（通常以对数时间），并且可以在恒定时间内检索优先级最低的绑定。

这是 Haskell 中的一个实现。

Answer 3

实际上，您可以使用常规优先级队列来进行统一成本搜索。

您可以插入一个新的、更好的（节点、成本）对，而无需删除旧的。您将始终首先处理新插入的条目（因为它更好），并且处理旧条目实际上将是无操作的。缺点是您最终可能会在优先级队列中得到 O(E) 个元素（而不是 O(V)）。