algorithm - 「均一コスト検索」アルゴリズムでパスを取得する方法は?

Question

一様コスト検索のアルゴリズムを調べてきましたが、優先キューの手順全体を理解できても、アルゴリズムの最終段階を理解できません。

このグラフを見ると、アルゴリズムを適用した後、各ノードの最小距離が得られますが、(例のように) A から G までのパスを知りたい場合、どのように計算すればよいでしょうか?

Answer 1

通常、まだ探索されていないすべてのノードの合計コストは無限から始めます。次に、前任者を保存するためにアルゴリズムを少し調整できます。

for each of node's neighbours n
    if n is not in explored
        if n is not in frontier
            frontier.add(n)
            set n's predecessor to node
        elif n is in frontier with higher cost
            replace existing node with n
            set n's predecessor to node

その後、目標から始めて、前任者のシーケンスを確認できます。