A* and heuristics
**A\*** is a best-first search that uses path cost so far plus a **heuristic** guess of remaining cost—classic informed search.
What it is
A\* is a best-first search that uses path cost so far plus a heuristic guess of remaining cost—classic informed search.
Why it matters
Powers route planning intuition and many game/pathfinding systems. Teaches when shortcuts are safe.
How it works (plain)
Expand the most promising node by \(f=g+h\). If \(h\) never overestimates (admissible), A* can find optimal paths (with other standard conditions).
Everyday example
GPS-ish routing: distance traveled + straight-line estimate to destination.
Try it
On a grid, compare BFS vs a Manhattan-distance heuristic mentally for a short path.
Myths
- ⚠️ Myth: Any heuristic is fine.
- ✓ Reality: Bad heuristics lose optimality or wander.
Sources
- Course 06 search-and-planning
- Russell & Norvig AIMA; CS50 AI: https://cs50.harvard.edu/ai/ ↗