论路径寻找：为外行人详细讲解D*算法
我希望处理的大型网络（小世界图类型）本质上是动态的，新节点经常添加和删除。 想必在这种动态环境中使用 D* 而不是 A* 是检测路径的更好方法吗？
D*有多坚固？ 它有任何现实世界的经验吗？ 就像加密算法一样 - D* 是否经过大量同行评审和测试而变得更加坚固？ 你会用 D* 来解决这个问题吗？
The large network (of small world graph type) I wish to deal with is dynamic in nature, new nodes are added and subtracted frequently. Presumably using D* over A* would be a better way to detect paths in this dynamic environment?
How solid is D*? has it had any real world experience? like a cryptographic algorithm - is D* hardened by lots of peer review and testing? Would you use D* for this problem?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我已经实现了 D* 和 A* 算法。 所以，我建议你，如果你的地图没有动态障碍物，你应该实现A*。 否则，实施 D*。 主要原因是：
在第一次搜索时，D* 计算地图中的所有节点，然后显示最短路径，而 A* 只计算地图中目标点和起点周围的有限区域。 因此，它比 D* 快得多。
在动态环境中，D*比A*更快、更高效。 因为在机器人行驶的过程中，如果它检测到新的障碍物，它只会更新意外障碍物周围的几个节点。 同时，A*会重新计算所有的事情。
I have implemented both D* and A* algorithm. So, I advice you that, if your map has no dynamic obstacles, you should implement A*. Else, implement D*. For the main reason is:
At the first search, D* calculates all nodes in the map, then shows you the shortest path, while A* only calculates a limited area around goal and start points in the map. So, it is much faster than D*.
In dynamic environment, D* is faster and more efficient than A*. Because on the way robot goes, if it detects a new obstacle, it only updates a few nodes around the unexpected obstacle. While, A* will calculates again all things.
据我了解，第一次运行 D* 时，它会找到与 A* 相同的路径，并且运行时间几乎相同。 然而，当节点更改其边缘值或添加节点时，A* 会重新计算所有路径，而 D* 只是在第二次重新计算不一致的节点，而不是整个路径。
Anthony Stentz 的 D* 算法（原始白皮书此处）在很大程度上已被其作品的衍生品所弃用。 D* Lite 和 LPA* 是最常见的，并且更容易编码/实现。
就现实世界的经验而言，来自 NASA 喷气推进实验室的 Joseph Carsten 和 Art Rankin 在火星漫游者“勇气号”和“机遇号”上安装了使用 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。 如果美国宇航局使用它，你可以放心地打赌它已经被彻底调查过。
As I understand, the first time you run D* it finds the same path as A* with nearly the same runtime. However, when a node changes it's edge value or nodes are added A* recomputes ALL of the path while D* simply recomputes the inconsistent nodes the second time around rather than the whole thing.
Anthony Stentz's D* algorithm (original whitepaper here) has largely been deprecated by derivatives of his work. D* Lite and LPA* are the most commonly found and are much easier to code/implement.
As far as real world experience, Joseph Carsten and Art Rankin from NASA's Jet Propulsion Laboratory installed a version of Field D* using elements of D* Lite on the mars rovers "Spirit" and "Opportunity" (slideshow of rovers using D* here). In Feburary 2007 it was used to fully navigate the mars rover autonomously.
alt text http://asm.arc.nasa.gov/Gallery/images/generic/rover.jpg
Apparently D* is really useful in the robotics domain because the robots on-board sensors are constantly re-evaluating edge values. That would make it pretty "battle tested" in my own opinion.
Similarly, I found another whitepaper that mentions the use of the D* Lite algorithm in Mobile Gaming.
I'll end this answer by stating that I've never implemented D* before, only A*. Because of the significant increase in complexity I would say that D* (or D* Lite) should only be used in cases where there is a significant and frequent changes in the graph. You described your situation as being similar to that so I would say definately go for D* Lite. If NASA uses it you could safely bet it has been thoroughly investigated.