A* Search
Best-first search ordered by g + h, distance so far plus an admissible estimate of what is left. Optimal and far more focused than BFS.
Grid Search and A*: A* leans toward the goal
Expand (0,0), g = 0, f = 9. New neighbours (1,0), (0,1) get g = 1 and f = 9, 9. Frontier: 2.
Cost
- Best
- O(E)
- Average
- depends on heuristic
- Worst
- O(E log V)
- Space
- O(V)
Worst case equals Dijkstra with a zero heuristic.