artificial-intelligence - 使用启发式方法在 A 星中找到具有最低扩展值的节点的最有效方法是什么？

Question

我正在使用星算法解决 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 值的最佳方法是什么？只需找到最小值，或者当我们有一个状态要添加时我们必须修改列表(当我们添加状态时对列表进行排序)因此最小值将在第一个位置。

Answer 1

维护 heap .

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

要实现一个，您只需要一个数组。根节点是0和 i 下面的节点'th 在 2*i+1和 2*i + 2 .堆条件是每个节点都小于它上面的节点。最小的总是根。要添加一个元素，只需将它推到数组上，然后让它“落下”到它的自然水平。要删除一个元素，请取出根元素，将最后一个元素从数组中取出，将其放在根部，然后让它“冒泡”到正确的位置。 (在“向上冒泡”阶段，你将它与它的两个子节点中较小的一个交换，直到它下面最终没有较小的子节点。)为了有效地创建一个数组，你从中间元素开始并让每个元素“冒泡”向上”。这个操作看起来像 O(n log(n))但仔分割析才知道，这只是O(n) .