如何获得"统一成本搜索"算法中的路径？

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

之后,您可以从目标开始检查前辈的顺序.