chapter twelve
12 A* Algorithm
This chapter covers
- Guiding a graph search with an educated guess rather than searching blindly
- Balancing the cost already paid against the estimated cost still ahead
- Analyzing time and space complexity, where A* memory becomes a bottleneck
In the previous chapter, we worked through the Bron–Kerbosch algorithm, which found every maximal clique in a graph by growing a group, backing out when it couldn't grow any further, and never revisiting ground it had already covered. That was fundamentally a clustering question, where nodes are mutually connected to each other. This chapter asks a different kind of question, one closer to where we started with Push–Relabel, given a start point and a destination, what's the cheapest way to get from one to the other?