Search problems, BFS, DFS & UCS

Write any planning puzzle down as a formal search problem, then hand-trace breadth-first, depth-first and uniform-cost search on it — including the frontier bookkeeping step that everyone gets wrong.

1. What a search problem actually is

An agent can always answer three local questions: where am I, what moves are legal here, and if I take one, where do I land and what did it cost? A search problem is those three, written down formally, plus a goal test.

One symbol to read carefully: $\text{Result}(s,a)$ is a function — one state and one action in, one state out, deterministic. (A random ghost breaks this and needs expectimax.)

Notice what is not in the definition: no map, no global view. A search algorithm may only call $\text{Actions}$, $\text{Result}$, $c$ and $\text{IsGoal}$; everything it knows, it discovered by poking those four functions.

A solution is a plan, not a state

Asked “what is the solution?”, the answer is an action sequence — [North, North, East, East] — or the path of states it induces, S → A → C → G. Never just the goal state.

2. World states, search states, and how big the space is

This slide looks like arithmetic and is really about modelling. Pacman in a small maze:

$p$ is Pacman's position, one of 120 non-wall squares. $f_i$ is a boolean — is dot $i$ still there? — so 30 dots give $2^{30}$ combinations: the 30 is a count of bits, not a count of states. $g_1, g_2$ are the ghosts' positions, $12 \times 12 = 12^2$; $d$ is the facing, 4 values. Multiply: $120 \cdot 2^{30} \cdot 144 \cdot 4 \approx 7.4 \times 10^{13}$, seventy-four trillion.

Why the representation shrinks when the task shrinks

For “eat the top-left dot” the goal test reads only Pacman's square. Ghosts do not block movement and dying is not modelled, so they go — factor $144$. Which other dots are eaten changes nothing we can do next, so the food bits go — factor $2^{30}$. Legal moves ignore the facing — factor $4$. State $= (p)$, 120 states.

For “eat all dots” the goal test is “are all 30 $f_i$ false?”, which mentions the food, so the food stays: $120 \cdot 2^{30} \approx 1.3 \times 10^{11}$. Ghosts and facing are still never read.

World state vs. search state

Abstraction is the highest-leverage decision in applied search: the algorithms are fixed and ten lines long, so the gap between a millisecond and never finishing is almost always the representation.

3. State space graphs vs. search trees

Two pictures, constantly confused, drawn from the same problem.

The search tree is the graph unrolled along every path: if two routes reach $B$, the graph has one $B$ and the tree has two nodes labelled $B$ — same state, different histories, usually different path costs.

4. The generic search algorithm

Every algorithm on this page — and greedy search and A* on the next page — is the same seven lines with one word changed.

The frontier

Tree search

function TREE-SEARCH(problem) returns a solution, or failure
    initialize the frontier using the initial state of problem
    loop do
        if the frontier is empty then return failure
        choose a leaf node and remove it from the frontier      <-- THE ONLY CHOICE
        if the node contains a goal state then
            return the corresponding solution
        expand the chosen node, adding the resulting nodes to the frontier

The comment marks the entire design space of uninformed search. Choose the shallowest node and you have BFS. Choose the deepest and you have DFS. Choose the cheapest-so-far and you have UCS. Choose by $g+h$ and you have A*. That is the whole story.

Graph search

function GRAPH-SEARCH(problem) returns a solution, or failure
    initialize the frontier using the initial state of problem
    initialize the explored set to be empty
    loop do
        if the frontier is empty then return failure
        choose a leaf node and remove it from the frontier
        if the node contains a goal state then
            return the corresponding solution
        add the node's state to the explored set
        expand the chosen node, adding the resulting nodes to the frontier
            only if not already in the frontier or the explored set

Two lines added, one enormous consequence: each state is expanded at most once, so the search is finite whenever the state space is. The cost is memory — the explored set can grow to the size of the state space.

What a node actually stores

From the slide “A Note on Implementation”. A node is a record with four fields:

The last row is the one to memorise, because it is the definition of $g$:

In words: a path costs its prefix plus the one new step. $g(n)$ is the backward cost — what you have already spent — as against the forward estimate $h(n)$ on the next page. We store parent rather than whole paths to save memory.

5. Breadth-first search

Strategy: expand a shallowest node first. Implementation: the frontier is a FIFO queue.

FIFO = first in, first out: children join the back, we pop from the front, so the queue drains depth 0, then all of depth 1, then all of depth 2 — BFS sweeps the tree in complete tiers. It is a ripple on a pond, except that the ripple travels by number of actions, not by cost, which is exactly why UCS exists.

Properties, with the reasoning

Write $b$ for the branching factor (max children per node), $d$ for the depth of the shallowest goal, $m$ for the maximum depth of the tree (possibly $\infty$).

