Lesson 103
A* Search
Heuristic Pathfinding · f = g + h
1:00How A* combines real cost (g) and a heuristic estimate (h) into f = g + h to find the shortest path faster than Dijkstra by steering the search toward the goal.
By the end, you can
- Explain what a heuristic is and compute Manhattan distance for any grid cell.
- Apply the formula f = g + h to assign a score to any node given g and h.
- Trace A* expansion on a small grid, selecting the correct node to pop at each step.
- Describe the roles of the open set and the closed set in A*.
- Place A* on the Dijkstra ↔ A* ↔ greedy spectrum and explain what changes as h varies.
- Define admissibility and explain why it guarantees optimality.
- Define consistency and explain what additional guarantee it provides over admissibility alone.
- Identify the three common A* pitfalls: inadmissible h, missing closed set, and dropping g.
Up next in Searching & Sorting
