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

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

Answer 2

访问以获取更多信息 https://www.youtube.com/watch?v=9vNvrRP0ymw

Insert the root into the queue
While the queue is not empty
      Dequeue the maximum priority element from the queue
      (If priorities are same, alphabetically smaller path is chosen)
      If the path is ending in the goal state, print the path and exit
      Else
            Insert all the children of the dequeued element, with the cumulative costs as priority