我一直在研究统一成本搜索的算法,尽管我能够理解整个优先级队列过程,但我无法理解算法的最后阶段。
如果我们看at this graph ,在应用该算法后,我将得到每个节点的最小距离,但假设我想知道 A 到 G 之间的路径(就像示例一样),我将如何计算它?
最佳答案
通常,您从尚未探索的每个节点的无限总成本开始。然后你可以稍微调整一下算法来保存前身:
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
之后,您可以从您的目标开始,检查前辈的顺序。
关于algorithm - "uniform-cost search"算法中的路径如何获取?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12755893/