Search algorithms · Part 1

Welcome to search algorithms — one of the most fundamental, reusable ideas in all of artificial intelligence. In fact, you have already met it: TuroChamp used search through chess continuations back in the history lectures. This lecture makes that idea precise and general.

The big picture is simple to state but powerful to apply. Many problems — finding a route on a map, solving a puzzle, planning how a robot should move — can be re-expressed as search: systematically exploring possible actions until we reach a goal. In this first part we do two things:

1. Model the problem. We translate an everyday task into a clean mathematical form using states, transitions, paths and costs — so that “finding the answer” becomes “searching a graph.”
2. Compare exploration rules. Then we study strategies for which path to explore next. This part covers the uninformed (or blind) strategies, which do not use any estimate of how far we still are from the goal — they simply follow a fixed rule.

Specifically you will learn:

• The vocabulary that lets us talk about any search problem: states, paths, costs and the frontier;
• Two classic strategies with opposite philosophies: breadth-first (finish all shallow options before going deeper) and depth-first (commit fully to one branch at a time);
• And two refinements — iterative deepening, which combines the strengths of both, and lowest-cost-first, which picks whatever partial solution has spent the least total cost so far.

The next part of this course adds “informed” strategies that use extra knowledge about the goal. For now, master these building blocks: almost every cleverer algorithm you will meet is a small variation on this same theme.

The parcel model used in the slides

The simplified robot state is (robot location, parcel status), with parcel status at depot, carried or delivered. Initially the state is (depot, at depot). Picking up, moving to the customer and delivering each cost one unit, giving (depot, carried), (customer, carried) and (customer, delivered). The depicted solution costs 3 units. The goal tests whether the parcel is delivered; the robot need not remain at the customer afterward.

Two situations may share an encoded state only if that state determines the same legal actions, their outcomes and costs, and the same goal-test result. If time, fuel or task progress changes any of these, include it in the state. Accumulated route cost is kept in a search record; it is not automatically part of the environment state.

The original application examples differ in their objectives: a video-game character may accept any route that completes the required tasks; a car navigator seeks minimum travel time; a delivery robot may minimize energy while avoiding obstacles; and a traveling salesperson seeks a minimum-fare itinerary visiting all required cities (returning to the start in the usual tour formulation). For the robot, shortest distance is an energy proxy only if the physical model makes energy proportional to distance; flat terrain alone does not establish that. The slides use unit action costs for their simplified parcel example.

The first step in solving any problem with search is deciding how to describe the situation — this description is called the state. A state must capture everything relevant about where you are right now, so that you can answer two questions: which actions are legal, what their outcomes and costs are, and whether the goal condition holds?

The key word is relevant, because a good state includes only the information needed to make decisions. Consider three examples:

• A simple road map. If you just need directions between cities, knowing your current intersection may be enough — every decision from there depends on where you are now and nothing else about how you got there.
• A delivery robot. The robot needs more than its location: it must also know the parcel status, distinguishing an item at the depot, being carried, and already delivered. A state of “robot at door, not holding parcel” and one of “robot at door, holding parcel” are completely different situations requiring different actions — even though the position is identical.
• A traveling salesperson visiting many cities needs to distinguish the current city from the set of cities already visited. Two routes that both end in Rome but have seen different other cities are not interchangeable, because what remains to visit differs. (That’s why the state must include both the current location and the set of cities already visited — a “subset” problem; the full visit order is not needed for the usual formulation.)

The crucial warning is this: if you leave out relevant information from your state definition, two genuinely different situations may look identical. The search algorithm cannot tell them apart, so it will treat one plan as valid for both — which can silently invalidate the solution. Getting the state right at the start is often half the work of solving a search problem; getting it wrong poisons everything downstream.

The formal graph definition

V is the set of vertices. The Cartesian product V × V contains every ordered pair of vertices; E selects the pairs that are legal moves. For example, V = {A, B, C, D} and E = {(A, B), (A, C), (B, D), (C, D), (D, A)}. An undirected edge allows movement both ways; a directed edge (A, B) allows only A → B unless (B, A) is also present.

Once we have defined states, we need to say how one state can turn into another — this is where graphs come in. A graph is a mathematical structure with two ingredients: vertices (also called nodes) and edges. In our search setting:

• Vertices = states. Each possible situation you can be in becomes one vertex of the graph.
• Edges = transitions. A connection between two vertices represents a permitted move from one state to another. When an edge carries a direction — “you may go from A to B” — we call it a directed (ordered) edge, and the graph is called directed.

The word directed matters more than students often expect. An edge pointing from A to B authorizes movement in that direction; it does not automatically authorize the reverse move back from B to A. You can see why this distinction is essential with everyday examples:

• One-way streets. A street may allow travel north but not south — a directed edge only one way.
• Irreversible actions. In many puzzles and robot tasks you cannot undo an action (you can pour out the water, but maybe you cannot un-pour it). The transition exists in one direction only.
• Prerequisites. Some moves require having done something first — you may only “submit assignment” after completing certain steps, so that edge is usable only from states where the prerequisite holds.

Finally, there are two practical ways to supply the graph:

1. Explicitly: store a full list of vertices and edges before searching (fine when small).
2. Generated on demand by a successor function: given any state, compute its neighbors as you go. This is usually much better — it avoids storing every possible state in advance, which for large problems would be impossible anyway.

The notion of “from each state, what states can I reach?” via this successor function is the workhorse that search algorithms will repeatedly call throughout this lecture.

G names the graph; V is its vertex (state) set and E its directed-edge (legal-transition) set. A, B, C and D are state labels. In the implicit representation, successors(current state) returns legal triples (action, next state, step cost). For the toy robot at (depot, at depot), picking up produces (depot, carried) at cost 1; moving without the parcel produces (customer, at depot) at cost 1. The latter is legal in this model but does not deliver the parcel.

