3

我正在用星算法做 8 个谜题求解器。我在这个求解器中实现了曼哈顿和错位的启发式函数。在某些情况下，求解器可以正常工作。但在某些情况下，找到解决方案需要花费大量时间。我认为我的问题之一是在打开列表中查找具有最低值的节点的函数（等待扩展）。

 a part of psedocode(from wiki)
 while openset is not empty
     x := the node in openset having the lowest f_score[] value
     if x = goal
         return reconstruct_path(came_from, came_from[goal])
     ................................

那么找到最低 f_score 值的最佳方法是什么？只需找到最小值，否则我们必须在有状态要添加时修改列表（添加状态时对列表进行排序），以便最小值将位于第一个位置。

4

1 回答 1

3

维护一个堆。

给定n元素，您可以及时将它们变成堆O(n)。一旦它们成为堆，您就可以及时添加和删除元素，O(log(n))并且可以及时找到最小的元素O(1)。

要实现一个，您只需要一个数组。根节点是'th0下面的节点是 at和。堆条件是每个节点都小于它上面的节点。最小的永远是根。要添加一个元素，只需将它推到数组上，然后让它“下降”到它的自然水平。要删除一个元素，请取出根元素，从数组中取出最后一个元素，将其放在根处，然后让它“冒泡”到正确的位置。（在“冒泡”阶段，您将它与它的两个子节点中较小的一个交换，直到它下面最终没有更小的子节点。）为了有效地创建一个数组，您从中间元素开始，让每个元素“冒泡”向上”。i2*i+12*i + 2O(n log(n))O(n).

于 2011-04-05T00:35:21.707 回答