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

Question

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

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

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

Answer 1

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

采用通常的堆实现与数组。元素的顺序如下：

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首先下降。但是当你继续提取时，你最终会得到一个平局，现在在顶部（左边，但是你定位你的想法），所以它首先下降。536, 77

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

这与为什么Heapsort不是一个稳定的排序直接相关。