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

我希望处理的大型网络(小世界图形类型)本质上是动态的,经常添加和减去新节点.大概在A*上使用D*是检测这个动态环境中路径的更好方法吗？

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

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

安东尼Stentz的d*算法(原白皮书这里)在很大程度上是由他的工作的衍生物弃用.D*Lite和LPA*是最常见的,并且更容易编码/实现.

至于现实世界的经验,约瑟夫·卡斯滕和艺术兰从美国航空航天局喷气推进实验室的安装版本字段的d*使用的火星探测器"勇气"号和"机遇" d*精简版的元素(使用d流浪者的幻灯片*这里) .在2007年2月,它被用来自动完全驾驶火星车.

alt text http://asm.arc.nasa.gov/Gallery/images/generic/rover.jpg

显然D*在机器人领域非常有用,因为机器人车载传感器不断重新评估边缘值.这将使我在自己的观点中进行"战斗测试".

同样,我发现另一篇白皮书提到在移动游戏中使用D*Lite算法.

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