当具有相同启发式值的节点被添加时，A *搜索如何选择下一个节点？

Question

我对这个概念有基本的了解，但一位讲师给出的模型答案使我感到困惑，

我对（2,3）B节点如何在（2,3）之前扩展这一事实感到困惑，该节点理论上首先被添加到队列中（在添加节点B之前）

此树是网格的最短路径评估的图形表示。 这棵树并不意味着（2,3）A节点没有孩子实际上，他们指的是网格中的相同位置，有人可以澄清我所缺少的吗？在此先感谢：）

Answer 1

答案是取决于优先级队列的实现。

[使用数组的常规heap实现。元素的排序如下：

0 1 2 3 4 5 6 7 8 9 10

但是在位置i以下，接下来的两个是2i+1和2i+2。因此，数组是一个看起来像这样的树结构：

[0,
  [1,
    [3, [7, 8]],
    [4, [9, 10]]]],
  [2, [5, 6]]]

现在假设3, 5的优先级彼此相同，因此6, 7的优先级也相同。并按此顺序添加了这4个。还假设堆在关系上首先放下顶部元素（但是您想到了它）。然后，在提取时，我们最终将3和5移到底部，并且3首先下降。但是，当您继续进行提取时，您最终会在6, 7之间找到平局，现在7在顶部（但是，您将思维方向对准了），因此它首先下降。

结果是，优先级队列保证事物按优先级顺序出现，但顺序上没有其他保证。因此，具有相同优先级的事物可以以任何顺序出现。

这直接与Heapsort不是稳定排序的原因有关。