p is a path; k is its number of vertices; i is a position index from 1 to k; vᵢ is the vertex at that position. The symbols vₛ and v_G name the start and goal vertices. g(p) is the path’s total edge cost from the start. ω_E (omega) is the edge-cost function, ℝ the set of real numbers, and ∑ means add the costs indexed from i = 1 to k − 1. The graph G and a state labeled G are different uses of the letter; state labels in worked examples are not graph variables.

Paths, weighted graphs and the cost sum

Angle brackets indicate an ordered sequence. Every listed vertex must exist, and each consecutive pair must be a legal edge. There are k vertices but only k − 1 transitions. Here vₛ is the start and v_G is a fixed goal; with several acceptable goals, replace the final equality with a goal test.

The edge-weight function ω_E assigns a real number to each edge. The summation adds the costs of the first, second, …, last transition in p. For p = ⟨A, B, D⟩, this is ω_E(A, B) + ω_E(B, D) = 1 + 5 = 6. The single-vertex path ⟨A⟩ has no edges, so its empty sum is 0. With unit edge weights, g(p) = k − 1. A real-valued weight function can describe negative edges, but the optimality guarantees taught for UCS and A* require the later cost assumptions.

See the path and cost formulation in the slides →

Now we connect states and transitions into a path: a sequence of legal transitions that starts at the initial state. If you think of the graph as a set of possible moves, then a path is one concrete way to actually get from your starting point somewhere else by following permitted edges in order.

A path becomes something we care about — a solution — precisely when its endpoint satisfies the goal condition. The goal isn’t necessarily “the last city on the map”; it is whatever state (or set of states) counts as having finished the task, such as reaching any charging station or solving the final puzzle configuration.

Here is an important subtlety: finding a solution and finding a good one are two different things, so we measure quality separately from existence. Each edge in the graph can carry a cost — representing distance, time or effort for that move. Adding up all the edge costs along a path gives its cumulative cost, usually written g. This single number is our way of comparing how good different solutions are.

The reason we need this separate notion should be obvious from a concrete example: two routes can reach the goal with the same number of steps yet very different total costs. In the lecture, route A–B–D has cost 6 while A–C–D has cost 18. Both take just two moves and both solve the problem — but if we only counted steps (each edge = one unit), we would wrongly treat them as equally good. Cost lets us prefer the cheaper A–B–D.

This distinction — solving versus optimizing the path’s cost — drives everything later in this lecture. Some search strategies ignore cost entirely (they just want any solution or one with few steps); others explicitly minimize cumulative cost. Keeping “path” and “cost” as separate concepts from the start will save you a great deal of confusion.

Directed cycles, DAGs and rooted trees

A directed cycle exists if a legal path with at least one edge returns to its start. A directed acyclic graph (DAG) has no such path:

The condition k ≥ 2 excludes the trivial, zero-edge path. A DAG may still have two distinct paths to one vertex: A → B → D and A → C → D form a diamond without a directed cycle. It is not a rooted tree.

For the outward-directed trees used here, the original definition has three requirements:

1. Connected underneath: for every pair u, v ∈ V, an undirected path connects u to v after we ignore arrow directions.
2. Acyclic underneath: that undirected graph has no cycle.
3. A root reaches everyone: there exists r ∈ V such that for every v ∈ V, there is a directed path ⟨r, …, v⟩.

Here ∀ means “for every” and ∃ means “there exists.”

Together these imply exactly one directed root-to-vertex path. The root has no incoming edge, each other vertex has one parent, and a leaf has no outgoing edge. Depth is the number of edges from the root. These statements describe the orientation used in our examples, not every possible orientation of an undirected tree.

Compare a DAG with a rooted tree in the slides →

To make the choices available during search easy to picture, we draw them as a tree. A tree is a special kind of graph with two useful properties: it has no cycles (you cannot loop back to where you were), and every node can be reached from a single starting point — called the root — by exactly one route. When we hang the picture from that root at the top, we call it a rooted tree.

• Depth: for any node, depth counts how many edges lie along the unique route from the root down to it. The root itself is at depth 0; its children are depth 1; and so on.
• Leaf: a node with no children — the end of a branch where there are no further choices in this picture.

Trees make successive decisions visible because each branching point shows you all the alternatives available at that step. In our running course example, the goal state S sits at depth four along the route A–B–F–P–S — meaning it takes exactly four transitions to reach from the root.

One more quantity is essential for understanding why search can explode so quickly: the branching factor. This describes how many alternative children a typical node generates. If every state has, say, three possible next moves (branching factor 3), then:

• depth 1 → 3 nodes;
• depth 2 → about 9 nodes;
• depth 10 → roughly 3¹⁰ ≈ 59,000 nodes.

The punchline is worth internalizing now: even a moderate branching factor creates an enormous number of paths as depth increases. A game with 30 legal moves per position produces astronomically many continuations just a few dozen moves deep. This exponential growth is the fundamental reason we need clever search strategies rather than simply listing every possibility — and it explains why chess (from our history lecture) was always such a natural test bed for AI.

In the quantified definition, u and v denote arbitrary vertices in V; r denotes the root. In the full-tree growth example, b is the number of children per non-leaf and d is depth in edges from the root. There are exactly b^d nodes at that depth when every non-leaf has b children: b = 3 gives 1, 3, 9, 27 and 81 nodes at depths 0–4, and 3¹⁰ = 59,049 at depth 10. For uneven trees these exact counts need not hold.

A subtle point that trips up beginners: the state graph and the search tree are different objects with a different relationship to “one situation.” It is worth being very precise about this.

• A state-graph vertex represents one situation. There is exactly one vertex for each distinct state, no matter how many ways you could arrive at it. Think of it as the physical map: each city appears once.
• A search-tree node represents reaching a situation by a particular route. The tree keeps track of how you got somewhere — which choices led here. So two different sequences of moves that end in the same state produce two distinct nodes, even though they refer to the same underlying graph vertex.

