Uninformed & Systematic Search — BFS · DFS · Uniform-Cost · A*
⚠️ Context for Methods of AI. These classical search algorithms are not their own lecture session in Methods of AI — they are assumed prerequisite knowledge. They appear only as (a) the contrast to Local Search (Session 02 keeps just the current state; classical search keeps the whole path) and (b) the search engine used by Classical Planning in STRIPS (Planning I). This note exists so the terms are defined once, properly — because the vault previously only mentioned them in passing.
The core idea
Classical (systematic) search looks for a path from an initial state to a goal state. Unlike local search, the path itself is the solution, and the algorithm keeps a frontier (the set of generated-but-not-yet-expanded nodes).
The single thing that changes between algorithms is the data structure of the frontier. Everything else (generate successors, check goal) is the same.
The four algorithms
Breadth-First Search (BFS) — frontier = FIFO queue. Expands the search tree layer by layer: all nodes at depth 1, then depth 2, … First-in-first-out, so the shallowest node is always expanded next.
- ✅ Complete (finds a solution if one exists, for finite branching).
- ✅ Optimal if all step costs are equal (the shallowest goal = fewest actions).
- ⚠️ Memory-hungry: must store the entire frontier →
O(bᵈ)time and space.
Depth-First Search (DFS) — frontier = LIFO stack. Goes as deep as possible down one branch before backtracking.
- ✅ Low memory: only stores the current path →
O(b·m)space. - ❌ Not complete on infinite/looping spaces (can descend forever) unless cycles are tracked.
- ❌ Not optimal — returns the first goal found, not the shallowest.
Uniform-Cost Search (UCS) — frontier = priority queue ordered by path cost g(n). Always expands the cheapest-so-far node. This is Dijkstra’s algorithm.
- ✅ Optimal for varying (non-negative) step costs — the case BFS can’t handle.
A* — the informed extension. Priority queue ordered by f(n) = g(n) + h(n), where g = cost so far and h = a heuristic estimate of the remaining cost to the goal.
- ✅ Optimal if
his admissible (never overestimates) for tree-search, or consistent for graph-search. - A* = “UCS guided by a heuristic” → explores far fewer nodes than BFS/UCS when
his good.
Comparison
| Algorithm | Frontier | Complete? | Optimal? | Time | Space | Informed? |
|---|---|---|---|---|---|---|
| BFS | FIFO queue | ✅ | ✅ (equal step cost) | O(bᵈ) | O(bᵈ) | ❌ |
| DFS | LIFO stack | ❌ (infinite spaces) | ❌ | O(bᵐ) | O(b·m) | ❌ |
| Uniform-Cost | priority queue (g) | ✅ | ✅ (any non-neg cost) | O(b^⌈C*/ε⌉) | high | ❌ |
| A* | priority queue (g+h) | ✅ | ✅ (admissible h) | depends on h | high | ✅ |
b = branching factor · d = depth of shallowest solution · m = max depth · C* = optimal cost · ε = min step cost.
Why it matters in Methods of AI
- Planning I (STRIPS): the forward-search planner uses BFS over world states → it returns the shortest plan (fewest actions). With A* + a relaxation heuristic (e.g. Ignore-Delete) the planner prunes most of the state space and scales far better — see the forward state-space search tree figure in STRIPS.
- vs. Local Search (Search Algorithms): systematic search keeps the path and frontier (complete, can prove optimality / infeasibility); local search keeps only the current state (fast, scalable, but incomplete — can’t prove there is no solution).
- vs. CSP backtracking: backtracking is essentially DFS over partial assignments, with constraint propagation pruning the branches.
Common exam framing ⚠️
- BFS finds the shortest path only when all step costs are equal — otherwise you need Uniform-Cost / Dijkstra.
- DFS trades completeness/optimality for memory.
- A* is optimal only with an admissible (or consistent) heuristic — an overestimating heuristic breaks optimality.
See also
- Search Algorithms — Local Search hub (the contrast: current-state-only methods)
- STRIPS — Classical Planning, which uses BFS/A* as its search engine
- Constraint Satisfaction Problems — backtracking = DFS + pruning
- Methods of AI Lecture · Methods of AI MOC