使用启发式函数的A星算法中，寻找要扩展的具有最低值的节点的最有效方法是什么？

Question

使用启发式函数的A星算法中，寻找要扩展的具有最低值的节点的最有效方法是什么？

3

我正在使用A*算法解决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 值的最好方法是什么？只需找到最小值，还是我们必须在添加状态时修改列表（在添加状态时对列表进行排序），这样最小值将位于第一个位置。

- khpn

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- btilly · Accepted Answer

保持一个堆。

给定 n 个元素，您可以在时间复杂度为 O(n) 的情况下将它们转换为堆。一旦它们是堆，您可以在时间复杂度为 O(log(n)) 的情况下添加和删除元素，并且可以在时间复杂度为 O(1) 的情况下找到最小的元素。

实现一个堆只需要一个数组。根节点是0，下面的节点是在i处的2*i+1和2*i + 2。堆的条件是每个节点都比上面的节点小。最小值始终为根。要添加一个元素，只需将其推到数组上，并让它“下降”到其自然水平。要删除一个元素，请取出根元素，从数组中取出最后一个元素，将其放在根处，并让其“冒泡”到正确的位置。（在“冒泡”阶段，您将其与较小的两个子节点之一交换，直到它最终没有更小的子节点为止。）为了有效地创建一个数组，您从中位数元素开始，让每个元素“冒泡”。这个操作看起来像O(n log(n))，但仔细分析表明它只是O(n)。