关于D* Lite算法反向遍历图及g代价修改可行性的技术问询

Great question—let’s unpack this clearly, since D* Lite’s design is all about efficiency in dynamic environments (like moving robots that encounter unexpected obstacles or shift their starting point).

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

D* Lite是专为目标节点固定，但起点（机器人位置）移动或环境动态变化（比如突然出现障碍物）的场景设计的。

如果用A*那样的正向遍历（起点→目标），每次机器人移动到新位置，都得从头重新规划整条路径——在大地图上这效率极低。

反向遍历（目标→起点）则完全换了思路：

• 我们预先计算并维护g(n)，它代表节点n到固定目标的最小代价。除非环境发生变化（比如某条边被阻断），这个值始终有效。
• h(n)则作为当前起点到节点n的启发式估计（比如曼哈顿距离）。当机器人移动到新起点时，我们只需要局部调整h(n)的值（具体来说，更新新起点的h值并传播小范围的变化），而非重新计算所有路径代价。

这种反向设计让D* Lite能复用几乎所有之前的计算结果，在起点移动或环境小范围变化时，路径更新速度极快。

能不能通过修改OPEN集合的g值代替h值来实现？ #

简单说：这不现实，而且会毁掉D Lite核心的效率优势*，原因如下：

• 在D* Lite的反向架构中，g(n)绑定的是到目标的固定代价，和起点无关。如果尝试在起点移动时修改g值，等于破坏了所有预先计算好的到目标的路径成本——直接违背了反向遍历的初衷。
• 就算切换到正向架构（g(n)代表起点→n的代价），起点移动时调整g值也远不止“减去刚遍历的边的代价”这么简单。每个节点的g值依赖于父节点的g值，起点改变意味着整个g值的基准都变了，你可能需要重新计算成百上千个节点的g值，这正是D* Lite要避免的情况。
• D* Lite的OPEN集合是按f(n) = g(n) + h(n)排序的。调整h只需要更新新起点附近的一小部分节点及其邻居；而调整g会迫使你重新处理所有依赖旧起点路径的节点，性能会暴跌。

总结下来，在D* Lite的反向遍历设计中，修改h值是处理起点移动的优雅高效方案——折腾g值会彻底抵消算法针对动态环境做的所有优化。

内容的提问来源于stack exchange，提问作者Chara