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

Question

我们经常需要丢弃重复的状态，如 uniform-cost search 中所述.

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

Priority Queue 不提供用于搜索项目的优先级然后更新它的界面。我很惊讶我找不到与此相关的任何资源，任何人都可以提供帮助。

Answer 1

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

A priority search queue efficiently supports the opperations of both a search tree and a priority queue. A Binding is a product of a key and a priority. Bindings can be inserted, deleted, modified and queried in the queue (usually in logarithmic time), and the binding with the least priority can be retrieved in constant time.

这是一个 implementation在 Haskell 中。