Chapter 02 · Section II · 14 min read
Solving problems with AI
How heuristics let a system skip exploring most of the search space — and where they go wrong.
A blind search through every possible route from Thamel to Bhaktapur would finish, eventually, but not in time for your daal-bhaat. The trick that makes search useful in practice has a single word for it: heuristic.
A heuristic is a quick, cheap, often-wrong guess about how far the goal is. The algorithm uses the guess to decide what to explore next. Good heuristics make impossible problems solvable. Bad ones lead you confidently down the wrong road.
The straight-line heuristic
Pull out a map of the valley. From Thamel, draw a straight line east to Bhaktapur. The length of that line — the crow-flies distance — is a heuristic estimate of how far you still have to travel.
It is not the actual distance. The actual distance is longer; the road bends, climbs, and detours around the airport. But the straight-line distance is a useful guess: any junction whose straight-line distance is smaller is, probably, closer to Bhaktapur in road distance too.
That word — probably — is doing all the work. The heuristic is allowed to be wrong. It just needs to be wrong less often than a random guess.
A* in one paragraph
The most famous heuristic-driven search algorithm is called A* (pronounced “A-star”). At every step, A* asks: which junction should I explore next? The answer is the junction that minimises this sum:
(distance walked so far) + (heuristic estimate of distance remaining)
That is the entire idea. It combines what you actually know — how far you have walked — with what you guess — how much further you have to go. If the heuristic is good, A* finds the optimal route while exploring only a small fraction of the map. If the heuristic is perfect, A* walks straight to the goal. If the heuristic is useless, A* degrades to a slow form of BFS.
Every navigation app you have ever used — Google Maps, Pathao, baato — is running A* or a refinement of it.
Worked example: Thamel to Bhaktapur
Let us walk through it informally. From Thamel, A* looks at the neighbouring junctions — say, three of them: Lainchaur (north), Naxal (east), and Chhetrapati (south).
- Lainchaur: 200m walked, straight-line distance to Bhaktapur 13.0 km. Total estimate: 13.2 km.
- Naxal: 250m walked, straight-line distance to Bhaktapur 12.5 km. Total estimate: 12.75 km.
- Chhetrapati: 300m walked, straight-line distance to Bhaktapur 13.4 km. Total estimate: 13.7 km.
Naxal wins, so A* explores Naxal’s neighbours next. The process repeats. Each step, the algorithm chases the lowest-total-estimate path. The straight-line distance shrinks as we move east; junctions to the south or west get bigger estimates and are quietly dropped.
A* never explores Lainchaur, because Lainchaur is in the wrong direction. That is the whole win. A blind BFS would have explored Lainchaur thoroughly before noticing it was wasted effort.
Where heuristics go wrong
A heuristic can be wrong in two ways, and they have very different consequences.
Optimistic (under-estimating distance). The heuristic claims the goal is closer than it really is. This is actually safe: A* will still find the optimal route, it just explores more junctions than necessary along the way. Straight-line distance is optimistic — the road is always at least as long as the crow-flies line.
Pessimistic (over-estimating distance). The heuristic claims the goal is further than it really is. This is dangerous: A* can convince itself the optimal route is hopeless and pick a worse one. The algorithm will still return an answer; it just won’t be the best one.
For navigation, optimistic heuristics are easy to design (straight-line distance is one). For other problems — solving a Rubik’s cube, scheduling a school timetable — designing a heuristic that is both informative and provably optimistic is a research career.
When the world isn’t a road map
A* doesn’t care that you drew it on a map. It works for any problem that can be expressed in states, actions, goals, and costs. Some real ones:
- Aircraft routing. States are points in 3D airspace; actions are heading changes; cost is fuel; heuristic is great-circle distance to the destination airport.
- Robot motion planning. A factory robot in Birgunj needs to move from one position to another without hitting anything. States are joint angles. Actions are small motions. Heuristic is straight-line distance in joint space.
- Software theorem proving. States are partially-completed proofs; actions are inference steps; the heuristic is how close the partial proof looks to a known finished one.
The pattern repeats. Define the four words. Find a sensible heuristic. Run A*. Done.
The limits
A* is powerful, but it is not magic. Two failure modes are worth knowing.
-
The state space is too big to fit in memory. Chess has more states than atoms in the observable universe. A* cannot store a meaningful fraction of them. Different algorithms — Monte Carlo Tree Search, deep reinforcement learning — were invented for this regime.
-
The cost function changes mid-search. A Pathao route planned at 5:55pm becomes invalid when an accident closes Maitighar at 6:01. Real systems re-plan continuously, every few seconds, throwing away the old answer and starting over.
These limits do not make A* obsolete. They tell us when to reach for it and when to reach for something else. Both halves of that judgement are part of being literate in AI.
Check your understanding
Quick check
—A heuristic in a search algorithm provides:
What comes next
We’ve used heuristics to turn a hopeless search into a tractable one. The next section turns up the difficulty: searching when there is an opponent who is actively trying to make you lose. Welcome to game-playing AI.