From Puzzle to Strategy
When you worked through the Analysts and Hackers puzzle, you were already doing a form of search — moving from the start state (331) toward the goal state (000), applying transitions one at a time and trying to find a sequence that worked. You probably did not do this randomly. You tried some moves, got stuck, backed up, and tried something else.
That informal process is exactly the problem a search algorithm has to solve, but systematically and at scale. Reading 1 established that any such problem can be described with four ingredients: start state, goal state, transitions, and cost. The question is: in what order do we explore the available transitions? That choice is the search strategy, and it matters enormously.
The first and most intuitive strategy is breadth-first search.
Building a Search Tree
As a search algorithm explores a state space, it keeps track of what it has found in a data structure called a search tree. The search tree is not the same as the state space — it is the portion of the state space that has actually been visited so far. It grows as the search proceeds.
The search tree has a specific structure:
- The root node is the start state.
- The children of any node are the states reachable from that node by applying a single transition.
- Every path from the root down to a node records the sequence of transitions taken to reach that node's state.
- When a node is the goal state, the algorithm walks back up the tree from that node to the root, reading off the solution path.
The key question is which nodes to expand next. Different answers to that question produce different search strategies.
Breadth-First Search
Breadth-first search (BFS) explores the search tree one complete level at a time. It visits every state that is one transition from the start before visiting any state that is two transitions away, visits every two-transition state before any three-transition state, and so on.
A useful image: BFS spreads outward from the start state like a drop of dye falling into still water. The dye does not race down one channel — it expands in all directions simultaneously, reaching everything close to the source before reaching anything far away.
The procedure is straightforward:
- Add the start state as the root of the search tree.
- Generate all children of the root (every state reachable in one transition) and add them as Level 1.
- For each Level 1 node in order, generate its children and add them as Level 2.
- Continue level by level until the goal state is found.
BFS has one important guarantee: if a path to the goal exists, BFS will find it. And because it explores all shorter paths before any longer ones, it always finds the path that uses the fewest transitions.
Fewest transitions = lowest cost only when cost is uniform. BFS finds the path with the fewest steps, which is the same as the cheapest path only when every transition costs the same. In the Analysts and Hackers puzzle, every boat crossing costs 1, so the fewest-move solution is always the best solution. In a GPS problem where road segments have different lengths or travel times, the fewest-hop path and the lowest-cost path can be very different things. We will return to this distinction in Reading 4.
Worked Example: Cedar Falls to Chicago
Let us trace BFS through the Cedar Falls to Chicago navigation problem from Reading 1. Recall the two routes and their structure:
| From | Direct connections to |
|---|---|
| Cedar Falls | Dike (W), Hudson (S), Waverly (N), Waterloo (E) |
| Waterloo | Cedar Falls, Independence (US 20 east), Cedar Rapids (I-380 south) |
| Independence | Waterloo, Manchester |
| Cedar Rapids | Waterloo, Iowa City |
| Manchester | Independence, Dubuque |
| Iowa City | Cedar Rapids, Davenport |
| Dubuque | Manchester, Galena |
| Davenport | Iowa City, Chicago |
| Galena | Dubuque, Freeport |
| Freeport | Galena, Rockford |
| Rockford | Freeport, Chicago |
Start state: Cedar Falls Goal state: Chicago
Level 0 — The Root
The search tree begins with a single node: Cedar Falls.
Level 1 — One Transition Away
From Cedar Falls, four cities are reachable: Dike, Hudson, Waverly, and Waterloo. BFS adds all four. Is any of them Chicago? No. Continue.
Notice that a human navigating this problem would immediately focus on Waterloo and ignore the other three — Dike, Hudson, and Waverly are in the wrong direction. BFS does not know that. It treats all four equally and adds them all. This is one of BFS's limitations: without any knowledge of where the goal is, it cannot prioritize.
Level 2 — Two Transitions Away
BFS expands each Level 1 node in order. Dike, Hudson, and Waverly all dead-end quickly (they only connect back toward Cedar Falls and to small towns that do not lead to Chicago in this graph). From Waterloo, two useful paths open up: Independence (on US 20 east) and Cedar Rapids (on I-380 south). BFS adds both.
Level 3 and Beyond
BFS continues expanding level by level. From Independence comes Manchester. From Cedar Rapids comes Iowa City. From Manchester comes Dubuque. From Iowa City comes Davenport — and Davenport connects directly to Chicago. Meanwhile, from Dubuque comes Galena, then Freeport, then Rockford, which also connects to Chicago.
BFS finds Chicago first via Davenport, at 5 hops from Cedar Falls (CF → Waterloo → Cedar Rapids → Iowa City → Davenport → Chicago). The US 20 route through Dubuque and Rockford reaches Chicago at 7 hops and is found later.
BFS found the route with the fewest stops — but is it the best route? The I-380/I-80 corridor (5 hops, ~330 miles) has fewer intermediate cities than the US 20 corridor (7 hops, ~315 miles) — but it is actually longer in miles. If your goal is to minimize miles driven rather than cities visited, BFS gave you the wrong answer. This is not a flaw in BFS; it is a limitation of uniform-cost thinking applied to a variable-cost problem. BFS is the right tool when all transitions cost the same. When they do not, a different approach is needed.
The Cost of Going Wide
BFS is correct and complete — if a solution exists, it will find it, and it will find the version with the fewest transitions. For small problems like the route example, it works well.
The problem is memory. BFS must hold every node at every level in memory before moving to the next level. In the route example, Level 2 had two useful nodes. A real GPS network with millions of intersections might have millions of nodes at Level 2, tens of millions at Level 3, and so on. The memory requirement grows exponentially with the depth of the solution.
Consider the 8-puzzle. Each state has two to four possible moves. At Level 1: up to 4 nodes. At Level 2: up to 16. At Level 10: over a million. The solution to a randomly scrambled 8-puzzle might require 20 or more moves, meaning BFS would need to hold an astronomical number of nodes in memory before finding it. This exponential growth is called the combinatorial explosion, and it is one of the central challenges of AI search.
BFS also has the limitation we saw in the Cedar Falls example: it treats all paths as equally worth exploring. It expands Dike, Hudson, and Waverly even though a human would immediately dismiss them as heading the wrong direction. BFS has no way to prioritize — it does not know which directions are more promising without being given additional information.
What Comes Next
BFS has two limitations: it uses a lot of memory, and it cannot prioritize promising paths over unpromising ones. The next two readings address these in turn.
Reading 3 introduces depth-first search, which trades the memory cost of BFS for a different kind of exploration — following one path deeply before trying another. It uses far less memory, but gives up the guarantee of finding the shortest path.
Reading 4 introduces heuristic search, which adds domain knowledge to the search strategy — using informed estimates about which paths look most promising to guide the search intelligently toward the goal. This is the approach that makes real-world AI systems like GPS navigation practical.