Unit 3 Wrap-Up and Self-Assessment

Unit 3: Search Techniques for Problem Solving — Wrap-Up

Search is AI’s universal problem-solving engine. By formulating a problem as a state space — defining states, actions, transition model, goal test, and path cost — any goal-directed task becomes a graph to be explored. The choice of algorithm determines whether that exploration is complete, optimal, and computationally feasible. A good heuristic transforms a slow, exhaustive search into a focused, efficient one.

Key Takeaways

Problem formulation is everything. How you define states and actions determines the size of the search space and which algorithms are practical.
Uninformed algorithms differ only in frontier management. BFS uses a FIFO queue (shallowest first); DFS uses a LIFO stack (deepest first); UCS uses a priority queue ordered by g(n).
ID-DFS bridges BFS and DFS. It achieves BFS completeness and optimality at DFS memory cost — usually the best choice when the search space is large and depth is unknown.
Heuristics transform search. A* with a good admissible heuristic explores exponentially fewer nodes than uninformed search.
Admissibility is non-negotiable for A* optimality. An inadmissible heuristic may find solutions faster on average but loses the guarantee of finding the best one.
Real applications use these algorithms. GPS navigation, robotics, puzzle solving, and network routing all rely on variants of BFS, UCS, and A*.

Complete Algorithm Comparison Matrix

Algorithm	Complete	Optimal	Time	Space	When to Use
BFS	Yes	Yes^a	O(b^d)	O(b^d)	Shallow solutions, uniform costs, ample memory
DFS	No^b	No	O(b^m)	O(b·m)	Any solution acceptable, very limited memory
DLS	No^c	No	O(b^ℓ)	O(b·ℓ)	Known solution depth bound
ID-DFS	Yes	Yes^a	O(b^d)	O(b·d)	Large spaces, unknown depth, limited memory
UCS	Yes	Yes	O(b^⌈C*/ε⌉)	O(b^⌈C*/ε⌉)	Variable action costs, no heuristic available
Greedy	No^b	No	O(b^m)	O(b^m)	Approximate solutions, real-time constraints
A*	Yes	Yes^d	Exponential	Exponential	Optimal + efficient, good admissible h(n) available

Algorithm

Complete

Optimal

Time

Space

When to Use

BFS

Yes

Yes^a

O(b^d)

Shallow solutions, uniform costs, ample memory

DFS

No^b

O(b^m)

O(b·m)

Any solution acceptable, very limited memory

DLS

No^c

O(b^ℓ)

O(b·ℓ)

Known solution depth bound

ID-DFS

Yes

Yes^a

O(b^d)

O(b·d)

Large spaces, unknown depth, limited memory

UCS

Yes

O(b^⌈C*/ε⌉)

Variable action costs, no heuristic available

Greedy

No^b

O(b^m)

Approximate solutions, real-time constraints

Yes

Yes^d

Exponential

Optimal + efficient, good admissible h(n) available

^a Optimal when all action costs are equal.
^b Complete with graph search on finite state spaces.
^c Complete only if solution is at depth ≤ ℓ.
^d Optimal when h(n) is admissible.

Unit 3 Glossary

State Space: The complete set of states reachable from the initial state by any sequence of actions. Defines the "world" the search algorithm explores.
Initial State: The state in which the agent begins searching.
Goal Test: A function that determines whether a given state satisfies the problem’s objective.
Path Cost: A numeric measure of the cost of a sequence of actions. Used by UCS and A* to prefer cheaper solutions.
Transition Model: A function that, given a state and an action, returns the resulting state.
Frontier: The set of nodes that have been generated but not yet expanded. Different data structures for the frontier define different algorithms.
Explored Set: The set of states already expanded in graph search. Prevents re-expansion of visited states.
BFS (Breadth-First Search): Expands shallowest node first using a FIFO queue. Complete and optimal for uniform costs; memory-intensive.
DFS (Depth-First Search): Expands deepest node first using a LIFO stack. Memory-efficient but neither complete nor optimal in general.
UCS (Uniform-Cost Search): Expands node with lowest g(n) first using a priority queue. Complete and optimal for variable costs.
ID-DFS (Iterative Deepening DFS): Runs DLS with increasing depth limits. Combines BFS completeness/optimality with DFS memory efficiency.
Heuristic Function h(n): An estimate of the cost from state n to the nearest goal. Guides informed search algorithms toward the goal.
Greedy Best-First Search: Expands node with lowest h(n). Fast but not optimal.
A* Search: Expands node with lowest f(n) = g(n) + h(n). Complete and optimal when h is admissible.
Admissible Heuristic: A heuristic that never overestimates the true cost to the goal: h(n) ≤ h*(n). Required for A* optimality.
Consistent (Monotone) Heuristic: A heuristic satisfying h(n) ≤ c(n, a, n') + h(n') for all n, a, n'. Implies admissibility; enables more efficient A* graph search.
Dominance: h₂ dominates h₁ if h₂(n) ≥ h₁(n) for all n (both admissible). A* with the dominant heuristic expands fewer nodes.
Relaxed Problem: A version of the original problem with some constraints removed. Used to derive admissible heuristics systematically.

Self-Assessment Quiz

Test your mastery of Unit 3 concepts with the chapter-level self-check.

Looking ahead: Unit 4 — Optimization and Constraint Satisfaction

The algorithms in this unit search for paths through a state space. But many real problems do not ask for a path — they ask for a configuration that satisfies a set of constraints. Scheduling, circuit board layout, map coloring, and Sudoku are all problems of this kind.

Unit 4 introduces two complementary approaches:

Local search (hill climbing, simulated annealing): searches for the best state rather than the best path
Constraint satisfaction problems (CSPs): uses constraint propagation and backtracking to find assignments that satisfy all constraints simultaneously

The uninformed and informed search concepts you learned this week carry directly forward — backtracking search is a form of DFS, and heuristics (like Minimum Remaining Values) play the same guiding role.

Begin Unit 4: Optimization and Constraint Satisfaction →

Based on the UC Berkeley CS 188 Online Textbook by Nikhil Sharma, Josh Hug, Jacky Liang, and Henry Zhu, licensed under CC BY-SA 4.0.

This work is licensed under CC BY-SA 4.0.