A *搜索，当评估函数评估相同时接下来展开的节点

Question

当评估函数（f（n）= g（n））时，我无法理解在A *搜索树中下一个应展开哪个节点/ + h（n））对两个节点的评估结果相同。
实施例1

Tree1 http://i39.tinypic.com/22w6d.jpg

我的理解是，前沿被存储为被F和因此为对前沿节点具有添加到该队列中的该节点的值相同第一将会排序优先级队列评估。

实施例2

Tree2 http://i39.tinypic.com/2wemfxg.jpg

在本例中B的评价函数小于C和因此扩展，但所产生的节点d具有相同˚F为C，在这种情况下，应选择哪个节点下一步扩展？

（我意识到这个问题也许应该被张贴在cstheory.stackexchange，但我没有足够的信誉发表图片，道歉）
预先感谢

Answer 1

不要紧，哪一个会被选择，取决于优先级队列的实现，但更多的时候它会是C，因为新创建的节点D不会在已经在队列中的C之前。如果我们继续使用C并且后来我们认识到h（C）被低估，那么当前节点（C的访问者）的f值变得比f（D）大的多，算法将返回并扩展D，因为它变成了顶部队列。这将起作用，因为启发式h应始终给出比实际成本更小或相等的值。