Reputation: 2038
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?
Upvotes: 1
Views: 292
Reputation: 12527
It makes a difference for each particular maze (assuming there are some blocks making it a maze) and details of the algorithm, but neither is consistently better since you can always swap starting and target.
To show that it matters, consider a simple maze with a big L-shape block as follows (extending further upwards)
|
|
| a
| | |
|
|---------
b
From a it seems you will traverse the entire square to the left. From b you will go straight right, then up, and one step to the left
Upvotes: 0
Reputation: 4595
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.
Upvotes: 1