A* Algorithm

 A* algorithm,

A^* search is a combination of lowest-cost-first and best-first searches that considers both path cost and heuristic information in its selection of which path to expand. For each path on the frontier, A^* uses an estimate of the total path cost from a start node to a goal node constrained to start along that path. It uses cost(p), the cost of the path found, as well as the heuristic function h(p), the estimated path cost from the end of p to the goal.

For any path p on the frontier, define f(p)=cost(p)+h(p). This is an estimate of the total path cost to follow path p then go to a goal node.

n  Evaluation function f(n) = g(n) + h(n)

n  g(n) = cost so far to reach n

n  h(n) = estimated cost from n to goal

n  f(n) = estimated total cost of path through n to goal

n  Best First search has f(n)=h(n)

n  Uniform Cost search has f(n)=g(n)

Example :: A* Algorithm 
Romania with step costs in km

Open List:

Arad

We start with our initial state Arad.  We make a node and add it to the open list.  Since it’s the only thing on the open list, we expand the node.

Think of the open list as a priority queue (or heap) that sorts the nodes inside of it according to their   g()+h()   score.

Open List: 

Sibiu

Timisoara

Zerind

We add the three nodes we found to the open list. 

We sort them according to the    g()+h()    calculation.

Open List:

Rimricu Vicea

Fagaras

Timisoara

Zerind

Arad                     (We’ve been to Arad before.  Don’t list it again on the open list.)

Oradea 

When we expand Sibiu, we run into Arad again.  But we’ve already expanded this node once; so, we don’t add it to the open list again.

Open List:

Rimricu Vicea

Fagaras

Timisoara

Zerind

Oradea

We see that Rimricu Vicea is at the top of the open list; so, it’s the next node we will expand.

Open List:

Fagaras

Pitesti

Timisoara

Zerind

Craiova

Sibiu

Oradea

When we expand Rimricu Vicea, we run into Sibiu again. 

But we’ve already expanded this node once; so, we don’t add it to the open list again.

Open List:

Fagaras

Pitesti

Timisoara

Zerind

Craiova

Oradea

Fagaras will be the next node we should expand – it’s at the top of the sorted open list.

Open List:

Pitesti

Timisoara

Zerind

Bucharest

Craiova

Sibiu

Oradea

When we expand Fagaras, we find Sibiu again.  We don’t add it to the open list.

We also find Bucharest, but we’re not done.  The algorithm doesn’t end until we “expand” the goal node – it has to be at the top of the open list.

Open List:

Pitesti

Timisoara

Zerind

Bucharest

Craiova

Oradea

It looks like Pitesti is the next node we should expand.

Open List:

Bucharest

Timisoara

Zerind

Craiova

Rimricu Vicea

Oradea

We just found a better value for Bucharest; so, it got moved higher in the list.  We also found a worse value for Craiova – we just ignore this.

And of course, we ran into Rimricu Vicea again.  Since it’s already been expanded once, we don’t re-add it to the Open List. 

Open List:

Bucharest

Timisoara

Zerind

Craiova

Oradea 

Now it looks like Bucharest is at the top of the open list…

Open List:

Bucharest

Timisoara

Zerind

Craiova

Oradea 

Now we “expand” the node for Bucharest. 

We’re done!   (And we know the path that we’ve found is optimal.)