Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
A* search combines uniform-cost search with greedy search:
- UCS uses , the cost to reach (past experience): optimal and complete, but can be very inefficient
- greedy uses , the estimated cost from to the goal (future prediction): neither optimal nor complete, but cuts the search space a lot
Evaluation Function
is the estimated total cost of the cheapest path through to the goal (the "whole life" cost). Special cases: gives greedy search, gives UCS.
function A*-SEARCH(problem) returns solution:
return BEST-FIRST-SEARCH(problem, g + h)If two frontier nodes tie on , a common rule is to expand the one with lower (closer to the goal) or lower , depending on what is preferred.
Example: Arad to Bucharest
Using straight line distance as :
| Step | Expand | New frontier entries |
|---|---|---|
| a | (start) | Arad |
| b | Arad (366) | Sibiu , Timisoara , Zerind |
| c | Sibiu (393) | Rimnicu Vilcea , Fagaras , Arad , Oradea |
| d | Rimnicu Vilcea (413) | Pitesti , Craiova , Sibiu |
| e | Fagaras (415) | Bucharest , Sibiu |
| f | Pitesti (415) | Bucharest , Craiova , Rimnicu Vilcea |
| g | Bucharest (418) | goal |
A* does not stop at the first Bucharest (450) because it is only on the frontier. Pitesti at 415 is still cheaper, and expanding it finds Bucharest at 418, the optimal route Arad, Sibiu, Rimnicu Vilcea, Pitesti, Bucharest.
Manhattan Grid Example
On a city grid with the Manhattan distance as , greedy rushes straight at the goal along whatever street looks closest, UCS spreads out evenly in all directions, and A* keeps constant along the true shortest paths (all 6s on the good street, 8s and 10s on detours), so it expands only nodes on the shortest route.
Properties
| Criterion | A* |
|---|---|
| Complete | Yes |
| Time | exponential in solution length |
| Space | exponential, all generated nodes kept in memory |
| Optimal | Yes, with an admissible heuristic |
With a good heuristic the savings over uninformed search are still large. Compare its frontier rule with UCS in Breadth-First and Uniform-Cost Search.