Search & Planning — Reading Notes

1.Search Problems & Terminology

A search problem asks an agent to find a sequence of actions that gets it from where it is to where it wants to be. Solving one means exploring a state space — the set of all states reachable from the initial state by any sequence of actions — without necessarily building the whole thing in memory. The vocabulary below describes how a search algorithm keeps track of what it has explored and what it still has left to explore; it is the same vocabulary the interactive lecture's Search Terminology tab illustrates on a small eight-state graph, and the same vocabulary this page reuses throughout.

1.1The Search Tree

A search algorithm does not explore the state-space graph directly. Instead it builds a search tree over that graph: a tree of paths extending outward from the initial state, where each edge corresponds to one action. The distinction matters because search tree ≠ state-space graph — a single state can be reached by more than one path, so the same state can appear as more than one node in the search tree, one for each path that reaches it. The state-space graph has one node per state; the search tree can have many.

1.2States: Initial and Goal

A state s ∈ S represents one possible configuration of the world the agent cares about. Every search problem names one state as problem.INITIAL, the state the agent starts in, and provides a test IS-GOAL(problem, s) that recognizes whether a given state counts as a solution. Three questions are worth keeping separate while reading a search trace: where can the agent be (any state), where does it start (the initial state), and where does it want to end up (any state that passes IS-GOAL)?

1.3Expansion: Successors & Child Nodes

Expanding a node means applying every action available in its state and looking at where each one leads. EXPAND(node) does this by calling RESULT(s, a) = s′ for each legal action a, then wrapping each resulting state in its own CHILD-NODE(...). It is worth keeping the vocabulary precise: a successor is a state, produced by RESULT; a child is the search-tree node built around that state. Expanding a node with three legal actions produces three successor states and three child nodes, one per action.

1.4Reached, Expanded & Frontier

At any point during search, every state the algorithm knows about falls into one of three groups. A state is reached once some path to it has been found — it has a node, even if that node has done nothing yet. A node is expanded once its children have actually been generated. And a reached-but-not-yet-expanded node sits in the frontier: the set of nodes discovered but still waiting their turn. These three ideas are easy to blur together, so it is worth stating the one that trips people up most directly: reached does not mean expanded. A node can sit in reached and in frontier at the same time, waiting; only once it is popped and its children generated does it move into the expanded set. A typical mid-search snapshot might read reached = {A, B, C, E}, expanded = {A}, frontier = {B, C, E} — one node expanded, three more reached and waiting.

1.5Expansion Order

The expansion order is simply the sequence in which nodes are selected and expanded — n₁ → n₂ → n₃ → … — and it is the single most useful thing to track while reading a trace, since it is what actually distinguishes one search strategy from another. Two algorithms can explore the exact same state-space graph and disagree completely about expansion order: BFS empties the frontier roughly level by level; DFS drains one branch before ever coming back for a sibling; a priority-queue strategy expands in order of whatever quantity it is minimizing. The graph and the algorithm never change — only the order does.

1.6The Solution Path & Path Cost

A solution path (or simply a solution) is an unbroken sequence of states and actions connecting the initial state problem.INITIAL to a goal state that passes IS-GOAL(problem, s):

When a search algorithm successfully identifies a goal node node_goal, it reconstructs the solution path by following the node.PARENT pointers backward from the goal up to the root, then reversing the chain. The path cost g(path) is the sum of the individual step costs c(s, a, s′) along that trajectory:

An optimal solution is any solution path whose path cost is minimal among all reachable solutions (denoted C*).

Crucial distinction — Expansion Order vs. Solution Path: The expansion order records every node selected and expanded during search (including dead ends, pruned redundant branches, and exploratory detours). The solution path is only the final, clean sequence of actions linking the start to the goal. For instance, in our standard graph from A to G, Uniform-Cost Search explores nodes in the expansion order A → C → B → D → E → G (6 nodes), but returns the optimal solution path A → B → D → G with path cost 8 (4 nodes).

1.7Redundant Paths

A redundant path is a second path to a state that has already been reached — formally, a child node whose node.STATE ∈ reached already. Redundant paths are common whenever the state-space graph has more than one route between two states (a city reachable from two different neighboring cities, say). Left unmanaged, they cause the same state to show up as more than one node in the search tree — wasted work at best, and at worst a search that never terminates if a redundant path can lead back to a state that leads back to it again.

