CODEWITHSUNDEEP
algorithmpath-findinga-star
Yamahari
Yamahari

Reputation: 2038

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?

Upvotes: 1

Views: 292

Answers (2)

Hans Olsson
Hans Olsson

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

francoisr
francoisr

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

Related Questions