Consequently, several search-tree nodes can point to the very same state. Why does this matter? Because it opens the door to a serious practical problem:

Imagine a small graph with a cycle — A goes to B, B goes back to A. From state A you can generate paths A–B, A–B–A, A–B–A–B, and so on without end. The tree grows forever even though there are only two real states, because the search keeps re-entering the same situation by different routes.

There is a standard remedy worth distinguishing clearly:

• Cycle prevention per path: check whether a state already occurs on the current single path. This stops any one branch from looping forever (you never revisit, along this route, somewhere you have already been). It does not stop different branches from both reaching the same new state.
• Global duplicate handling: remember states reached across routes and apply a strategy-appropriate duplicate rule. In weighted search, preserve a later cheaper route rather than discarding it merely because the state was seen before. This can avoid exploring redundant routes, but requires extra bookkeeping, such as a visited set or a best-known cost for each state.

The lecture’s point: per-path cycle checking and global duplicate removal are different mechanisms with different effects. The first prevents a branch from cycling; the second avoids redoing entire subtrees. Both are useful, but you should know which one you are applying.

The frontier (also called the open list or agenda) is the heart of search bookkeeping — so let us make sure its meaning is crystal clear. The frontier is a collection of unfinished possibilities: partial paths that have been discovered but not yet fully explored to completion.

A very common misconception is to think of it as “the list of states already solved.” It is exactly the opposite: these are precisely the possibilities we have not finished with. Each one is a partial route that might, if extended far enough, reach the goal.

The two key operations on the frontier mirror the search loop:

• Selecting removes a path from the collection so we can examine it (we will formalize this in the search loop next).
• Expanding takes that path, looks at its endpoint’s legal successors, and places each extended path back into the collection — growing the frontier with new unfinished possibilities.

A subtle but important consequence: a node can be discovered long before it is selected or expanded. When we expand A, we add paths through B, C and D to the frontier even though we have not yet looked inside any of them. They sit there waiting; only when one is eventually selected do we actually inspect where it leads.

To see this concretely in our running example: expanding state A replaces the single path ⟨A⟩ with three new paths, through B, C and D. Which of those gets examined next depends entirely on the strategy — a queue would take them in discovery order; a stack would reverse that; a priority queue might jump straight to whichever looks cheapest so far. The frontier is the stage where all these different strategies play out.

G is the input graph, V its vertices, and E its edges. vₛ is the start vertex and v_G the goal vertex. F is the frontier, p the selected path and v a legal next vertex. select(F) chooses according to the strategy; end(p) is p’s final vertex. The arrow ← assigns a value and p ⊕ v appends v to p. Here the goal is one specified vertex; multiple acceptable goals use a goal-test predicate.

Inputs, outputs and mathematical notation

Input: G = (V, E), vₛ ∈ V and v_G ∈ V. Output: a legal path starting at vₛ and ending at v_G, or failure if the frontier is exhausted without finding one. F is the collection of waiting paths; ∅ is the empty collection; end(p), also written p[end] in the original, is the last vertex. We write p ⊕ v for appending v to p.

All of the strategies in this lecture share one underlying skeleton, called the generic search loop. If you understand this single algorithm, every later strategy is just a different choice inside it. Here is how it works:

1. Initialize. Begin with a collection holding only the trivial path consisting of the start state alone — written ⟨A⟩ if A is our starting point. This is everything we know so far: one unfinished possibility.
2. Select. Remove one path from the frontier (the set of candidate paths awaiting attention).
3. Test. Check whether the endpoint of that path satisfies the goal condition. If yes, you are done — this path is your solution.
4. Expand. If not a goal, generate all legal extensions of its endpoint (its successors), and add each one as an extended path to the frontier.
5. Repeat steps 2–4. If at any point the frontier becomes empty with no solution found, then under this search policy no candidate remains, and the search returns failure. Concluding that no solution exists also requires a search and pruning policy that has preserved every possible solution.

The single most important insight about this loop is where all the interesting variety lives: the selection step. Step 2 — deciding which path to take out of the frontier next — is what distinguishes one search strategy from another. The way we store and order that collection controls selection:

• A queue (first in, first out) yields breadth-first exploration;
• A stack (last in, first out) yields depth-first exploration;
• A priority queue, ordered by some score, yields strategies like lowest-cost-first.

Notice the elegant consequence: replacing a queue with a stack or priority queue can radically change the order of exploration — and therefore how quickly you find (or fail to find) solutions — without changing anything about how the problem itself is represented. The same graph, the same goal, completely different behavior. That clean separation between “the problem” and “the strategy that searches it” is exactly what makes search such a powerful and reusable framework.

Read the set operations: F ∖ {p} removes just the selected path. The expression {p ⊕ v : (end(p), v) ∈ E} means “all one-edge extensions of p whose next step is legal.” The colon means “such that”; ∈ means “belongs to.” Union (∪) adds those paths to the frontier without discarding the other waiting candidates.

For example, after selecting ⟨A, B⟩ from {⟨A, B⟩, ⟨A, C⟩, ⟨A, D⟩}, remove it and add ⟨A, B, E⟩, ⟨A, B, F⟩ and ⟨A, B, G⟩. The paths to C and D remain. F is abstract set notation: an implementation also records queue/stack order or priorities and a tie rule. This is a path-search skeleton; add appropriate cycle or duplicate handling on graphs. “No solution” is justified by exhaustion only if that policy has preserved all possible solutions.

Before comparing specific strategies, we need a shared vocabulary for judging them — four questions you can ask of any search algorithm. Learning these criteria now will make every later comparison effortless:

