search - 为什么 D* Lite 需要反向遍历图？

Question

如果原因是因为起始节点位置一直在变化，那我们就不能只修改OPEN集中每个节点的g成本而不是h成本吗？（例如减去您刚刚遍历的边的成本）

Answer 1

D* Lite 是一种基于 LPA*（Lifelong Planning A*）的增量启发式搜索算法。LPA* 执行从起点到目标顶点的搜索 a，并使用 g 值作为起点距离的估计值。与 LPA* 不同，D* Lite 向后搜索图，即从目标到起始顶点。这样，g 值就是目标距离的估计值。

实际上，D* Lite 是通过交换起始和目标顶点以及反转所有边从 LPA* 派生的。因此，两种算法应用于图的前提条件相同，所有节点的后继和前驱都必须是可获取的。

总结并回答您的问题，

我们不能只修改 OPEN 集中每个节点的 g 成本而不是 h 成本吗？

不，g-cost 是已经经过的路径的成本，而 h-cost 是达到目标的估计成本。不确定的是达到目标的路径的成本，而不是已经走过的路径。