tree - A* 搜索，当评估函数评估相同时，下一个要扩展的节点

Question

当评估函数 (f(n) = g(n) + h(n)) 对两个节点进行相同评估时，我无法理解在 A* 搜索树中接下来应该扩展哪个节点/状态。
示例 1

我的理解是，边界存储为按 f 排序的优先级队列，因此由于边界上的节点具有相同的值，因此将评估首先添加到队列中的节点。

示例 2

在这个例子中，B 的评估函数小于 C，因此扩展但生成了一个与 C 具有相同 f 的节点 D，在这种情况下，接下来将选择哪个节点进行扩展？

（我意识到这个问题可能应该已经发布在 cstheory.stackexchange 上，但我没有足够的声誉来发布图片，道歉）
提前致谢

Answer 1

选择哪一个并不重要，取决于优先级队列的实现，但更常见的是 C，因为新创建的节点 D 不会先于已经在队列中的 C。如果我们继续使用 C 并且稍后我们意识到 h(C) 被低估了，那么当前节点（C 的访问器）的 f 值变得大于 f(D)，然后算法将返回并在 D 变为顶部时展开的队列。这将起作用，因为启发式 h 应该总是给出小于或等于实际成本的值。