News for hackers. Stuff that matters.
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

There are no comments on this comment yet.