What BFS and DFS Have in Common
The comparison table at the end of Reading 3 highlighted the tradeoffs between breadth-first and depth-first search — memory use, path length guarantees, completeness. But buried in that table was a property both algorithms share, and it is worth pulling out and looking at directly:
Neither BFS nor DFS uses any knowledge about where the goal is.
BFS spreads outward in all directions simultaneously because it has no information about which direction is more likely to lead to the goal. It expands Dike, Hudson, Waverly, and Waterloo from Cedar Falls with equal enthusiasm, even though three of those four cities are clearly heading the wrong way. DFS picks one direction and follows it because it has no information to prefer any direction over another. If it happens to go toward Des Moines first, it will follow that path deep into the wrong part of the country before reconsidering.
This is not a flaw in the algorithms themselves — it is a consequence of designing them to work without any domain-specific knowledge. They are general purpose: the same algorithm works for the 8-puzzle, the maze, the navigation problem, and the Analysts and Hackers puzzle. But that generality comes at a cost. An algorithm that knows nothing about the problem it is solving cannot be smart about how it solves it.
The question is: can we do better? Can we give a search algorithm some information about the problem — not enough to solve it outright, but enough to make more intelligent choices about which paths to pursue?
The answer is yes. The mechanism is called a heuristic.
What a Human Does That BFS and DFS Cannot
Suppose you are standing in Cedar Falls and someone tells you to drive to Chicago. You glance at a map — or just recall that Chicago is to the east — and immediately start evaluating your options.
From Cedar Falls, you can go to four places:
- Dike, to the west
- Hudson, to the south
- Waverly, to the north
- Waterloo, to the east
You dismiss Dike, Hudson, and Waverly almost instantly. You do not check a timetable. You do not calculate exact distances. You do not look up road conditions. You just know, from the general position of Chicago relative to Cedar Falls, that heading west, south, or north is a bad idea when your destination is to the east. Waterloo is the obvious first step.
How do you know this? You are using a piece of geographic intuition: cities that are closer to the goal in a straight line are more likely to be on a good path toward the goal. Waterloo is east of Cedar Falls, and Chicago is east. Dike is west of Cedar Falls, and Chicago is east. Waterloo is the better choice.
This intuition is not a guarantee. It is possible to imagine a road network where the best route from Cedar Falls to Chicago goes north first before curving east. But as a general estimate, "head toward the goal" is almost always a good idea, and it lets you dismiss three of four options in a fraction of a second without doing any formal calculation.
That informal estimate — "this city feels closer to the goal" — is a heuristic. And it is exactly the kind of information we can give to a search algorithm.
What a Heuristic Is
The word heuristic comes from the Greek word for "to find" or "to discover." In everyday usage, a heuristic is a rule of thumb — a practical shortcut that usually works well, even if it cannot be proven to work in every case.
You use heuristics constantly. When you are running late and need to park, you do not check every parking spot in every lot before deciding where to go. You use rules of thumb: the lot closest to the building is usually full by this time of day, the overflow lot two blocks away usually has spaces, the street around the corner sometimes has a spot near the end. You act on those estimates without certainty. They might be wrong — the overflow lot might be full today, the street spot might be taken — but they are usually right enough to be useful, and they let you make a decision in seconds rather than spending twenty minutes on an exhaustive search.
In a search problem, a heuristic is a function that takes a state and produces an estimate of how "far" that state is from the goal. A state that appears to be close to the goal gets a low value. A state that appears to be far from the goal gets a high value. The search algorithm uses these values to decide which states to explore first — always preferring the states that look most promising.
The key word is estimate. A heuristic does not calculate the true distance to the goal — if it could do that, we would already have the solution. It approximates. It guesses intelligently. And that intelligent guessing, even when imperfect, can make an enormous difference in search efficiency.
Best-First Search: Letting the Heuristic Lead
Once we have a heuristic, we can use it to build a smarter search strategy called best-first search (also called heuristic search). The idea is straightforward: at each step, instead of expanding nodes in level order (BFS) or along a single deep path (DFS), always expand whichever unexplored node has the best (lowest) heuristic value — the one that appears to be closest to the goal.
Returning to Cedar Falls: at the start, the heuristic evaluates all four neighbors and estimates how far each is from Chicago. Waterloo, being to the east, gets a low value. Dike, Hudson, and Waverly, being in the wrong direction, get high values. Best-first search picks Waterloo. From Waterloo, it evaluates the next set of options: Independence and Cedar Rapids, both heading east, get lower values than backtracking toward Cedar Falls. The search keeps heading east, following the most promising node at each step.
The result is a search that looks much more like what a human would do: it heads generally toward the goal, ignoring obviously wrong directions, and only explores alternatives when the most promising path runs into trouble.
What Heuristics Look Like in Practice
The specific heuristic used depends on the problem. Here are two examples, one for each of our main problem types.
Navigation: Straight-Line Distance
For a navigation problem, the most natural heuristic is the straight-line distance from the current location to the goal. Straight-line distance (sometimes called "as the crow flies" distance) can be calculated instantly from coordinates. It is always an underestimate of the actual road distance, since roads curve, intersect, and sometimes require detours — but it captures the essential geographic fact that cities closer to the goal in a straight line are generally closer to the goal by road as well.
This is precisely the heuristic your GPS uses. When it is planning a route from Cedar Falls to Chicago, it is not checking every possible sequence of road segments. It is computing a straight-line estimate of distance to the destination for each candidate location and using that estimate to focus the search on roads that are heading in the right general direction.
The 8-Puzzle: Tiles Out of Place
For the 8-puzzle, straight-line distance does not apply — there are no coordinates, just tile arrangements. But we can design a heuristic that captures a similar idea: how far is the current arrangement from the goal arrangement?
One simple heuristic is to count the number of tiles that are currently in the wrong position. A state where seven of eight tiles are in the wrong position "feels" farther from the goal than a state where only two tiles are out of place. This count does not tell us exactly how many moves are needed — a tile that is one move away from its correct position and a tile that requires five moves both count as "one wrong tile" — but it gives the search algorithm a useful signal about which states are more promising than others.
A more refined heuristic for the 8-puzzle is to add up, for each tile, the number of moves it would need to reach its correct position if it could move freely (ignoring other tiles). This "total distance" estimate is still not exact — tiles block each other, so the actual number of moves is usually higher — but it is a better approximation than simply counting wrong tiles, and it consistently guides the search toward more productive states.
The practical impact is significant. A BFS or DFS of a scrambled 8-puzzle might explore thousands of states before finding the solution. The same puzzle, solved with a good heuristic, might require only a few dozen state expansions. The search is not faster because the computer is faster — it is faster because far fewer wrong paths are pursued.
Heuristics and the Cost Problem
Recall from Reading 1 that GPS navigation involves variable cost: different road segments have different lengths, speeds, and travel times. BFS, which counts transitions, cannot handle this well. DFS, which commits to one path without evaluating alternatives, cannot handle this well either.
Heuristic search handles variable cost naturally. The heuristic estimates remaining cost to the goal. The search algorithm can also track the actual cost accumulated so far along the current path. Combining both — actual cost so far plus estimated cost to go — gives a much better picture of which paths are likely to be cheap overall.
This is the core idea behind an algorithm called A* (pronounced "A-star"), which is what most real navigation apps actually use. A* chooses which node to expand next based on the sum of two values: the actual cost to reach the current node, and the heuristic estimate of the cost from the current node to the goal. This combination prevents a common failure of pure best-first search: blindly chasing a node that looks close to the goal but was reached by an extremely expensive path.
Consider a concrete example. Suppose there is a direct road from Cedar Falls to a city that is geographically very close to Chicago — but the road is a narrow county highway with a 30 mph speed limit and it takes four hours. Meanwhile, the I-380/I-80 route through Cedar Rapids and Iowa City is geographically farther from Chicago for most of the journey, but it uses high-speed interstates and takes three hours. Pure best-first search, using only geographic distance as its heuristic, might prefer the county highway because it "looks closer" at every step. A*, which also considers the time already spent, would recognize that the county highway is costing too much and prefer the interstate route.
A* is one of the most important algorithms in computer science and is worth knowing by name, even if the details of how it balances actual and estimated cost are beyond what we need here.
Heuristics Are Not Magic
It would be easy to come away from this reading with the impression that heuristics solve everything. They do not. Several important qualifications are worth making explicit.
Heuristics can be wrong. An estimate is not a guarantee. A heuristic that says "Waterloo is closer to Chicago than Waverly" is right in this case, but in a different road network it might be wrong. Best-first search following a heuristic does not guarantee finding the shortest path — it might make a poor choice at some junction if the heuristic gives a misleading estimate there. The tradeoff is speed (follow the best-looking option) versus certainty (verify that you found the best option). A* recovers some of this certainty by combining the heuristic with actual cost tracking, but even A* depends on the heuristic not being too badly wrong.
Designing a good heuristic is real intellectual work. For simple problems like the 8-puzzle and navigation, natural heuristics suggest themselves. For harder problems — scheduling, planning, game-playing, optimization — designing a heuristic that is both fast to compute and accurate enough to be useful is a significant challenge. Researchers spend considerable effort developing and evaluating heuristics for specific problem domains. The quality of the heuristic directly determines the efficiency of the search.
Some problems resist heuristics. A heuristic requires some knowledge about what "closer to the goal" means for the problem at hand. For some problems, that knowledge is hard to come by. If every state looks roughly equally distant from the goal, a heuristic cannot help much, and the search falls back on something closer to BFS or DFS.
The power of heuristics is not that they are always right. It is that they are right often enough, and cheap enough to compute, that following them produces much better searches than ignoring them entirely. The art of AI search is not finding a perfect heuristic — it is finding one good enough to matter.
Looking Back Across the Four Readings
This is a good moment to look back at the arc of Topic 6b and see how the pieces fit together.
Reading 1 established the framework: any goal-directed problem can be described as a search problem with four ingredients — start state, goal state, transitions, and cost. Solving the problem means finding a path through the state space from start to goal, minimizing cost along the way.
Reading 2 introduced breadth-first search: explore level by level, guarantee the fewest-transition solution, but pay a steep memory price and waste effort on obviously wrong directions.
Reading 3 introduced depth-first search: commit to one path at a time, use far less memory, but give up the shortest-path guarantee and risk wandering badly when the first path chosen happens to be wrong.
Reading 4: this reading — introduced heuristics: inject domain knowledge into the search to give it a sense of direction, dramatically reducing the number of states explored while accepting that the search might occasionally make a suboptimal choice.
None of these strategies is universally best. BFS is the right tool when cost is uniform and memory is not a constraint. DFS is useful when memory is limited and any solution will do. Heuristic search is essential when the state space is large and domain knowledge is available. Real AI systems often combine elements of all three, choosing and adapting strategies based on the structure of the specific problem they face.
What unifies all of them is the state space framework from Reading 1. Once you can describe a problem as a search problem — start state, goal state, transitions, cost — you have access to the entire toolkit of search strategies that computer scientists have developed over decades. That is the power of the framework: not that it solves any particular problem, but that it reduces an enormous variety of different problems to the same underlying challenge, making the solutions transferable.