Search algorithms · Part 1
Model a search problem, then compare exploration rules that do not use an estimate of the remaining distance.
Build the model, understand the loop, then change how it chooses the next path.
First define what counts as a solution. Then choose how to explore—and which quality guarantee you need.
A robot must deliver a parcel. Its state describes the situation; search finds a sequence of actions.
Is the parcel delivered?
Several robot locations may satisfy the same goal.
A real robot might minimize energy; distance is a proxy only under suitable assumptions.
A solution is a legal action sequence from the initial state to any state satisfying the goal test.
Two robots stand at the customer’s door. Can both take the “deliver” action?
Parcel is still at the depot.
Deliver is not a legal action.
Parcel is ready to hand over.
Deliver is a legal action.
The state must distinguish situations with different legal actions or outcomes.
Apply the robot’s lesson elsewhere: keep the information that changes what can happen next.
Current intersection.
For a simple map, it determines which roads are available.
Objective: minimum travel time.
Current city and visited-city set.
We must know which cities remain.
Objective: minimum total fare.
Position and keys held.
Being at the door is not enough to open it.
Goal: complete the game’s tasks.
A state is a task-specific description, not just a location.
G is the graph: the pair G = (V, E).
V is its set of vertices (states).
E is its set of directed edges (legal moves).
A successor function generates legal transitions only when a state is expanded.
(depot, at depot)
Check action preconditions.
Compute the resulting states and costs.
Pick up → (depot, carried), cost 1.
Move → (customer, at depot), cost 1.
Generating a graph on demand saves upfront storage; it does not remove the growth in possible paths.
Start at A. Reach D.
A → B → D 1 + 5 = 6
A → C → D 10 + 8 = 18
Equal edge counts can hide very different costs.
The same A → B → D example, now written as a mathematical object.
p is the path; k is its number of vertices.
vᵢ is the vertex at position i, from 1 to k.
⟨…⟩ means an ordered sequence.
Each vᵢ is in V; each consecutive pair (vᵢ, vᵢ₊₁) is in E, for i = 1, …, k − 1.
vₛ is the start vertex; vG is the goal vertex.
A solution has v₁ = vₛ and vₖ = vG.
G is the graph; V its vertices; E its edges.
ωE (omega) maps each edge to its cost.
ℝ is the set of real numbers.
Example: ωE(A, B) = 1 prices A → B at 1.
g(p) is the total cost of path p.
∑ adds the edge costs for i = 1 to k − 1.
A path with k vertices has k − 1 edges. For p = ⟨A, B, D⟩: k = 3 and g(p) = 1 + 5 = 6. The start-only path has cost 0.
DAG = directed acyclic graph. A rooted tree is a more restricted case.
Two routes to D; no directed route loops back.
For a path ⟨v₁, …, vₖ⟩, k counts vertices; v₁ is the first and vₖ the last.
No legal path with k ≥ 2 has v₁ = vₖ: it cannot return to its start.
The underlying undirected graph is connected and has no cycle.
The vertex r is the root: it reaches every vertex along the arrows.
A DAG may merge branches. In a rooted tree, there is exactly one directed path from the root to each vertex.
One root. One path from the root to every node.
Next: distinguish a loop on one route from a state reached by two routes.
The same state can reappear on one route, or on two different routes.
A → B → A
A already occurs on this route.
Reject this cyclic extension.
A → B → X
A → C → X
Both reach X, but neither route loops.
Cycle checking prevents loops. Reusing work across routes needs extra memory and a strategy-specific rule.
After exploring A, suppose B, C and D are available next. Keep all three possibilities.
Choosing one route now must not lose the others.
⟨A,B⟩ records how we reached B, so we can return a complete route later.
The frontier contains unfinished candidates. It is not the list of states already explored.
Use the waiting list to explore one candidate at a time.
| Step | What to do |
|---|---|
| 1 · Initialize | Put only the start path ⟨A⟩ in the frontier. |
| 2 · Select | Choose and remove one waiting path. |
| 3 · Test | If its endpoint is a goal, return this path as the solution. |
| 4 · Expand | Otherwise, extend the path to each legal successor. Add these extended paths to the frontier. |
| 5 · Repeat | Repeat steps 2–4. If the frontier is empty, return failure. |
Step 2 defines the search strategy: choosing a different waiting path changes the order of exploration.
Input: graph G, with vertices V and edges E; start vertex vₛ and goal vertex vG. Output: a path, or failure.
F ← {⟨vₛ⟩}
while F ≠ ∅:
p ← select(F)
F ← F ∖ {p}
if end(p) = vG: return p
F ← F ∪ {p ⊕ v : (end(p), v) ∈ E}
return failureF: frontier of waiting paths
p: the path selected from F
v: a legal next vertex after p
select(F): choose a path using the strategy
end(p): the last vertex of p
←: assign · ∅: empty collection
∖ {p}: remove p · ∪: add candidates
p ⊕ v: append vertex v to path p
∈: belongs to; (end(p), v) ∈ E requires a legal edge to v.
Test the selected endpoint before extending it. The selection rule changes; the path and goal definitions stay the same.
Use the course tree. Suppose the oldest waiting path is selected next; B has children E, F and G.
| Operation | Frontier · next first |
|---|---|
| Before selection | ⟨A,B⟩ · ⟨A,C⟩ · ⟨A,D⟩ |
| Select ⟨A,B⟩ | ⟨A,C⟩ · ⟨A,D⟩ |
| Test B: not a goal | ⟨A,C⟩ · ⟨A,D⟩ |
| Expand B; add its extensions | ⟨A,C⟩ · ⟨A,D⟩ · ⟨A,B,E⟩ · ⟨A,B,F⟩ · ⟨A,B,G⟩ |
B was selected and expanded. E, F and G are discovered, but still waiting.
Will it find a solution whenever one exists?
Will it return a minimum-cost solution?
How much search must it perform?
How many search records must it retain?
Every guarantee depends on assumptions about the graph, costs and implementation.
Choose systematically, using arrival order,
depth or cost already paid.
Breadth-first search (BFS) uses a first-in, first-out queue—like a checkout line.
Remove a path from the front.
Add its extensions to the back.
Front → ⟨A,B⟩ · ⟨A,C⟩ · ⟨A,D⟩
Select B; its children join behind C and D.
In the lab, watch the queue: new deeper paths wait behind the shallower paths already there.
Predict: after A, B, C and D, which node is selected? Try goal B as well as S.
Unit step costs: the returned cost equals the number of edges.
The lab completed each shallow layer before moving deeper. Queue order explains why.
Select the start state.
Select all one-edge paths before the two-edge paths they generate.
d is the number of edges from the start.
The first selected goal cannot have a shallower goal still waiting.
With finite branching, BFS eventually reaches a finite-depth goal; no shallower goal was skipped.
Fewest edges does not necessarily mean lowest total cost.
Fewest steps means minimum cost only when each step has the same positive cost.
Depth-first search (DFS) uses a last-in, first-out stack—like a pile of books.
Remove the path on top.
Put its extensions on top.
Push B, then C, then D.
Top → ⟨A,D⟩ · ⟨A,C⟩ · ⟨A,B⟩
D is selected next.
In the lab, set the goal to B. Does a one-edge-away goal necessarily get selected quickly?
Predict the first four selections. Then set goal B and compare with BFS.
Unit step costs: the returned cost equals the number of edges.
Use the course tree: push A’s children in the order B, C, D. The top is shown first.
| Selected | Stack after expansion · next first | Reason |
|---|---|---|
| A | D · C · B | D was pushed last. |
| D | C · B | D is a leaf; it adds nothing. |
| C | J · I · H · B | C’s new children go above the old B. |
| J | I · H · B | Another leaf: pop the next alternative. |
The stack remembers where to try next. A recursive DFS uses the function-call stack for the same purpose.
BFS: finish shallow layers. DFS: follow one branch; no shortest-path guarantee, and an infinite branch can postpone a goal forever.
In a full tree, b, the branching factor, is the number of children per non-leaf. d is depth: the number of edges from the root.
bᵈ means b multiplied by itself d times. Each added depth level multiplies the node count by b.
A, B and G label states. Each record stores g (its total path cost from the start), and a link to its parent record.
State: A
Parent: none
g = 0
State: B
Parent: record A
g = 2
State: G
Parent: record B
g = 3
One extension needs one new record, not a copied route. The memory comparisons use this representation.
The main memory difference is how many unfinished alternatives stay live.
Keep the waiting paths across a wide layer.
The queue may span adjacent levels; storage grows exponentially with depth.
b is the maximum number of children per node; m is the maximum depth in edges.
Keep the branch and its waiting siblings.
O(bm) is an upper bound on record-count growth, proportional to b × m, ignoring constant factors.
Can we keep DFS-sized storage and still find a shallowest goal? This motivates iterative deepening.
Each depth-limited pass needs to distinguish three outcomes.
A selected state is a goal.
Return the solution.
Some legal continuation was stopped by the current depth limit.
Try a larger limit.
No goal and no deeper continuation remains under the search rules.
Stop: no solution.
Do not carry a simple “visited forever” set across passes: shallow visits must not block deeper exploration.
Watch the limit change from 0 to 4. Back restores the previous depth limit.
Unit step costs: the returned cost equals the number of edges.
We count node visits (search work), not edge costs. Assume every pass runs in full.
These are the nodes at depths 0, 1, 2 and 3. One full traversal visits each node once.
IDS restarts at limits 0, 1, 2 and 3: the root is visited 4 times, depth 1 3 times, depth 2 twice, and depth 3 once.
b = children per non-leaf node;
d = maximum depth in edges.
One pass through depth 3:
1111 node visits
Deepening through limits 0–3:
1234 node visits
123 extra visits: about 11% more work.
Most nodes are at the deepest level, which IDS visits only once. A long single chain is a less favorable case.
Lowest-cost-first, also called uniform-cost search (UCS), orders the frontier by g, the total cost of a path from the start.
Always remove the path with the smallest g.
For an extension: new g = old g + edge cost.
A → C → H: 2 + 1 = 3
A → B → F: 1 + 6 = 7
The path to H has priority.
The smallest last edge is not enough: sum the whole path. Next, decide when a discovered goal is safe to accept.
Here A, B and G label states; G is the goal. g is total path cost from start A. Expanding A discovers G at cost 9 and B at cost 2.
| Select by minimum g | Frontier / result |
|---|---|
| A, g = 0 | B: 2 · G: 9 |
| B, g = 2 | G: 3 replaces G: 9 |
| G, g = 3 | Return A → B → G. |
For UCS, accept a goal when its cheapest waiting path is selected—not when the goal is first generated.
Predict the next selected path, then run to goal S. g is total path cost from the start; numbers on edges are individual step costs.
A, B, X and G are state labels. A → X costs 8; A → B → X costs 2 + 1 = 3. g is total path cost from start A.
best_g[X] = 8
Parent of X = A
new_g = 3 < best_g[X] = 8
Update the record and parent.
If X → G costs 2,
the improved solution costs 5.
With nonnegative costs, UCS finalizes a state’s best g on selection, not on first discovery.
Uniform-cost search (UCS) selects the cheapest waiting path—even when a goal is already in the frontier.
| After expanding | Waiting paths · total cost |
|---|---|
| A | A → B: 0 | A → Goal: 1 |
| B | A → B → C: 0 | A → Goal: 1 |
| C | A → B → C → D: 0 | A → Goal: 1 |
Every selected free path creates another free path. The goal is never selected.
With nonnegative costs, keep a new route to a state only if it improves the best known cost. Zero-cost loops then stop adding copies.
Require finitely many next moves per state and one fixed positive lower bound ε > 0 on every step cost; ε (epsilon) names that bound. For example, if each step costs at least 1, detours cost at least 1, 2, 3, …
With these safeguards, only finitely many candidates can come before the goal. UCS eventually selects it.
| Method | Select by | Solution guarantee | Frontier memory |
|---|---|---|---|
| BFS | Oldest path | Fewest edges | Exponential in depth |
| DFS | Newest path | Any solution, if it terminates | Linear in depth* |
| IDS | DFS, increasing limit | Fewest edges | Linear in depth* |
| UCS (Lowest-cost-first) | Minimum g · total path cost | Least cost** | Can be exponential |
* For fixed branching and parent-linked records. ** Under the cost and termination assumptions discussed.
Compare BFS and lowest-cost-first: predict the exit, then record steps and cost.
g = cost from the start. In the optional Part 2 modes: h = estimated remaining cost; f = g + h = estimated total cost.
Choose one idea and explain it in your own words. Use an example or an interactive experiment to support your explanation.
AIML 2025/26 · Lesson 01 — Search
Content sequence, six original interactive examples, course-tree topology, edge costs and heuristic values.
Search strategies, heuristic conditions and pruning.
Adaptation notes, complete slide notes and source mapping are included in the notes folder.
The interactive slides run locally; the gallery and PDF are static review copies.
Lecture 03 · Search algorithms · Part 1