AIMA Chapter 3 — Solving Problems by Searching.

This is the chapter where AI starts to feel algorithmic in a very concrete way. Instead of talking generally about intelligence, we now say: suppose the agent has a goal but does not yet know which action sequence will achieve it. How should it search? That question sounds innocent until you realise that even simple-looking problems generate enormous spaces of possibilities. Search is what happens when intelligence meets combinatorial explosion and tries not to drown.

01 Problem-solving agents: formulate, search, execute

A problem-solving agent works in a loop: first it formulates a goal, then it formulates a problem, then it searches for a solution, and finally it executes the resulting action sequence. This is the first place where AIMA makes a very powerful simplification: instead of attacking messy reality directly, the agent builds an abstract model where the problem becomes cleaner and more manageable.

Imagine you want to drive from Arad to Bucharest. Reality contains road quality, traffic jams, weather, fuel, driver fatigue, pedestrians, and countless local details. The Chapter 3 abstraction throws most of that away and keeps only what matters for the specific problem: locations, legal road connections, and step costs such as distance. That abstraction is not “wrong”; it is strategic. Search becomes possible because we simplify the world enough to reason over it.

Once the agent has a problem formulation, it can apply a generic search procedure. That is important. Search algorithms do not need to know they are solving a map problem or a puzzle or a scheduling task. They only need a clean interface: what state are we in, what actions are legal, where do they lead, what counts as a goal, and what does a path cost?

02 What a well-defined problem consists of

AIMA defines a well-defined problem using five components. You should know them exactly, because they are the skeleton under every search example.

These five pieces are enough to define a huge range of search tasks. The initial state gives the root of the search. The actions and transition model define the legal motion through the state space. The goal test tells us when to stop. The path cost tells us which solutions are better than others.

That last warning matters. If you model a route-planning problem using only distance but ignore tolls, fuel limits, or one-way restrictions, you may get a mathematically correct path for a simplified world that is not actually usable. Problem formulation is therefore part of intelligence, not just a pre-processing chore.

03 State space, running example, and what “solution” means

The state space is the set of all states reachable from the initial state by any sequence of actions. In the Romania map example, the states are cities and the actions are road trips between connected cities. In other problems, states may be board configurations, robot positions, or partial schedules.

A solution is a sequence of actions that takes the agent from the initial state to a goal state. An optimal solution is a solution with minimum path cost among all possible solutions. Notice that a solution is not just “reaching the goal somehow.” It is the full path that gets you there.

The Romania example is a perfect teaching example because it is intuitive without being trivial. From Arad, you can go to several neighbours, each of which opens new choices. Very quickly, you are not thinking about roads anymore; you are thinking about branching possibilities. That is exactly what Chapter 3 wants you to see.

04 Search tree vs state-space graph: the distinction students forget

This is one of the most important distinctions in the chapter. The state-space graph is the abstract problem structure: states connected by actions. The search tree is the data structure generated by the search algorithm as it explores the problem. A single state can appear multiple times in the search tree if there are multiple paths to reach it.

Why does this matter? Because algorithm complexity is usually discussed in terms of the search tree, not the clean graph. Even if the problem graph has a manageable number of states, the search tree may duplicate them many times if the algorithm does not remember what it has already seen. This is why graph search, with an explored set, can behave dramatically better than naive tree search.

This distinction also explains why loops are dangerous. In a cyclic state-space graph, a tree search that forgets repeated states can keep regenerating the same regions forever. Memory is not a luxury feature here; it can be the difference between termination and endless wandering.

05 Frontier, explored set, and child-node construction

The frontier — often called the open list — contains the nodes generated but not yet expanded. The explored set — often called the closed list — contains states whose nodes have already been expanded. Search is basically the art of deciding which frontier node to expand next.

When a node is expanded, the algorithm applies the action function to its state, constructs child nodes for each legal successor, attaches parent/action/path-cost information, and inserts those children into the frontier according to the strategy's discipline. BFS uses a FIFO queue. DFS uses a stack. UCS uses a priority queue ordered by path cost.

