关于路径查找：对D *算法的外行人的详细描述

Question

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

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

Answer 1

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

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

就现实世界的经验而言，来自美国宇航局喷气推进实验室的约瑟夫卡斯滕和艺术兰金在火星探测器上使用D * Lite的元素安装了一个Field D *版本的“精神”。和“机会” （使用D * 这里）。在2007年2月，它被用来自动完全驾驶火星车。

alt text http://asm.arc.nasa.gov/廊/图像/通用/ rover.jpg

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

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

我将结束这个回答，说明我之前从未实施过D *，只有A *。由于复杂性的显着增加，我会说D *（或D * Lite）仅应用于图中存在显着且频繁变化的情况。你描述了你的情况类似于那样我肯定会说D * Lite。如果美国宇航局使用它，你可以安全地打赌它已被彻底调查过。

Answer 2

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