A-ghastly name-*
Actually the name is just A*
The Total distance heuristic has a guarantee
- 1. heuristic score is guaranteed lower bound on true path cost via the current state
- 2. heuristic score of solution is the true cost of solution
A* = Best First + heuristic with this guarantee
A* guarantees that first solution found is optimal
Helpful because we can stop searching immediately
- otherwise must continue to find possible better solutions
- e.g. in Depth First for 8s puzzle.