1.8Tree-Like vs. Graph Search

Whether redundant paths get pruned is a design choice, not a law of nature — it is the difference between tree-like search, which keeps every path it finds as its own node (frontier only, no memory of what has already been reached), and graph search, which consults reached[state] = node before adding a child and discards the child outright if a path to that state already exists. Tree-like search is simpler but can re-explore the same state arbitrarily many times; graph search does more bookkeeping per node but guarantees each state is expanded at most once. Every strategy in Section 3 can be run either way — the pseudocode in Section 2.4 is written as graph search, since that is what the interactive lecture runs.

2.Search Data Structures

Every strategy in Section 3 is really the same algorithm with one piece swapped out: the ordering rule used by its frontier. This section covers the two data structures that make that swap possible — the search node, and the frontier itself — and then assembles them into the one generic search loop that BFS, DFS, UCS, Greedy, and A* all turn out to be instances of.

2.1The Search Node

A search-tree node is a small bundle of four fields, not just a bare state: node.STATE (which state it represents), node.PARENT (the node it was expanded from), node.ACTION (the action that produced it from its parent), and node.PATH-COST (written g(node), the total cost of the path from the initial state down to this node). A node for the state C reached from A via the action Go(C), at a running cost of 2, would read STATE = C, PARENT = A, ACTION = Go(C), PATH-COST = g(C) = 2. The parent pointers are what let a solved search recover the actual sequence of actions at the end — the algorithm just walks node.PARENT back up to the root.

2.2Frontier Operations

Whatever data structure implements it, every frontier supports the same four operations: IS-EMPTY(frontier) tests whether any nodes remain; TOP(frontier) looks at whichever node would come out next, without removing it; POP(frontier) removes and returns that node; and ADD(node, frontier) inserts a newly generated node. IS-EMPTY and TOP only ever peek — the frontier's contents never change because of them. Only POP and ADD change what is actually waiting.

2.3Frontier Types

The frontier's ordering rule — which node TOP/POP hand back next — is the one thing that turns this generic algorithm into a specific strategy:

• A FIFO queue (first-in, first-out) always returns the node that has been waiting longest. This is breadth-first behavior.
• A LIFO stack (last-in, first-out) always returns whichever node was added most recently. This is depth-first behavior.
• A priority queue always returns whichever node scores lowest under some evaluation function — g(node) for uniform-cost search, h(node) for greedy search, g(node) + h(node) for A*.

Run all three over the same graph from the same starting frontier and they diverge immediately: the FIFO queue's search tree grows level by level and tends to need the most expansions to find any particular goal; the LIFO stack's tree dives straight down whatever branch it discovered most recently, reaching a goal in very few expansions in the best case while never even looking at whole other branches; the priority queue's tree always grows toward whichever node is currently cheapest by its own measure.

2.4Best-First Search, in General

With a node structure and a swappable frontier, the entire search loop collapses to eleven lines. Starting from a node for the initial state, with the frontier and reached table both genuinely empty, the algorithm repeats one cycle until either the frontier runs dry (failure) or a popped node passes the goal test (success): pop the next node, test it, and if it is not the goal, expand it and push every child that is either newly reached or reached more cheaply than before.

function BEST-FIRST-SEARCH(problem) returns a solution node or failure
    node ← NODE(problem.INITIAL)
    frontier ← a queue containing node
    reached ← {problem.INITIAL: node}
    while not IS-EMPTY(frontier) do
        node ← POP(frontier)
        if IS-GOAL(problem, node.STATE) then return node
        for each child in EXPAND(node) do
            if child.STATE not in reached or
                    child.PATH-COST < reached[child.STATE].PATH-COST then
                reached[child.STATE] ← child; ADD(child, frontier)
    return failure

Every strategy in Section 3 is BEST-FIRST-SEARCH with one line changed: the ordering rule inside frontier. Breadth-first search and uniform-cost search are exactly this algorithm with a FIFO queue and a g(node)-ordered priority queue, respectively; depth-first search is the same loop with a LIFO stack; greedy search and A* swap in priority queues ordered by h(node) and g(node) + h(node). Nothing else about the loop changes — which is exactly why the interactive lecture's Putting It Together stepper can walk the same eleven lines for both BFS and UCS and only ever point at line 3 (frontier ← a queue) to explain why their traces diverge.

