Search code examples
algorithmpath-findinga-star

A* algorithm - Start point


I am on a two-dimensional grid-maze where you can only move horizontally and vertically. The edge cost is 1 and I use the Manhattan distance to estimate the distance from a node to the target.

My question is whether or not it does make a difference if you start in your current node finding the way to your target or starting on the target node and finding your way back to your current node?


Solution

  • No it doesn't make any difference whether you work forward or backward. Keep in mind though that in practical applications, you often have many goal nodes but almost always a single start node. If you only want to reach one goal node, it's better to search forward from the start node.

    Also, note that A* will yield the optimal solution if using an admissible heuristic. There might be multiple solutions that are equally optimal, so searching backward rather than forward could lead you to a different, but just as good, solution.