1. Completeness. If a solution exists somewhere in the problem, will this method eventually find it? A complete algorithm guarantees that, given enough time and memory, no reachable goal is missed forever (e.g., by wandering down one infinite branch).
2. Optimality. When the method does return a solution, is it guaranteed to have minimum cost among all possible solutions? A complete algorithm might find a goal but not necessarily the best one — optimality asks whether it finds the cheapest path.
3. Time complexity. How many operations (states generated or expanded) does the method need in the worst case, as a function of problem size?
4. Memory (space) complexity. How much storage does it require — especially how large can its frontier grow to be?

The crucial point is that these four criteria are separate and often trade off against one another. Some vivid examples make this concrete:

• A method using very little memory may nonetheless explore a deeply unfortunate branch for an enormous time before noticing it was the wrong way (memory-efficient, but slow).
• An optimal algorithm that always finds minimum-cost solutions may have to retain an enormous frontier of candidates — potentially consuming huge amounts of memory.

In short: cheap in one resource often means expensive in another, and completeness/optimality are properties you must check separately from speed or storage. Finally, a crucial warning about reading guarantees honestly:

Each algorithm’s promised behavior holds only under stated assumptions — typically about the branching factor, the maximum search depth, whether edge costs are nonnegative, and how repeated states (which we met earlier) are handled. Change any of those assumptions and a guarantee may break. So whenever you see “BFS is complete” or “this strategy is optimal,” always ask: under what conditions?

The strategies in this lecture belong to a category called uninformed search (also known as blind or brute-force search). The name tells you exactly what they lack: they use no heuristic estimate of how far a state still is from the goal. They still use the problem’s legal transitions, goal test and any specified edge costs.

It might sound like “not knowing anything” would make these strategies weak, but they can still be remarkably effective because they are systematic. Even without a goal-distance estimate, an uninformed strategy has plenty of information to organize its choices:

• Depth: how far down the tree this path already is (used by depth-limited ideas and iterative deepening).
• Insertion order: when each candidate was added to the frontier — a queue respects arrival time, a stack reverses it.
• Accumulated cost: how much has been spent so far along this path (used by lowest-cost-first search).

So “uninformed” does not mean random — it means the strategy relies on properties of the exploration itself rather than clever guesses about where the goal lies.

Why study them? Three reasons:

1. They are useful baselines. Before trying anything fancy, you want to know how a simple systematic method performs. They give you a reference point for measuring whether an informed (heuristic) strategy is actually helping.
2. They are appropriate when no good heuristic exists, or when the problem offers no reliable way to estimate remaining distance — in which case any clever guess could actively mislead, and blind search may be the safest honest choice.
3. They reveal a fundamental tradeoff. Across all uninformed methods runs one central tension: explore many alternatives at shallow depth (breadth-first), versus commit to fewer, deeper possibilities and follow them all the way down (depth-first). Weighing these two impulses — breadth of coverage against depth of commitment — is exactly what distinguishes the strategies you are about to learn.

Hold onto that tradeoff: it explains why breadth-first, depth-first, iterative deepening and lowest-cost-first each exist. They use different frontier-selection rules: queue order, stack order with or without a depth limit, and accumulated path cost.

Breadth-first search (BFS) realizes one side of our tradeoff: explore broadly before going deep. It works by storing its frontier in a first-in, first-out queue — exactly like the line at a checkout counter.

• Newly generated paths are added to the back of the queue.
• The path selected next comes from the front — whichever has been waiting longest.

The consequence of this discipline is predictable and important: BFS exhausts every possibility at depth 0 (just the start), then every path of length 1, then length 2, and so on. It “completes a layer” before ever descending to the next one — which is exactly why it is called breadth-first.

What does that buy us? Under reasonable assumptions (finite branching factor and a goal reachable at finite depth), BFS has strong guarantees:

• Complete: if any solution exists, BFS will eventually find it — because no shallower layer is ever skipped.
• Returns the fewest-edge solution: since it examines all paths of length d before any of length d+1, the first goal it hits lies on a shortest path in terms of steps.
• Cost-optimal when every edge has the same positive cost: if each move costs exactly 1 (or some fixed amount), then fewest edges also means least total cost. (With differing edge costs this guarantee no longer holds — that’s why we need lowest-cost-first later.)

The tradeoff shows up in memory: BFS must keep track of every unfinished path, and because it finishes one whole broad layer before descending, an entire wide level can accumulate on the frontier at once. With a large branching factor, that single level may be astronomically big — this is why BFS, though complete and often optimal in steps, can run out of memory long before it runs out of time.

A goal is accepted when its waiting path is selected. BFS need not expand every node at the goal’s depth: it finishes the shallower layers and may stop partway through the goal layer. Equal-depth ties follow insertion order.

The interactive example in this section lets you watch breadth-first search run on the running course map, and it rewards active use. Before advancing each step, try to predict which path will be selected next by inspecting the queue display — then check your guess.

A helpful mental rule for prediction: after a node is expanded, all of its siblings (the other children of the same parent) were generated earlier than this node’s own descendants. Because BFS uses a first-in-first-out queue, those older siblings sit ahead in line. So the algorithm always finishes every member of the current layer before moving down into the next one.

The example also invites you to compare different goal placements. If we set the goal at B, BFS finds it almost immediately — right after expanding A. If instead we put the goal deep at S (depth four along A–B–F–P–S), notice how much more work BFS must do first: every shallower path gets explored before that deeper one is ever reached.

• Comparing goals at different depths makes vivid that goal depth directly controls the total amount of work. Shallow goals are found quickly; deep ones force BFS to sweep out many entire layers first.
• The point about finding B right after A deserves special care: this happens purely because of queue order — B was discovered early and waited near the front. It is not evidence that BFS judged B promising or knew anything about where the goal lies. Uninformed search has no such knowledge; it just follows its fixed ordering.