That simple mechanism creates all the major behaviours in Chapter 3. The difference between strategies is not magic. It is the frontier ordering policy plus the bookkeeping around repeated states and costs.

06 How we measure a search strategy

AIMA compares search algorithms using four main criteria. Completeness asks whether the strategy is guaranteed to find a solution if one exists. Optimality asks whether the strategy is guaranteed to find the best solution according to path cost. Time complexity asks how many nodes are generated or expanded. Space complexity asks how many nodes must be stored in memory.

To express these cleanly, the chapter uses a few standard symbols: \(b\) for branching factor, \(d\) for depth of the shallowest goal, and \(m\) for the maximum depth of the state space. These are not exact running times for every instance. They are asymptotic descriptions of what happens as the problem grows.

Space complexity is especially important in search because memory often kills an algorithm before CPU time does. BFS is the classic example. It is conceptually elegant and often optimal under equal step costs, but the size of the frontier grows exponentially with depth. By the time you reach the level where the goal lies, you may be storing an absurd number of nodes.

07 Breadth-first search: shallowest first, memory-hungry always

Breadth-first search expands the shallowest nodes first. Its frontier is a FIFO queue, so nodes are processed level by level. First the root, then all depth-1 nodes, then all depth-2 nodes, and so on. This makes BFS incredibly intuitive: it explores the search tree in rings spreading outward from the start.

If every step cost is equal, BFS is optimal because the first goal found must be the shallowest, and shallowest means cheapest when each step costs the same. It is also complete as long as the branching factor is finite. If a solution exists at depth \(d\), BFS will eventually reach all nodes up to that depth.

The problem is memory. Both time and space are \(O(b^d)\). Why? Because the algorithm must generate every node on each level up to the goal depth, and it must store huge parts of the frontier while doing so. That exponential frontier size is the killer.

Using the Romania map from Arad to Bucharest, BFS first expands Arad, then the depth-1 cities Zerind, Sibiu, Timisoara, then depth-2 cities reachable from them, and so on. The first time it reaches Bucharest through the shallowest number of steps, it stops. The path it finds may be Arad → Sibiu → Fagaras → Bucharest because that is a shallow 3-step route, even though it is not the cheapest by distance.

08 Depth-first search: deep, cheap on memory, dangerously blind

Depth-first search expands the deepest frontier node first. The frontier behaves like a LIFO stack, so the search follows one branch downward as far as it can before backtracking. This makes DFS memory-efficient: it only needs to store the current path plus a small number of unexpanded siblings. The space complexity is \(O(bm)\), which is tiny compared with BFS in many cases.

But DFS pays for this thriftiness with risk. It is not optimal. It can also be incomplete in infinite-depth or cyclic spaces because it may keep going down a bad path forever and never return to a shallow solution elsewhere.

That is why DFS feels seductive. On paper, low memory sounds wonderful. In practice, an unlucky expansion order can waste huge amounts of time or never terminate. This is especially dangerous when the state space has loops or when very deep irrelevant branches exist.

Its time complexity is often written as \(O(b^m)\), where \(m\) is maximum depth. That can be much worse than BFS when the solution is shallow, but the real story is qualitative: DFS is memory-light and solution-blind.

09 Depth-limited search and iterative deepening

Depth-limited search (DLS) is DFS with a safety belt: do not expand beyond depth limit \(\ell\). This stops the algorithm from falling forever down an infinite branch. It introduces a new outcome called cutoff, meaning “I stopped because the depth limit blocked me, not because the subtree was fully empty.” DLS is useful when you know a sensible depth bound in advance.

But what if you do not know the depth of the shallowest goal? That is where iterative deepening search (IDS) becomes beautiful. IDS runs DLS repeatedly with limits \(0, 1, 2, \dots\) until it finds a goal. At first this seems wasteful because the upper layers are re-expanded many times. Yet most nodes in a tree lie near the bottom, not the top. So the repeated work is surprisingly cheap compared with the memory savings.

