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應始終給出比實際成本更小或相等的值。