Keep this in mind whenever you watch a blind-search animation: any “luck” you see comes from insertion order and layer-by-layer discipline, never from foresight about the goal.

This lab uses unit edge costs, so its reported solution cost equals edge count. With the default goal S, the route A → B → F → P → S has cost 4. The UCS lab uses the same tree topology with its supplied unequal edge weights, for which that route costs 1 + 6 + 2 + 3 = 12. The final exit-comparison lab applies the same weighted costs to every method.

Stack or recursion: recursive DFS uses the function-call stack to remember the current branch and the alternatives left to try. Returning from a recursive call performs backtracking. The explicit LIFO frontier and recursive versions describe the same depth-first discipline when child order is matched.

Depth-first search (DFS) takes the opposite philosophy to breadth-first: instead of finishing every shallow layer, it commits fully to one branch and follows it as deep as possible before ever looking elsewhere. It is implemented by storing its frontier in a last-in, first-out stack — like a pile of plates where you always take from the top.

• Newly generated paths are placed on top of the stack.
• The next path selected is whatever was added most recently.

Because DFS always grabs the newest candidate, it keeps pushing deeper and deeper down a single chain of choices — that is why we say it “commits to one branch.” It returns immediately if a selected state is a goal. Otherwise, the branch ends at a leaf or when the search rules reject further extensions. Then, because there are no newer alternatives left, the stack supplies an older option and the search backtracks: it selects an alternative route already saved on the stack. This is planning, not physical movement: no reverse action in the state graph is required.

The practical consequence is striking: DFS keeps only a small frontier. At any moment it needs to remember just the current branch plus a few sibling paths waiting higher in the stack — far less memory than BFS, which holds entire layers at once. This makes depth-first very appealing for problems where solutions lie deep and branching is wide.

However, DFS has real weaknesses you must weigh against that memory saving:

• Not generally optimal. It returns the first goal it stumbles upon down its chosen branch — which may be far more costly than another solution reached later. There is no guarantee of fewest steps or lowest cost.
• Vulnerable to infinite branches. If a branch keeps generating new descendants forever (possibly from repeated cycles, but even an acyclic infinite chain can do this), DFS can chase it indefinitely and never notice that a perfectly good goal lies on some other branch. Without care, an unbounded path makes DFS incomplete in practice.
• Sensitive to neighbor order. The order in which you insert a node’s children decides which one is explored first — and since DFS dives all the way down before backtracking, this choice can dramatically change how quickly (or whether) it finds a solution.

To see the ordering effect concretely: if we expand A with its three children B, C and D in that insertion order onto the stack, then because D was pushed last, D is selected first. The “most recent = next” rule means DFS starts by charging down whatever child came out of expansion most recently.

With the top written first, the course-tree stack evolves as follows: after A, [D, C, B]; after leaf D, [C, B]; after C, [J, I, H, B]; after leaf J, [I, H, B]. Each endpoint label abbreviates a complete path. B remains waiting throughout; DFS does not discard that alternative.

The interactive example in this section lets you follow depth-first search through its stack one step at a time, and it contains a lesson that often surprises newcomers. As you advance each frame, watch which path gets selected and compare it with the order the children were inserted onto the stack — remember DFS always takes the most recently added candidate.

Now try changing the goal to B. Here is what makes this instructive: even though B sits directly below the root — visually, one step away from where we started — depth-first search does not reach it quickly at all. Because of how children were pushed onto the stack (recall D was inserted last and so explored first), DFS charges off down other branches before ever coming back to B.

• This is a vivid demonstration that a visually nearby goal need not be reached quickly by DFS. “Nearby” in terms of depth or distance on the page has nothing to do with how soon DFS stumbles onto it; what matters is only where it happens to fall in the stack order and which branches get dived into first.
• It also reinforces a general truth about uninformed search: blind strategies follow their data structure’s discipline, not any sense of promise. BFS found B quickly because queue order put it early; DFS may find B late or last depending purely on insertion order.

Finally, make use of the Back and Reset controls in the example. They let you step backward to inspect each decision again — which branch was being explored, what the stack looked like at that moment — without having to reconstruct the whole frontier mentally yourself. Replaying these small traces is one of the best ways to build a genuine intuition for how depth-first search actually behaves.

This lab uses unit edge costs, so its reported solution cost equals edge count. With the default goal S, the route A → B → F → P → S has cost 4. The UCS lab uses the same tree topology with its supplied unequal edge weights, for which that route costs 1 + 6 + 2 + 3 = 12. The final exit-comparison lab applies the same weighted costs to every method.

A surprising and clarifying fact about breadth-first and depth-first search is that on many problems they can end up returning exactly the same goal path, even though they examined completely different portions of the tree to get there. The answer you receive is only half the story — how much searching was required to reach it is often what really matters.

• BFS spreads its effort across a whole layer. Before descending anywhere, it checks every node at one depth. Its work is wide: broad coverage of shallow regions first.
• DFS concentrates its effort along a single branch. It plunges down one route as far as possible before backtracking. Its work is deep and narrow, covering few paths but following them all the way to their ends.

So when you compare two search strategies, always evaluate both dimensions together: (1) what solution did it return, and (2) how much of the tree did it have to explore — and with what memory cost — in order to find that answer? A strategy might reach a good goal but only after wasting enormous effort; another might reach the same goal cheaply. Judging purely on “did it get the right path” misses most of the comparison.

Their contrasting memory behavior follows directly from this same distinction and is worth stating explicitly:

• BFS holds a wide collection of peers: waiting paths across a wide frontier, which may span adjacent depth levels as one layer generates the next. Its size can be enormous when branching is large.
• DFS mostly retains only alternatives alongside its current deep route — essentially one branch plus a handful of waiting siblings. Its footprint stays small because it commits to one path and retains the unselected siblings for later backtracking.

