Re:Show HN: Algoviz, Interactive a* Pathfinding Visualization
by nemetroid on Sunday January 12, 2020 @07:13AM
(#22025932)
Whether a greedy heuristic is faster or not is dependent on the structure of the graph. For the example in the article about mountains and grassland, it makes sense that such a heuristic would speed up the search, since the algorithm can't get stuck in dead-ends.
But in a problem where the algorithm can get stuck in dead-ends, it's possible to construct examples where the greedy heuristic is (much) slower than plain Manhattan distance. Here's an example:
xxx
xEx
x x
x x
x x
x x
Sxxxxxxxxxxxxxx x
x
xxxxxxxxxxxxxxxx
But in a problem where the algorithm can get stuck in dead-ends, it's possible to construct examples where the greedy heuristic is (much) slower than plain Manhattan distance. Here's an example: