haskell - 如何在 Haskell 中实现最佳优先搜索？

Question

有没有办法在 Haskell 中有效地进行最佳优先搜索？我想维护一棵动态树。我有一个启发式函数，可以计算每个节点的数字，还有一个后继函数，它将返回节点的子节点列表。

在每一步中，我都想采用最佳启发式的叶节点并用它的子节点替换它。重复这个过程，直到我得到一个“足够好”的节点。

为此，我需要维护叶子的优先级队列。但是有没有一种方法可以让我有效地从优先级队列中的叶子到达它在树中的位置，以便我可以修改树？

Answer 1

一个可能的答案是使用 Haskell 最狡猾的可变性形式:懒惰。如果您懒惰地生成整个树(即使它无限)，然后根据您的优先级队列重复查看树中的不同点，那么您将只能生成尽可能多的树执行最佳优先搜索所需的树。

您仍然需要为重复遍历树的较低分支付费，但也许您可以以某种方式更改搜索结构以做得更好。