3.Search Strategies

The strategies below are grouped, in the traditional way, by how much they know about the goal's location. Uninformed strategies (BFS, DFS, UCS, IDS, plain Bidirectional Search) only know the problem definition itself — the state space, the actions, and the goal test — and nothing about how close any given state is to a solution. Informed strategies (Greedy Best-First Search, A*, SMA*) additionally use a heuristic function h(n), an estimate of the cost remaining from state n to the nearest goal, to guide the search toward the goal rather than outward in every direction at once.

3.1Uninformed vs. Informed Search

Every node a search algorithm holds can be scored by two quantities: g(n), the cost already paid to reach it, and h(n), the estimated cost still remaining. An uninformed strategy's frontier can only ever be ordered using g(n) or plain insertion order, since h(n) is not available to it; an informed strategy can combine the two, most commonly as f(n) = g(n) + h(n), an estimate of the total cost of the cheapest solution that passes through n. The practical effect shows up immediately on the same frontier viewed both ways: a node that looks unremarkable by g(n) alone can rank at the top once h(n) is folded in, because the heuristic recognizes it as sitting close to the goal even though little has been spent to reach it yet.

3.2Breadth-First Search

Breadth-first search expands the shallowest unexpanded node first, which a FIFO frontier gives for free: nodes come out in exactly the order they went in, so the search finishes an entire depth level before starting the next one. BFS is also usually implemented with an early goal test — checking a child the instant it is generated, rather than waiting for it to be popped — since doing so returns a solution at the shallowest possible depth without any extra expansions. That shortcut has a cost, though: the first goal BFS generates is guaranteed to be shallowest, not necessarily cheapest, so on a graph with unequal step costs BFS can return a shallow, expensive path while a deeper, cheaper one still exists.

Evaluation Function

f(n) = depth(n)

Frontier

FIFO queue

Goal Test

Early — tested when a child is generated

Complete?

Yes, if the branching factor b is finite

Optimal?

Only if all step costs are equal. With unequal costs it is not guaranteed — see Section 4.5.

Time Complexity

O(bd)

Space Complexity

O(bd)

3.3Depth-First Search

Depth-first search expands the deepest unexpanded node first. A LIFO stack produces this behavior automatically: whatever was added most recently comes out next, so the search commits to one branch and follows it as far as it goes before ever backtracking to try a sibling. DFS uses the standard goal test — a node is checked only once it is popped and selected, not the moment it is generated — and its successors are conventionally pushed in reverse order, so that the stack still pops them out in the same left-to-right order the other strategies use.

Frontier

LIFO stack

Goal Test

Standard — tested when a node is popped and selected

Complete?

Not in general — it can loop forever down an infinite or cyclic branch unless graph search prunes repeated states in a finite space

Optimal?

No

Time Complexity

O(bm), where m is the maximum depth of the state space

Space Complexity

O(bm) — only the current path and each level's unexplored siblings need to be kept

3.4Uniform-Cost Search

Uniform-cost search replaces the FIFO queue with a priority queue ordered by g(n), the path cost accumulated so far, and always expands the cheapest node on the frontier. Because a later-discovered path to a state can turn out to be cheaper than an earlier one, UCS uses the standard goal test and continues to update reached whenever a cheaper path to a state is found, superseding the earlier, more expensive one. This is what guarantees optimality: UCS never returns a goal node until it is certain nothing cheaper remains on the frontier.

Evaluation Function

f(n) = g(n)

Frontier

Priority queue, ordered by g(n)

Goal Test

Standard — tested when a node is popped and selected

Complete?

Yes, if step costs are ≥ ε > 0

Optimal?

Yes

Time Complexity

O(b1+⌊C*/ε⌋)

Space Complexity

O(b1+⌊C*/ε⌋)

3.5Iterative Deepening Search

Iterative deepening search runs depth-limited depth-first search — DFS that refuses to expand any node past a fixed depth limit — over and over, starting the limit at 0 and increasing it by one each time the previous attempt fails to find a goal. Every iteration restarts from scratch and re-explores the shallow levels it already searched, which sounds wasteful, but because the number of nodes at each depth grows exponentially, the repeated shallow work is dwarfed by the cost of the final, deepest iteration — IDS ends up asymptotically no worse than BFS in the nodes it generates, while needing only DFS's linear memory.

Control Parameter

