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

Question

3

如果原因是起始节点位置总是变化的，那么我们是否可以修改OPEN集合中每个节点的g值而不是h值？（例如，减去刚刚遍历的边缘的成本）

- Chara

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- FrankS101 · Answer 1

D* Lite是一种基于LPA*（终身规划A*）的增量启发式搜索算法。LPA*从起点到目标顶点进行搜索，并将g值用作“起始距离”的估计值。与LPA*不同，D* Lite从目标到起点顶点进行搜索。这样，g值就成为“目标距离”的估计值。

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

总之，回答问题：

我们能否仅修改OPEN集合中每个节点的g成本，而不是h成本？

不行，g成本是已遍历路径的成本，而h成本是到达目标的估计成本。不确定的是到达目标的路径成本，而不是已遍历的路径成本。