What are the time and space complexities of D* and D* Lite? How to derive those?
Asked
Active
Viewed 687 times
2
-
similar question: https://stackoverflow.com/questions/2900718/where-can-i-find-information-on-the-d-or-d-lite-pathfinding-algorithm – Eziz Durdyyev Mar 27 '18 at 00:12
-
I am asking about the complexity and not the reference material – J.Dow Mar 28 '18 at 09:43
-
D* Lite runs like an A-star so for the first iteration it is O(n) in Time (where n is the total number of nodes in grid) in the worst case. For the path updates, it depends on the number of obstacles that have been updated and in the worst case can be much worse than A-star. Time Complexity doesn't make a lot of sense for these kind of heuristic search algorithms as in worst case a lot of them run to O(n). Eg. BFS, Dijkstra's, A-star even though A-star runs much faster than BFS. – yasht Nov 17 '19 at 06:06
-
For the space complexity, in the naive implementation all the nodes that have been searched need to be stored so again it is O(n) in worst case – yasht Nov 17 '19 at 06:07