limit = 0, 1, 2, …

Frontier

LIFO stack (depth-limited), rebuilt fresh at the start of every iteration

Goal Test

Standard, within each depth-limited iteration

Complete?

Yes, if b is finite

Optimal?

Only if all step costs are equal — it finds the same shallowest solution BFS would

Time Complexity

O(bd)

Space Complexity

O(bd)

3.6Bidirectional Search

Bidirectional search runs two searches at once — a forward search from the initial state, following successors, and a backward search from the goal, following predecessors — and stops once some state has been reached by both. The appeal is asymptotic: if both searches expand outward from their respective ends at similar rates, they meet somewhere near the middle of the path, after roughly the square root of the nodes a single one-directional search of the same depth would have needed. A concrete, cost-ordered version of this idea is described below as BiBF: both directions run as priority queues ordered by g(n), and at each step the search expands whichever direction's frontier currently holds the cheaper node, continuing past the first meeting point only until no remaining combination of a forward and a backward node could beat the best meeting cost already found. Run this way, bidirectional search inherits uniform-cost search's guarantees in each direction: complete when step costs are bounded below by ε > 0, and optimal, since it never stops early on a meeting point that a cheaper combination could still beat.

Meeting Condition

Forward ∩ Backward ≠ ∅

Frontier

Two priority queues, one per direction, each ordered by g(n) (BiBF)

Complete?

Yes, under the same condition as UCS in each direction (≥ ε > 0)

Optimal?

Yes, as implemented here (BiBF) — the search does not stop at the first meeting point, only once no cheaper one remains possible

Time / Space

Substantially less than a single one-directional search to the same depth — informally, on the order of the square root of the one-directional node count when both searches expand at comparable rates

3.7Greedy Best-First Search

Greedy best-first search orders its priority queue by h(n) alone, always expanding whichever node the heuristic estimates is closest to the goal — completely ignoring g(n), what it has already cost to get there. That single-mindedness makes it fast when the heuristic is good, but it is easy to mislead: a node that looks close to the goal by the heuristic's estimate can sit at the end of an expensive path, and greedy search has no mechanism to notice. It will happily commit to that path anyway.

Evaluation Function

f(n) = h(n)

Frontier

Priority queue, ordered by h(n)

Goal Test

Standard — tested when a node is popped and selected

Complete?

Not in general — a poor heuristic can lead it down an infinite path; complete in finite state spaces when repeated states are pruned (graph search)

Optimal?

No

Time Complexity

O(bm) worst case — much better with an accurate heuristic

Space Complexity

O(bm) worst case — generated nodes are kept, as in BFS

3.8A* Search

A* orders its priority queue by f(n) = g(n) + h(n), combining what greedy search and uniform-cost search each do alone: g(n) keeps it honest about cost already paid, and h(n) keeps it aimed at the goal instead of expanding outward in every direction. Provided the heuristic never overestimates the true remaining cost — it is admissible — A* run as tree-like search is guaranteed optimal; the slightly stronger condition of consistency (h(n) ≤ cost(n, a, n′) + h(n′) for every edge) is what extends that guarantee to graph search. In practice A* with a good heuristic explores dramatically fewer nodes than uniform-cost search while still finding the same optimal solution.

Evaluation Function

f(n) = g(n) + h(n)

Frontier

Priority queue, ordered by f(n)

Goal Test

Standard — tested when a node is popped and selected

Complete?

Yes, if b is finite and step costs are ≥ ε > 0

Optimal?

Yes, if h(n) is admissible (tree-like search) or consistent (graph search)

Time Complexity

Exponential in the worst case, often written O(bd); far better with an informative heuristic

Space Complexity

O(bd) worst case — like BFS and UCS, A* keeps every generated node

3.9SMA*: Memory-Bounded A*

SMA* (Simplified Memory-Bounded A*) is A* with a hard cap on how many nodes it may hold at once. When that cap is reached and a new node needs room, SMA* forgets its worst leaf — the one with the highest f-value, and therefore the least promising — and backs up that leaf's f-value to its parent. Recording the discarded value at the parent matters: it stops the parent from ever being mistaken for as cheap as it first looked, so if every other option turns out worse, SMA* can still regenerate the forgotten branch and pick up where it left off.

Evaluation Function

f(n) = g(n) + h(n), plus a fixed memory bound

Frontier