This is the core memory tradeoff of uninformed search, and it falls out naturally from how each strategy orders its work. Remembering this single contrast — wide-but-memory-hungry versus narrow-and-lean but order-sensitive — will help you predict which method suits which kind of problem before you even run them.

The storage comparison counts compact, parent-linked search records: each stores a state, a parent link and g, the path cost from the start; retain the incoming action too when the solution must specify actions. Following parent links from G to B to A, then reversing the sequence, reconstructs A → B → G. In the illustrated unit-plus-weight example, g is 0 at A, 2 at B and 3 at G.

b is the maximum number of children per node; m is the maximum search depth in edges. DFS retains O(bm) records: an asymptotic upper bound proportional to b × m, ignoring constant factors. IDS uses O(bd) records, where d is shallowest-goal depth. A global visited set consumes additional memory. The teaching labs also save full paths and earlier frames for rewind, so their actual storage is larger than these algorithmic frontier bounds.

Each depth-limited pass may use an explicit LIFO stack or recursive DFS with a depth counter. Restart the traversal for each new limit; an old global visited set must not prevent a state being reconsidered with a larger remaining depth allowance.

Iterative deepening search (IDS) is one of the cleverest ideas in basic search — it manages to get many of BFS’s best guarantees while using DFS’s tiny memory footprint. The trick is disarmingly simple: run depth-first search over and over, each time allowing slightly more depth.

• Round 1: allow only depth 0 (just the root). Check it, stop.
• Round 2: restart from the root, this time allowing paths down to depth 1.
• Round 3: restart again, now permitting depth 2. And so on — each round increasing the allowed depth limit by one.

The “iterative” part means we keep increasing the limit until we finally find a solution. Each new round is a fresh depth-limited DFS: whenever a branch tries to descend beyond the current limit, it is simply cut off there and DFS backtracks; if no goal was found and a deeper continuation was cut off, increase the limit and restart from the root. If the search was exhausted with no cutoff, return failure instead.

Why would anyone deliberately redo work they already did? Because the payoff is excellent:

• Tiny frontier like DFS: each individual round only ever keeps a small stack-sized collection in memory, so IDS avoids BFS’s huge-memory problem.
• BFS-like completeness and shallowest-first behavior: because we increase the depth limit gradually from zero, the first solution found is at the smallest depth that contains a goal. Under finite branching this guarantees IDS eventually reaches any finite-depth goal — making it complete in practice — while still finding the shallowest one.
• Cost-optimal for equal positive edge costs: if each move has the same cost, shallowest also means cheapest, so the first solution is optimal (just as with BFS).

There is a subtle but important implementation detail about knowing when to stop. When no goal is found, a depth-limited DFS round can end in two different ways:

1. Depth cutoff: it hit a node at the allowed limit whose deeper successors were not explored — meaning there may still be solutions just beyond this depth.
2. Exhausted search: every branch was fully explored and none reached a goal, so no solution exists at any depth.

Distinguishing these two cases is essential for correct termination: only when you know the space is genuinely exhausted (case 2) may you conclude there is no solution. A cutoff alone must never be treated as “no answer” — it merely says “try deeper next time.”

ℓ (ell) is the current depth limit; d is reserved for shallowest-goal depth in the memory bound, and b is maximum children per node. With finite branching and a goal at depth d, the depth-d pass can reach that goal. IDS guarantees fewest edges; it guarantees minimum total cost when all edges have the same positive cost. Positive but unequal edge costs alone are insufficient.

The interactive example for iterative deepening is best watched in a particular way: don’t just look at which node gets selected — keep one eye on the depth limit. That number controls everything about how far each round is allowed to go.

• A node that you saw visited in an earlier pass will very likely be visited again after the algorithm restarts with a larger limit. This repetition is not wasted or buggy — it is the whole point of iterative deepening, and it is completely intentional. Each new round revisits shallower states on its way to the newly reachable deeper region. How much extra work this creates depends on branching, child order and the position of the goal.
• In this particular course map, once the depth limit reaches four, our goal state becomes reachable for the first time — that is the moment IDS finally succeeds. Notice how much shallow re-exploration happened before that point; it all paved the way for reaching depth four.

Back restores the previous frame, including its frontier and depth limit. Reset starts the entire search again at limit 0. This lets you directly compare how much work was repeated at shallow depths versus the new deeper portion each round contributes.

• The key takeaway is a tradeoff worth internalizing now: IDS deliberately accepts redundant shallow exploration to keep memory small, and the amount of repetition depends on the tree. In a full, rapidly branching tree, the deepest level dominates the node count; that is the model used for the next section’s overhead calculation. That is precisely why IDS gets BFS-like completeness at DFS-like memory: it pays an extra time cost for repeated passes while avoiding a broad frontier. That cost need not be modest on every example.

When you watch this animation, try to articulate each step as “we are re-checking depth 2 with limit now 3” — doing so builds the mental model that IDS is not one search but a sequence of increasingly permissive DFS sweeps sharing one small stack.

The default goal is S, reached at depth 4. Changing the goal to B makes the depth-1 pass succeed; choosing Unreachable exhausts this finite example without a goal. The displayed depth limit is ℓ, the current pass’s allowed depth.

This lab uses unit edge costs, so its reported solution cost equals edge count. With the default goal S, the route A → B → F → P → S has cost 4. The UCS lab uses the same tree topology with its supplied unequal edge weights, for which that route costs 1 + 6 + 2 + 3 = 12. The final exit-comparison lab applies the same weighted costs to every method.

With goal S and the default child order, the lab selects 46 nodes across all IDS passes, counting repeated selections. BFS selects 19 and DFS 13. Each returns the same four-edge route under unit costs; these search-effort counts are separate from solution cost.

The slides compare exact node-visit counts on a full tree. b is children per non-leaf; d is maximum depth in edges. Here b = 10 and d = 3, and each pass runs in full, with no early goal stop. These numbers count search work, not route cost or simultaneous memory use.

