algorithm - 关于寻路：D*算法的外行详解

Question

我希望处理的大型网络（小世界图类型）本质上是动态的，经常添加和减少新节点。大概使用 D* over A* 会是在这种动态环境中检测路径的更好方法？

D*有多坚固？它有任何现实世界的经验吗？就像加密算法一样——D* 是否通过大量同行评审和测试得到强化？你会用 D* 来解决这个问题吗？

Answer 1

据我了解，第一次运行 D* 时，它会找到与 A* 相同的路径，运行时间几乎相同。然而，当一个节点改变它的边缘值或添加节点时，A* 重新计算所有路径，而 D* 只是第二次重新计算不一致的节点，而不是整个事情。

Anthony Stentz 的 D* 算法（此处为原始白皮书）在很大程度上已被其工作的衍生产品所弃用。D* Lite 和 LPA* 是最常见的，并且更容易编码/实现。

就现实世界的经验而言，来自 NASA 喷气推进实验室的 Joseph Carsten 和 Art Rankin 在火星探测器“Spirit”和“Opportunity”上安装了使用 D* Lite 元素的 Field D* 版本（此处使用 D* 的漫游车幻灯片） . 2007 年 2 月，它被用于完全自主导航火星探测器。

替代文字 http://asm.arc.nasa.gov/Gallery/images/generic/rover.jpg

显然 D* 在机器人领域非常有用，因为机器人车载传感器不断地重新评估边缘值。在我看来，这将使它非常“经过实战考验”。

同样，我发现另一份白皮书提到了在移动游戏中使用 D* Lite 算法。

我将通过说明我以前从未实现过 D*，只有 A* 来结束这个答案。由于复杂性显着增加，我会说 D*（或 D* Lite）只应在图表中有显着且频繁变化的情况下使用。您将您的情况描述为与此类似，所以我会说肯定选择 D* Lite。如果 NASA 使用它，您可以放心地打赌它已经过彻底调查。

Answer 2

我已经实现了 D* 和 A* 算法。所以，我建议你，如果你的地图没有动态障碍，你应该实现 A*。否则，实施 D*。主要原因是：在第一次搜索时，D* 计算地图中的所有节点，然后显示最短路径，而 A* 仅计算地图中目标和起点周围的有限区域。因此，它比 D* 快得多。在动态环境中，D* 比 A* 更快、更高效。因为在机器人前进的路上，如果它检测到一个新的障碍物，它只会更新意外障碍物周围的几个节点。同时，A* 将重新计算所有事物。