Priority queue ordered by f(n), capped at a fixed number of nodes; the worst leaf is forgotten (and its value backed up to its parent) whenever the cap is reached

Complete?

Yes, if a solution exists whose nodes fit within the memory bound

Optimal?

Yes, under the same memory condition as completeness

Time Complexity

Can exceed A*'s — a forgotten subtree that turns out to be needed again must be regenerated

Space Complexity

Bounded by construction — never exceeds the fixed memory limit

3.10Goal Testing: Standard vs. Early

The generic algorithm in Section 2.4 tests IS-GOAL right after popping a node — the standard goal test. Some strategies instead test each child the moment EXPAND generates it, before it is even added to the frontier — the early goal test — trading a small amount of bookkeeping for the chance to stop one generation sooner. The early test is only safe when the first-generated goal is guaranteed to be the one the algorithm actually wants: true for BFS, since every step costs the same and the first-generated goal is therefore guaranteed shallowest. It is not safe for UCS or A*, where a goal generated early is not necessarily the cheapest one — using the early test there could return a correct-looking but suboptimal solution, exactly the failure mode the standard test is built to avoid.

4.Evaluating Search Algorithms

With eight strategies on the table, the natural next question is how to compare them. Four criteria, applied consistently, do the job: whether a strategy is guaranteed to find a solution at all (completeness), whether it is guaranteed to find the cheapest one (optimality), and how much time and memory it may need along the way. All four are usually expressed in terms of five quantities that describe the shape and cost structure of the search tree itself.

4.1b, d, m, C*, ε

Two of these quantities describe depth, and two describe cost — worth keeping straight, since they measure different things and do not have to move together. The branching factor b is how many children a node typically has. The depth of the shallowest solution d and the maximum depth m of the state space are both depth quantities. The optimal solution cost C* and the minimum positive step cost ε > 0 are both cost quantities — and, as the figure below shows, the shallowest solution and the cheapest one are not required to be the same node.

4.2Time Complexity

A search algorithm's time complexity is normally expressed as however many nodes it may need to generate — not wall-clock time, since that depends on the hardware, but node count, which does not. BFS and IDS, which explore level by level (IDS by repetition), generate on the order of every node down to the shallowest solution: O(bd). DFS and greedy search, in the worst case, can be forced down a branch all the way to the tree's maximum depth before finding anything: O(bm). UCS's bound is stated in terms of cost rather than depth, since that is what it actually searches by: O(b1+⌊C*/ε⌋), the branching factor raised to roughly how many ε-sized steps fit inside the optimal cost. A*'s worst case is exponential as well, often written O(bd), but an informative heuristic can shrink the number of nodes actually generated well below that bound.

4.3Space Complexity

Space complexity counts how many nodes an algorithm may need to hold in memory at once, and this is where the uninformed strategies split sharply into two camps. BFS, UCS, and A* all keep every node they generate — the entire frontier, plus everything in reached — so their space bounds match their time bounds exactly. DFS and IDS need only the current path from the root down to wherever they are now, plus each level's unexplored siblings along the way, which is why their space bounds — O(bm) and O(bd) respectively — are so much smaller than their time bounds. This is the whole reason iterative deepening exists: it accepts BFS's repeated shallow work in exchange for DFS's memory footprint.

4.4Completeness

An algorithm is complete if it is guaranteed to find a solution whenever one exists — which also means correctly reporting failure whenever one does not, rather than searching forever. Completeness turns out to hinge on a small number of structural guarantees: a finite branching factor rules out an algorithm getting stuck expanding one node's infinitely many children; a positive lower bound ε on step cost rules out an infinite sequence of ever-cheaper paths that a cost-ordered strategy could chase forever without ever reaching the cheapest one. BFS, IDS, UCS, and A* each satisfy the conditions relevant to them and are complete. DFS and greedy search are not complete in general — both can be led down an infinite (or merely very long) branch with nothing to pull them back, unless the state space is finite and graph search prunes repeated states.

4.5Optimality

An algorithm is optimal if, whenever it returns a solution, that solution's cost equals the true optimal cost: C(solution) = C*. Finding a solution is not the same as finding the best one, and BFS is the clearest illustration of the gap: because it uses an early goal test and stops at the shallowest goal it generates, it can return a shallow, expensive path while ignoring a deeper, cheaper one still sitting unexplored on the frontier — exactly the situation the interactive lecture's BFS trace walks through, where the shallow route (cost 10) is found before the truly cheapest one (cost 8) would have been. UCS and A* avoid this by using the standard goal test and refusing to return a goal until nothing better remains possible on the frontier, which is precisely what makes them optimal.

