Suppose you are in Dhaka and want to reach Chattogram using a road map, but you have no idea which direction Chattogram lies. You can only look at which cities are connected. How do you systematically find a route? This is uninformed (or blind) search, and it is the foundation on which all smarter search algorithms are built.
Formulating a search problem#
A search problem consists of:
- A set of states $S$ and an initial state $s_0$.
- A set of actions $A(s)$ available in each state.
- A transition model $\text{Result}(s, a)$ giving the next state.
- A goal test $\text{IsGoal}(s)$.
- An action cost function $c(s, a, s')$.
A solution is a sequence of actions from $s_0$ to a goal; an optimal solution has the lowest total cost. The states and transitions implicitly define a graph — often astronomically large (the 15-puzzle has about $10^{13}$ reachable states), so we generate it lazily.
The general algorithm#
All search algorithms maintain a frontier of nodes waiting to be expanded and (in graph search) a reached set to avoid repeated states. They differ only in which node to expand next.
from collections import deque
import heapq
def breadth_first_search(start, goal, neighbors):
frontier = deque([start])
parent = {start: None}
while frontier:
s = frontier.popleft()
if s == goal:
return reconstruct(parent, s)
for t in neighbors(s):
if t not in parent: # early goal test variant is also common
parent[t] = s
frontier.append(t)
return None
def uniform_cost_search(start, goal, neighbors_with_cost):
frontier = [(0, start)]
best = {start: 0}
parent = {start: None}
while frontier:
g, s = heapq.heappop(frontier)
if s == goal:
return g, reconstruct(parent, s)
if g > best[s]:
continue # stale queue entry
for t, c in neighbors_with_cost(s):
if g + c < best.get(t, float("inf")):
best[t] = g + c
parent[t] = s
heapq.heappush(frontier, (g + c, t))
return None
def reconstruct(parent, s):
path = []
while s is not None:
path.append(s)
s = parent[s]
return path[::-1]Measuring search algorithms#
We judge a strategy on four criteria, using $b$ = branching factor, $d$ = depth of the shallowest goal, $m$ = maximum depth, $C^*$ = optimal cost, and $\epsilon$ = the minimum action cost.
| Strategy | Complete? | Optimal? | Time | Space |
|---|---|---|---|---|
| Breadth-first (BFS) | Yes (finite $b$) | Yes if costs equal | $O(b^d)$ | $O(b^d)$ |
| Uniform-cost (UCS) | Yes if $\epsilon > 0$ | Yes | $O(b^{1+\lfloor C^*/\epsilon \rfloor})$ | same |
| Depth-first (DFS) | No (infinite paths) | No | $O(b^m)$ | $O(bm)$ |
| Depth-limited | No | No | $O(b^\ell)$ | $O(b\ell)$ |
| Iterative deepening (IDS) | Yes | Yes if costs equal | $O(b^d)$ | $O(bd)$ |
| Bidirectional | Yes | Yes (with care) | $O(b^{d/2})$ | $O(b^{d/2})$ |
Breadth-first search#
Expands the shallowest node first using a FIFO queue. It finds the shortest path in number of steps. Its weakness is memory: with $b = 10$ and $d = 10$, BFS stores roughly $10^{10}$ nodes — far beyond typical RAM.
Uniform-cost search#
Expands the node with the smallest path cost $g(n)$ using a priority queue. It is exactly Dijkstra's algorithm, adapted to stop at the goal. It is optimal for any non-negative costs.
Depth-first search#
Expands the deepest node first (a LIFO stack or recursion). Its memory is only linear in depth, which is its great virtue, but it can wander down infinite branches and returns whatever solution it finds first.
Iterative deepening search#
Runs depth-limited DFS with limits $0, 1, 2, \dots$ until a goal is found. It seems wasteful to regenerate the upper levels repeatedly, but the total cost is dominated by the last level:
For $b = 10, d = 5$, IDS generates 123,450 nodes versus 111,110 for BFS — only about 11% more — while using linear memory.
Bidirectional search#
Searches forward from the start and backward from the goal simultaneously, stopping when the frontiers meet. Since $2b^{d/2} \ll b^d$, the savings are enormous, but you must be able to compute predecessors and the goal must be explicit.
A worked example#
Consider the graph A–B (1), A–C (5), B–C (1), C–D (1). From A to D:
- BFS finds A→C→D (2 steps, cost 6).
- UCS finds A→B→C→D (3 steps, cost 3) — the cheaper route.
This illustrates the key lesson: BFS optimises the number of steps; UCS optimises total cost.