IDS has the completeness and, under equal step costs, the optimality of BFS, but with the linear-in-depth space usage of DFS: \(O(bd)\) space instead of \(O(b^d)\). Its time remains \(O(b^d)\) in the asymptotic sense. That is why IDS is often the preferred uninformed search when the goal depth is unknown.

10 Uniform-cost search: cheapest path first, not shallowest first

Uniform-cost search (UCS) generalises BFS to unequal step costs. Instead of expanding the shallowest node, UCS expands the frontier node with the lowest path cost \(g(n)\). The frontier is therefore a priority queue ordered by cumulative cost from the root.

This one change fixes the main weakness of BFS. If roads have different lengths, the cheapest solution may use more steps than the shallowest solution. UCS finds the true least-cost path as long as every step cost is greater than some positive \(\varepsilon\). It is complete and optimal under that condition.

Two textbook details matter a lot here. First, the goal test should happen when a node is expanded, not when it is merely generated. Why? Because generating a goal node does not guarantee it is the cheapest path to that goal. A cheaper path might still be sitting elsewhere in the frontier waiting to be expanded first. Expansion is when the node is known to be the minimum-cost frontier element.

Second, if the same state is discovered again with a cheaper path cost, the cheaper frontier entry should replace the old one. Otherwise UCS can cling to an inferior route and lose optimality.

For the Arad problem, UCS eventually prefers the route Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest with total cost 418 over the shallower but costlier route through Fagaras with cost 450. That single example tells you exactly why BFS and UCS are different.

11 A worked UCS frontier story: why the cheapest route wins

Let us walk the famous route conceptually. Start with frontier = {Arad: 0}. Expand Arad and insert Zerind: 75, Timisoara: 118, Sibiu: 140. Expand Zerind first because 75 is cheapest, add Oradea: 146. Expand Timisoara next, add Lugoj: 229. Expand Sibiu at 140, then add Fagaras: 239, Rimnicu Vilcea: 220, Oradea: 291. Notice something subtle: Oradea was already in the frontier at 146 from Zerind, so the more expensive 291 path is ignored or replaced appropriately depending on implementation.

Next, UCS expands Rimnicu Vilcea at 220 because it is now the cheapest frontier node. That generates Pitesti at 317 and Craiova at 366. Fagaras at 239 is still waiting. It eventually gets expanded and generates Bucharest at 450. A careless student might say, “great, we found Bucharest, stop.” But UCS does not stop because 450 is not yet the minimum-cost node overall. Pitesti at 317 is cheaper and still waiting.

When Pitesti is expanded, it generates Bucharest at 418. Now the frontier has two candidate Bucharest nodes: one with cost 450 and one with cost 418. UCS keeps the cheaper one. Eventually Bucharest at 418 becomes the lowest-cost frontier node and is expanded. Only then do we know we have the optimal route.

Expansion step	Cheapest expanded node	Important frontier effect
1	Arad (0)	Add Zerind 75, Timisoara 118, Sibiu 140
2	Zerind (75)	Add Oradea 146
3	Timisoara (118)	Add Lugoj 229
4	Sibiu (140)	Add Rimnicu 220, Fagaras 239
5	Rimnicu (220)	Add Pitesti 317, Craiova 366
6	Fagaras (239)	Generate Bucharest 450, but do not stop yet
7	Pitesti (317)	Generate cheaper Bucharest 418, replace 450
8	Bucharest (418)	Goal expanded; optimal route confirmed

That is the logic examiners want to see when they ask why the goal test is on expansion and why frontier replacement matters.

12 Bidirectional search and the bigger comparison picture

Bidirectional search is often mentioned briefly as an idea rather than worked in detail. The intuition is simple: if you know the goal state exactly and can generate predecessors as well as successors, why search only forward? Search forward from the start and backward from the goal until the frontiers meet. In principle this can reduce the effective depth from \(d\) to about \(d/2\), which is an enormous win in exponential search. In practice, meeting conditions, reverse operators, and memory demands can make implementation awkward.

