[Solved]: Why choose D* over Dijkstra?

Problem Detail: 

I understand the basis of A* as being a derivative of Dijkstra, however, I recently found out about D*. From Wikipedia, I can understand the algorithm. What I do not understand is why I would use D* over Dijkstra. To my understanding, Dijkstra gives a best path and D* works backwards from the end goal, but unlike A* it seems to do many calculations, so it doesn't seem as efficient.

Asked By : user1938107

Answered By : Juho

The main reason for choosing D* is that it is incremental. Basically, when your initial route gets blocked, an incremental search algorithm is able to take advantage of the previous calculations. Dijkstra doesn't do this; it needs to recompute everything from scratch. Such an incremental approach is often used in robotics, navigation, and planning.

This is the short answer. For much more, I think you would be interested in How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22284

3.2K people like this

 Download Related Notes/Documents