Chapter 12: A* Algorithm
The introduction frames A* as a way to find the cheapest route to a specific destination while using an estimate of the remaining distance to guide the search.
After this chapter you will be able to
- Goal Directed Search Advantage. Explain why searching outward without regard to the destination can waste effort, and how A* uses an estimate of the distance left to steer toward the goal while seeking the cheapest path.
- Goal Directed Search. Explain why A* uses an estimate of remaining cost rather than exploring only by distance traveled, as Dijkstra does in this section's comparison.
- Admissible Heuristic Bounds. Explain what h(n) estimates, why an admissible heuristic must not overestimate, and how the section's distance examples fit that rule.
- Combined Path Cost Priority. Describe the roles of g(n), h(n), and f(n), and explain why A* does not choose nodes using h(n) alone.
- Cheaper Route Updates. Trace how A* compares a newly found route to a neighbor with the route already recorded, and describe what it changes when the new route is cheaper.
- Goal Popping Stop Rule. Explain why discovering the goal does not end A*, and describe how the example obtains its final route.
- Road routing and ALT. Explain how A*’s original robot path-planning problem relates to road navigation, and why large road networks use an A*-style improvement such as ALT rather than textbook A* unchanged.
- Game pathfinding constraints. Describe why game maps suit A* and how a heuristic and path cost work together when obstacles block a character’s direct route.
- Sliding-puzzle search benchmark. Explain why the 15-puzzle is a useful search benchmark and what the Manhattan-distance heuristic contributes when searching its enormous state space.
- Worst-Case Time Bound. Explain why A* can perform no better than Dijkstra’s algorithm in the worst case, and distinguish its worst-case time bound from the practical benefit of a useful heuristic.
- Graph and Heuristic Fit. Describe how graph density and heuristic quality affect A*’s practical advantage over Dijkstra’s algorithm.
- Memory Limits and IDA. Explain why A* can run out of memory on large searches and how IDA* trades repeated work for lower memory use.
- Speed Versus Optimal Cost. Justify choosing weighted A* or greedy best-first search when a fast, good-enough path matters more than a guaranteed lowest-cost path.
What it builds on
- What is a clique? (chapter 11) · Introduces cliques as groups of mutually connected nodes.
- All-pairs shortest path (APSP) (chapter 9) · Covers Floyd-Warshall’s all-pairs shortest-path problem.
Section by section
Introduction
The introduction frames A* as a way to find the cheapest route to a specific destination while using an estimate of the remaining distance to guide the search.
- Cheapest Route Search Question: Distinguish the start-to-destination cheapest-path question in this chapter from the previous chapter’s search for maximal cliques.
Why it matters: It identifies the problem A* is meant to solve before considering how it searches. - Goal Directed Search Advantage: Explain why searching outward without regard to the destination can waste effort, and how A* uses an estimate of the distance left to steer toward the goal while seeking the cheapest path.
Why it matters: It captures why A* can focus a cheapest-path search when only one destination matters.
Key terms: start point, destination, cheapest, maximal clique, A*, Dijkstra's algorithm, Floyd-Warshall algorithm, educated guess, cheapest path
12.1 What is an informed search algorithm?
This section explains how A* combines a goal-directed heuristic with actual path costs, then traces how it updates routes and decides when to stop.
- Goal Directed Search: Explain why A* uses an estimate of remaining cost rather than exploring only by distance traveled, as Dijkstra does in this section's comparison.
Why it matters: The goal estimate explains why A* can focus its search toward a particular destination. - Admissible Heuristic Bounds: Explain what h(n) estimates, why an admissible heuristic must not overestimate, and how the section's distance examples fit that rule.
Why it matters: A useful direction estimate must not make A* overlook a truly shorter route. - Combined Path Cost Priority: Describe the roles of g(n), h(n), and f(n), and explain why A* does not choose nodes using h(n) alone.
Why it matters: The combined score keeps a promising-looking direction from hiding an expensive route so far. - Cheaper Route Updates: Trace how A* compares a newly found route to a neighbor with the route already recorded, and describe what it changes when the new route is cheaper.
Why it matters: Comparing routes prevents a worse discovery from replacing a cheaper path and lets a later improvement take effect. - Goal Popping Stop Rule: Explain why discovering the goal does not end A*, and describe how the example obtains its final route.
Why it matters: Stopping on first discovery would have returned the worse route in the section's trace.
Key terms: informed search, Dijkstra, heuristic, h(n), admissible, straight-line distance, Manhattan Distance, g(n), f(n), greedy best-first search
12.2 Real-world applications
The section shows how A*’s heuristic-guided search is applied to road routing, game pathfinding, and sliding-tile puzzles.
- Road routing and ALT: Explain how A*’s original robot path-planning problem relates to road navigation, and why large road networks use an A*-style improvement such as ALT rather than textbook A* unchanged.
Why it matters: It shows how the same A* idea can be adapted for road networks too large for textbook A* to handle efficiently. - Game pathfinding constraints: Describe why game maps suit A* and how a heuristic and path cost work together when obstacles block a character’s direct route.
Why it matters: Game pathfinding makes clear why searching toward the goal is useful but cannot ignore the cost of routes around obstacles. - Sliding-puzzle search benchmark: Explain why the 15-puzzle is a useful search benchmark and what the Manhattan-distance heuristic contributes when searching its enormous state space.
Why it matters: The puzzle makes the value of heuristic guidance visible through the number of states a search has to examine.
Key terms: Shakey, ALT, landmarks, triangle inequality, admissible heuristic, weighted graph, grid, navigation mesh, Manhattan distance, g(n)
12.3 Key insights
This section explains when A* is efficient, where its time and memory limits arise, and when alternative searches better fit the problem.
- Worst-Case Time Bound: Explain why A* can perform no better than Dijkstra’s algorithm in the worst case, and distinguish its worst-case time bound from the practical benefit of a useful heuristic.
Why it matters: A heuristic can make a search much faster in practice without changing its worst-case guarantee. - Graph and Heuristic Fit: Describe how graph density and heuristic quality affect A*’s practical advantage over Dijkstra’s algorithm.
Why it matters: The graph and the quality of the available heuristic determine whether A*’s extra bookkeeping pays off. - Memory Limits and IDA: Explain why A* can run out of memory on large searches and how IDA* trades repeated work for lower memory use.
Why it matters: A search can be feasible in time yet fail because its discovered nodes do not fit in memory. - Speed Versus Optimal Cost: Justify choosing weighted A* or greedy best-first search when a fast, good-enough path matters more than a guaranteed lowest-cost path.
Why it matters: The best search choice depends on whether a minimum-cost path is worth the extra exploration.
Key terms: A*, Dijkstra’s algorithm, heuristic, binary priority queue, O((V+E)logV), graph density, sparse graph, dense graph, tight heuristic, ALT-style landmarks
12.4 Summary
12.5 References
This section lists an A* code implementation and references for further reading.
Concepts explained in this chapter
- A* algorithmA* is a best-first search algorithm that prioritizes paths using their cost so far and a heuristic estimate of the remaining cost.
- heuristicAn estimate used to guide choices in a search or optimization problem.
- informed searchInformed search is a search strategy that uses an estimate of remaining cost to guide which candidate to explore next.
- greedy best-first searchGreedy best-first search expands the candidate with the most promising heuristic estimate without accounting for the cost already incurred.
- lower boundA lower bound is a limit that a quantity does not asymptotically fall below.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.