• Complete? Yes, if $b$ is finite — a goal sits at some finite depth $d$, every tier is finite, so BFS reaches it.
• Optimal? Only when all step costs are equal. BFS returns the goal with the fewest actions; if every action costs the same, fewest actions = cheapest. With unequal costs it returns a 2-step path of cost $100$ over a 3-step path of cost $3$.
• Time: $O(b^d)$ — it generates every node down to depth $d$, and $1 + b + \dots + b^d = \dfrac{b^{d+1}-1}{b-1} = O(b^d)$: the last tier dominates the sum.
• Space: $O(b^d)$, and this is the killer — just before expanding the first node of tier $d$, the frontier holds essentially all of tier $d$: $b^d$ nodes in memory at once.

6. Depth-first search

Strategy: expand a deepest node first. Implementation: the frontier is a LIFO stack.

Change one word — FIFO becomes LIFO — and the behaviour inverts: children go on top of the stack and one is popped immediately, so the search plunges down a branch until it dead-ends, then backs up one level. Like a maze-walker with chalk, you mark only the current path — DFS's $O(bm)$ memory advantage.

Properties, with the reasoning

• Complete? Tree search: no — one cycle and DFS walks $A, B, A, B, \dots$ forever, and an infinitely deep branch traps it too. Graph search on a finite space: yes, because the explored set forbids revisiting.
• Optimal? No, in no sense. It returns the first goal it stumbles into, however deep and expensive.
• Time: $O(b^m)$ — in the worst case it explores the whole tree down to maximum depth $m$. When $m \gg d$ that is far worse than BFS; when goals are dense it can be far better in practice.
• Space: $O(bm)$ — linear: the stack holds only the current root-to-leaf path ($m$ nodes) plus their unexpanded siblings ($b-1$ each). This is the entire reason anyone still uses DFS.

7. Iterative deepening beyond syllabus

Not in the Lecture 2 slides, but standard pre-reading (R&N §3.4.5), and alpha-beta leans on it for move ordering.

Run a depth-limited DFS with limit $0$; no goal, run it again with limit $1$, then $2$, stopping at the first limit that finds a goal.

Re-searching from scratch every round sounds wasteful. It is not, and the arithmetic is worth seeing. Nodes generated by IDS down to depth $d$:

because the root is regenerated $d+1$ times, tier 1 $d$ times, and the bottom tier exactly once. BFS generates $N_{\text{BFS}} = b^0 + b^1 + \dots + b^d$. For $b = 10, d = 5$: $N_{\text{IDS}} = 123{,}456$ versus $N_{\text{BFS}} = 111{,}111$ — about 11% more work, and in general the overhead factor tends to $\dfrac{b}{b-1}$.

The bottom tier dominates, and IDS generates it only once. So IDS is complete, optimal when step costs are uniform, $O(b^d)$ time and only $O(bd)$ memory — the standard choice for large uniform-cost spaces of unknown depth.

8. Uniform-cost search

BFS optimises the wrong thing: number of actions. Real problems have costs — time, fuel, money, risk. UCS fixes exactly this and nothing else.

Here is the course's pseudocode, from the slides:

function UNIFORM-COST-SEARCH(problem) returns a solution, or failure
    initialize the explored set to be empty
    initialize the frontier as a priority queue using g(n) as the priority
    add initial state of problem to frontier with priority g(S) = 0
    loop do
        if the frontier is empty then
            return failure
        choose a node and remove it from the frontier          <-- the MINIMUM-g node
        if the node contains a goal state then
            return the corresponding solution
        add the node state to the explored set
        for each resulting child from node
            if the child state is not already in the frontier or explored set then
                add child to the frontier
            else if the child is already in the frontier with higher g(n) then
                replace that frontier node with child

Three lines deserve a sentence each.

• “choose a node and remove it from the frontier” — pop the node with the smallest $g$. Ties break arbitrarily, giving different but equally optimal answers.
• “if the node contains a goal state then return” — the goal test is on pop, and this is required for optimality, not stylistic: a goal generated cheaply may still sit on the frontier with a bad $g$ that a later path improves. Only at the front of the queue do we know nothing cheaper remains.
• “else if the child is already in the frontier with higher $g(n)$ then replace” — the decrease-key step of §10: rediscover a frontier state more cheaply and you must upgrade its entry; if the new route is worse, discard it. If the state is already explored, do nothing — safe by §13, because a popped node's $g$ is already optimal.

Properties, with the reasoning

Let $C^*$ be the cost of the optimal solution and $\varepsilon > 0$ a lower bound on any single step cost.