The levels contain 1, 10, 100 and 1,000 nodes. One full traversal visits each once:

IDS runs at limits 0, 1, 2 and 3. The root is visited four times; depth 1 three times; depth 2 twice; depth 3 once:

For full trees with fixed b > 1 and increasing d, the total-work ratio (IDS visits divided by one-traversal visits) approaches b / (b − 1). The extra-work fraction is that ratio minus one, approaching 1 / (b − 1). Thus b = 10 gives about 11% extra work, while b = 2 approaches 100% extra work. The ratio is not itself an extra-work percentage.

A single chain is less favorable: its nodes do not concentrate in a large deepest layer, and repeating every prefix creates much more work relative to one traversal. IDS exchanges repeated visits for depth-first-sized frontier storage; the size of that tradeoff depends on the search space.

The selection rule in symbols

Read the first line as “choose a path q from frontier F whose accumulated cost is smallest, and call it p.” arg min returns a minimizing path; min would return the numerical cost. If paths tie, use a fixed tie-breaking rule. The second line updates the whole-path cost by adding the new edge. The priority queue is ordered by this sum, not by the last edge weight alone.

Lowest-cost-first search — also called uniform-cost search — answers the question neither BFS nor DFS addresses well: what if we actually care about minimizing total cost, not just steps? Its rule is beautifully simple:

To implement this, the frontier’s arrival-order data structure is replaced by a priority queue, which always hands back whichever candidate has the lowest current total cost — regardless of when it arrived. Accumulated cost determines the primary priority. Depth does not determine it, while insertion order may still break ties between equal-cost paths.

A subtle but crucial detail concerns when we test for the goal. Lowest-cost-first tests a path’s endpoint as a goal only at the moment that path is selected, not when it is generated. Why? Because an expensive route to the goal might be discovered early, while a cheaper route still waiting in the frontier could appear later.

If we accepted the first-generated goal immediately, we might stop at an expensive solution when a better one was just around the corner. Testing the goal on selection lets cheaper waiting paths be considered first; nonnegative costs make this stopping rule safe.

The optimality guarantee — that lowest-cost-first returns the minimum-cost path — rests on assumptions you should know precisely:

• Nonnegative edge costs: if any cost could be negative, a currently expensive partial path could become cheaper after a negative-cost edge and reasoning breaks down. Nonnegativity supports the standard optimality argument.
• Correct handling of duplicate states (graph search): when several paths reach the same state by different routes, we track the cheapest known cost for that state and preserve any improvement. Retaining obsolete entries can waste work, but discarding a later cheaper route can lose the optimal solution. Without this — using unrestricted tree search even on a finite graph — you can chase infinitely many zero-cost-cycle paths forever.
• Termination in infinite spaces: if the space is unbounded, we need an extra condition to guarantee termination — for example, that every edge cost has a strictly positive lower bound (so each step adds at least some fixed minimum) combined with finite branching and a goal of finite total cost. Only finitely many paths can then remain below a finite solution cost, so endlessly cheap continuations cannot postpone the goal forever.

In short: lowest-cost-first is the go-to uninformed method when edge costs differ and you want genuinely minimal cost — as long as its assumptions (nonnegative, correctly deduplicated, terminating) are met.

The stopping, improvement and termination examples

For the selection equation, q is a candidate path in frontier F, g(q) its total cost, and p the selected path. In the update equation, v is the next vertex, end(p) the current endpoint and ω_E(end(p), v) the next edge’s cost.

In the stopping example, A → G costs 9, while A → B → G costs 2 + 1 = 3. Expanding A discovers a goal at cost 9, but UCS selects B at cost 2 first. Its cheaper route to G is then selected at cost 3. The state label G here names the goal, rather than the graph.

In the duplicate example, A → X costs 8; A → B → X costs 3. state is a route’s endpoint, new_g the candidate route cost and best_g[state] the lowest cost discovered for that state. Brackets retrieve its saved entry. The cheaper route updates best_g[X] from 8 to 3 and the parent of X from A to B. If X → G costs 2, the improved solution costs 5. Replace or reinsert the improved record and skip obsolete entries when selected.

For termination, a goal costing 1 can wait forever beside an infinite A → B → C → D → … chain of zero-cost edges: every selected free path generates another. The states are distinct, so duplicate checks cannot remove the chain. On a finite graph, nonnegative costs plus best-cost duplicate handling prevent endless repetitions. In an infinite space, finite branching, a finite-cost reachable goal, and one fixed positive lower bound ε > 0 on every edge cost suffice. ε (epsilon) names that bound. Merely requiring every edge to be positive is weaker and does not suffice if costs shrink toward zero.

The interactive example for lowest-cost-first search rewards careful reading of the cost labels — and there is one mistake beginners make constantly: read the cost attached to the whole path, not just to the most recent edge. The number that decides selection in a priority queue is the cumulative total spent so far along that entire route (g), never merely the last step’s weight.

Try this specific experiment in the example: compare the accumulated costs of two candidate paths, A–C–H and A–B–F. Read the frontier display: A–C–H costs 2 + 1 = 3, while A–B–F costs 1 + 6 = 7. Of these two candidates, the path to H has priority. The whole point of this comparison is to separate a low-cost route from merely a short route:

• A–C–H and A–B–F both have exactly two transitions, yet their cumulative costs differ.
• What matters is their total expenditure. One of them will come out cheaper overall, and the priority queue ranks purely on that sum.

The deeper lesson generalizes immediately: with unequal edge weights, a path containing more transitions can still deserve priority, simply because its cumulative cost so far happens to be smaller. Two moves across cheap edges may beat one move across an expensive edge. This is exactly the distinction that lowest-cost-first captures and that step-counting methods (BFS) would miss.