4.6Comparing the Strategies

Put together, the eight strategies trade completeness, optimality, time, and space against each other in different combinations — no single strategy dominates every column, which is exactly why the choice of strategy matters.

That is the full arc of Topic 02: a search problem's terminology (Section 1) gets implemented with a node and a frontier (Section 2), the frontier's ordering rule is what turns the same generic loop into eight different strategies (Section 3), and completeness, optimality, time, and space are the four questions that let you choose between them (Section 4). The interactive lecture covers the same ground with a live, clickable version of every example above.

5.Practice Exercises

The eight exercises below are drawn from the course's search-problem exercise set (instructions/exercises.md), in the same order and grouping used there — Exercises 1–2 trace algorithms on a graph, Exercises 3–8 prove properties of them. Each one is stated first, exactly as assigned; the worked solution stays hidden behind a Show Answer button so this section can double as a self-check rather than a spoiler.

g(A)=1, g(B)=1 → A first
g(C) = min(g(A)+1, g(B)+2) = min(2,3) = 2   [via A]
g(G) = g(C)+3 = 5

h(S)=2 → children h(A)=4, h(B)=1 → B (min h)
h(C)=1 → C
h(G)=0 → G

f(A)=1+4=5,  f(B)=1+1=2        → B first
f(C)=g(B)+2+h(C)=3+1=4         → C next  (4 < 5)
f(G)=g(C)+3+0=6+0=6
pop A(f=5): g(C via A)=1+1=2 < 3 → f(C)=2+1=3, C reopened
f(G) via new C = 2+3+0 = 5 < 6 → update, then G popped

depth(G) = 1  (direct child of S)
⇒ no node at depth < 1 remains ⇒ early test on G is safe

generated together: g(A)=1, g(G)=10
early test on G ⇒ reports cost 10
true cost: g(A) + c(A,G) = 1+1 = 2 < 10
late test: pop min(g) = A(1) first ⇒ g(G): 10 → 2 ⇒ G popped at cost 2

Base:  N(0) = 1 = b^0
Step:  N(k+1) ≤ b·N(k) ≤ b^(k+1)                          ∎

Σ_(k=0..d) b^k = O(b^d)

Time = Space = Σ_(k=0..d) b^k = O(b^d)

Base:  S(0) = 1
Step:  S(k+1) = S(k) - 1 + b ≤ 1+(b-1)(k+1)                    ∎

Space = O(bm) at depth m;  Time = Σ_(k=0..m) b^k = O(b^m)

IDS:     Time = Σ_(l=0..d) O(b^l) = O(b^d)   [geometric sum, dominated by last term]
         Space = O(bd)                        [one DFS branch live at a time]

UCS:     layer by cost band j = floor(g(n)/e);  same Lemma re-indexed by j, bound j* = floor(C*/e)
         Time = Space = O(b^(1+floor(C*/e)))

A*:      admissible h ⇒ f(n)=g(n)+h(n) ≤ g(n)+h*(n) = C*  for n on an optimal path
         layering by floor(f(n)/e) reuses the same Lemma
         Time = Space = O(b^(1+floor(C*/e)))        [h=0 reduces this to UCS's bound]

Greedy:  no cost pruning ⇒ worst case matches the DFS/tree bound
         Time = Space = O(b^m)

n on optimal path:      g(n) + h*(n) = C* = 2+3 = 5
admissibility:          f(n) = g(n)+h(n) ≤ g(n)+h*(n) = 5
h(G2)=0:                f(G2) = g(G2) = 8
therefore:              f(n) ≤ 5 < 8 = f(G2)

limit=1: IDS finds G1 first → cost 10 → returns it, stops
true optimum: G2, cost 1+1 = 2
10 > 2  ⇒  IDS is not optimal here

g(n) = 2 ≤ C* = 5 < 8 = g(G2)

pop S → push B,A (A on top) → pop A → expand → generates G1
pop G1 → goal test succeeds → STOP

DFS returns:  S→A→G1,  cost = 10+0 = 10
true optimum: S→B→G2,  cost = 1+1  = 2