• Complete? Yes, provided every step cost is at least some $\varepsilon > 0$ and a finite-cost solution exists: each expansion raises the contour by at least $\varepsilon$, so after finitely many expansions the frontier minimum would exceed $C^*$ — impossible unless the goal was popped first. The $\varepsilon$ is not pedantry: with zero-cost actions UCS can loop forever at $g = 0$.
• Optimal? Yes — see the proof in §13.
• Time and space: $O\!\left(b^{\,1 + \lfloor C^*/\varepsilon \rfloor}\right)$, because UCS expands every node whose path cost is less than $C^*$, and at $\varepsilon$ per step the deepest such node sits at depth about $C^*/\varepsilon$ — an “effective depth” replacing BFS's $d$. With unit costs $C^*/\varepsilon = d$ and the bound collapses back to $O(b^{d+1})$.

9. Watch the frontier move

Press Step and follow three columns: what got popped, what is on the frontier, and what is already explored. Then switch algorithm and run the same graph again.

10. The UCS walkthrough, and the step everyone gets wrong

This is the slide trace, reproduced exactly and then explained. The graph:

The slide's table, complete:

Result: S-B-D-G, path cost 8.

The step you must understand: “replaced by a better path to D!”

Freeze the algorithm right after $C$ has been expanded. The state of the world is:

• Explored: $\{S, A, C\}$
• Frontier: $\{\;\texttt{S-B}: 4,\;\; \texttt{S-A-C-D}: 7\;\}$

UCS pops the minimum, which is S-B at $4$. It expands $B$. $B$'s only child is $D$, reached with

Now run the pseudocode's last two lines against this child:

1. “if the child state is not already in the frontier or explored set” — $D$ is already in the frontier, as S-A-C-D with $g = 7$, so we do not simply add it.
2. “else if the child is already in the frontier with higher $g(n)$, replace that frontier node with child” — the entry has $g = 7$, our new child has $g = 5$, and $5 < 7$, so we throw the old node away entirely and put the new one in its place.

The frontier now holds exactly one node for state $D$: S-B-D with $g = 5$, and S-A-C-D no longer exists anywhere. Hence the slide's annotation “Replaced by better path to D!”.

Why is the replacement safe? $D$'s future cost does not depend on how we reached $D$, so the only difference between the two nodes is the prefix, and $5 < 7$: any completion of the expensive prefix is beaten, edge for edge, by the same completion of the cheap one. That optimal substructure fails as soon as costs depend on history (a toll charged only if you passed through $C$) — your cue that the history belongs in the state.

Note also that $S\!-\!A$ is the cheapest first move, and UCS briefly preferred it — it popped $A$ before $B$ — before the arithmetic overturned it. Greedy first steps are not optimal plans.

11. Cost contours: how UCS really spreads

The slides summarise UCS as “UCS explores increasing cost contours”, beside a picture of concentric rings. Here is what it means.

The contour at cost $c$ is the set of states whose cheapest path from the start costs at most $c$. UCS pops the minimum $g$ and popped $g$-values never decrease (§13), so it expands states in non-decreasing order of optimal cost: the explored set always is a contour.

This also explains the bound $O(b^{1+\lfloor C^*/\varepsilon\rfloor})$ from §8: the expansions are the states inside the $C^*$ contour, and with a minimum step cost $\varepsilon$ you can only be $C^*/\varepsilon$ steps deep inside it.

The contours on a real search tree

The lecture's lettered graph:

Unrolled into a tree the way the slide does it, those twelve states explode to 28 nodes — $q$ appears four times, $a$ three times, $c$, $f$ and $p$ twice each. Drag the slider to sweep the cost contour:

12. The comparison table, and how to reconstruct it

13. Why UCS is complete and optimal — the proof

The slides assert “UCS is complete and optimal!” and move on. Here is the argument. Assume every step cost satisfies $c(s,a,s') \ge \varepsilon > 0$.

14. What's wrong with UCS — and what fixes it

Two complaints, both visible in Figure 4:

• It explores options in every “direction.” The contours are circles centred on the start, so UCS works as hard walking away from the goal as towards it: $g$ is blind to where the goal is.
• It has no information about goal location. Nothing in $\text{Actions}$, $\text{Result}$ or $c$ tells UCS which way the goal lies. That is what uninformed means.

The fix is a second number in the priority: keep $g(n)$, the backward cost paid, and add $h(n)$, an estimate of the forward cost still to pay. Order by $h$ alone and you get greedy best-first search (fast, not optimal); order by $f(n) = g(n) + h(n)$ and you get A*, whose contours stretch from circles into ellipses aimed at the goal, with optimality surviving as long as $h$ never overestimates.

15. Recap and self-check

The Essentials box at the top of this page is the recap — read it once more, then take these two checks cold.