More broadly, the point of Chapter 3 is not that one algorithm beats all others. It is that different search disciplines fail in different ways. BFS is safe but memory-hungry. DFS is memory-light but reckless. DLS is disciplined DFS but needs a good limit. IDS gets the best trade-off when solution depth is unknown and step costs are equal. UCS is the right answer when costs differ and you need optimality.

Algorithm	Frontier rule	Complete?	Optimal?	Time	Space
BFS	Shallowest first (FIFO)	Yes, if \(b\) finite	Yes only for equal step costs	\(O(b^d)\)	\(O(b^d)\)
DFS	Deepest first (LIFO)	No in infinite spaces	No	\(O(b^m)\)	\(O(bm)\)
DLS	DFS with depth limit \(\ell\)	No if \(\ell < d\)	No	\(O(b^\ell)\)	\(O(b\ell)\)
IDS	Repeated DLS, \(\ell=0,1,2,...\)	Yes	Yes for equal step costs	\(O(b^d)\)	\(O(bd)\)
UCS	Lowest path cost \(g(n)\)	Yes if costs > 0	Yes	\(O(b^{1+\lfloor C^*/\varepsilon \rfloor})\)	same order

13 What search traces are really teaching you

When teachers walk through Arad-to-Bucharest, the point is not to make you memorise one famous road map forever. The point is to train your eye to read a search trace. A search trace tells a story: what is in the frontier right now, which node is chosen next, what children are generated, whether repeated states are ignored or replaced, and why the algorithm is allowed to stop. If you can narrate that story cleanly, you usually understand the algorithm. If you cannot, you probably only memorised the headline.

This becomes especially important in written exams, because many questions are not asking for a raw definition. They are asking you to simulate a few iterations, compare expansion order, or justify why one algorithm returns a different path from another. A strong answer therefore states both the mechanical rule and the consequence. Example: “BFS uses a FIFO queue, so it expands by depth and returns the shallowest solution under equal step costs.” Or: “UCS pops the lowest-cost frontier node, so it delays stopping until the goal is expanded, not merely generated.” Those explanation links are what separate real understanding from formula dumping.

It also helps to remember what information a node stores during a trace: the current state, a pointer to its parent, the action that produced it, its depth, and its cumulative path cost. Parent pointers matter because search does not usually carry the entire path string at every step; instead, it reconstructs the solution by following parents backward from the goal node once the goal is found.

Finally, traces teach humility about abstraction. The algorithm is often perfectly rational relative to the problem you gave it, yet the path it returns may feel odd in the real world. That is not always the algorithm's fault. Sometimes it is the problem formulation that was too crude. Search quality depends on both the strategy and the model being searched.

14 FAQs, takeaways, and chapter cheatsheet

Why do we abstract away messy details when formulating a problem?

Because search over raw reality is usually impossible. A useful abstraction preserves what matters to the goal and cost while discarding irrelevant noise. Good abstraction is what makes generic search feasible.

Why is the frontier sometimes called the open list?

Because it contains nodes that have been discovered but not yet fully processed. The explored set or closed list contains states already expanded.

Why is IDS usually preferred over DFS when depth is unknown?

Because it keeps DFS's low memory usage while recovering BFS-like completeness and shallow-solution behaviour. The repeated work is much smaller than it first appears.

Can BFS ever beat UCS when step costs differ?

It can be faster on some instances, but it loses the guarantee of cheapest path. If the task requires optimality under unequal costs, UCS is the correct uninformed algorithm.

• A problem-solving agent goes through formulate → search → execute.
• A well-defined problem has five components: initial state, actions, result, goal test, and path cost.
• The search tree is generated by the algorithm; it is not the same thing as the underlying state-space graph.
• Frontier ordering defines the search strategy.
• BFS is complete and shallow-solution friendly but memory-expensive.
• DFS is memory-efficient but can be incomplete and non-optimal.
• IDS is the preferred uninformed choice when goal depth is unknown and costs are uniform.
• UCS is the right answer for nonuniform step costs and requires goal testing at expansion time.