• So whenever you inspect any search animation, force yourself to track accumulated totals rather than counting steps or glancing at the last label. Doing so builds the habit needed not just for uniform-cost search but also for A*, which we meet in Part 2 and which builds directly on this idea of scoring whole paths.

Take a moment with Back/Reset to step through both routes side by side: watching their running totals grow is the clearest way to internalize that it is the total, not the last edge, that drives selection here.

You now have four uninformed methods at your disposal: breadth-first, depth-first, iterative deepening and lowest-cost-first. Rather than memorizing each one as an isolated fact, the best way to remember them is by the single question each strategy asks of its frontier:

• Breadth-first → oldest (queue). Guarantee: fewest edges and completeness with finite branching and a finite-depth goal; minimum cost for equal positive edge costs.
• Depth-first → newest (stack). Small frontier with parent-linked records; no optimality guarantee, and an infinite branch may prevent success.
• Iterative deepening → shallow-enough-for-this-limit. Fewest edges with finite branching and a finite-depth goal, using DFS-sized frontier storage; minimum cost for equal positive edge costs.
• Lowest-cost-first → cheapest-so-far (priority queue). Minimum weighted cost under nonnegative costs, sound duplicate handling and the stated termination conditions.

Framing each method as “what question does it ask?” makes its behavior and guarantees follow naturally, instead of requiring you to memorize a list of properties for each name.

A practical implementation note about memory: when we say “a path is stored,” the naive approach copies the entire sequence on every extension — which bloats storage. A much better technique stores each node with only a link back to its parent. The full path can then be reconstructed by walking backward from any node, and extending it costs just one small record rather than copying all previous states. All memory estimates you see assume this efficient parent-linked representation.

Finally, choosing among these methods should start from what your task actually values, asked up front:

1. Do you need the solution with minimum steps? → BFS or iterative deepening.
2. Do you need minimum weighted cost (edges have different prices)? → lowest-cost-first.
3. Is any feasible solution enough, and memory is tight? → depth-first (with care about infinite branches).

Matching the method to the goal’s objective — steps vs. cost vs. merely existence — is the single most useful habit you can take from this lecture.

Use this final experiment to test a choice: does the task require the fewest steps or the lowest total cost? Run the same problem with BFS and lowest-cost-first, predicting the exit before each run. Keep the graph and goals fixed so the comparison isolates the selection rule.

• The map has three exits that all satisfy the goal condition — so there is no question of “does a solution exist?” Here every strategy succeeds; what differs is which acceptable route each one returns, and how much work precedes it. When all goals are equally valid, quality (cheapest) versus convenience (fewest steps or quickest find) becomes the real battleground.

A striking concrete example of why step-counting can mislead: BFS may prefer a two-edge route that costs 9 over a three-edge route that costs only 6. Because BFS (with equal-cost edges assumption aside) cares about the number of transitions, it will find and return the shallowest exit — even if that “shorter” route is actually more expensive in real cost. Uniform-cost search would instead pick up the cheaper three-edge option.

For an optional preview of Part 2, notice how the additional selection rules differ in what signal they use:

• Greedy search (a preview of informed methods) emphasizes an estimate of what remains — it reaches toward where it thinks the goal is, ignoring what has already been paid.
• Uniform-cost and A*, by contrast, incorporate the amount already spent along each path. A* adds on top of that a remaining-distance estimate; uniform-cost uses only the cost so far.

The most valuable way to study this example is to compare two things at once: (1) the final solution each algorithm returns, and (2) the whole sequence of frontier selections leading up to it. Two algorithms can return an identical route while having explored very differently — or reach different goals with similar-looking behavior. Seeing both dimensions together reveals that a search strategy is defined by its entire pattern of exploration, not just its endpoint.

The shared lab gives BFS the route A → B → G1 (2 edges, cost 1 + 8 = 9); UCS returns A → C → D → G2 (3 edges, cost 2 + 2 + 2 = 6). Both slides and handout run the same engine and data. In the optional modes, g is cost from the start, h is estimated remaining cost and f = g + h is estimated total cost. Greedy returns A → E → G3 at cost 12 here; A* returns the cost-6 route. These two modes are previews for Part 2.

The numbers on edges are individual step costs. The frontier’s g value and returned solution cost add those weights even in BFS mode here; BFS still selects by queue order rather than by those costs.

You now have a complete toolkit of uninformed search strategies. Before moving to informed (heuristic) methods in the next lecture, check that you can explain three core ideas:

• Represent a task using states, actions, a goal and costs. Turn any planning problem into search by defining what matters about each situation (the state), which moves are legal (actions/transitions), when you have finished (goal condition), and how much effort each move demands (edge costs). A solution is then simply a path whose endpoint meets the goal, with its quality measured by cumulative cost g.
• Explain the difference between queue and stack exploration. A first-in-first-out queue always selects the oldest waiting path, producing breadth-first sweeping that completes each shallow layer before descending — complete and fewest-edge but memory-hungry. A last-in-first-out stack always grabs the newest path, diving deep along one branch with a tiny footprint, but it is order-sensitive and not optimal.
• Choose an uninformed method using the costs and memory available. If your edges all cost the same and you want fewest steps cheaply in memory → iterative deepening. If edges differ in price and you truly need minimum weighted cost → lowest-cost-first (with nonnegative costs, sound duplicate handling and the stated termination conditions). If any solution is acceptable and frontier memory is scarce → depth-first, while accounting for cycles, infinite branches and sensitivity to child order. DFS does not guarantee a fast answer.

Now choose one of these ideas and explain it in your own words using an example from this part — perhaps how BFS prefers a 2-edge route costing 9 over a cheaper 3-edge route, why DFS finds the visually nearby goal late, or how IDS re-walks shallow layers to save memory. Teaching it back is the surest way to confirm you have truly understood search.