Problem Solving by Search — Uninformed Strategies

Formulating problems as state-space search (states, actions, transition model, goal test, path cost), tree search vs graph search, measuring strategies by completeness, optimality, time and space, and the uninformed strategies — breadth-first, uniform-cost, depth-first, depth-limited, iterative deepening and bidirectional search — traced on an example graph.

Section 79 practice questions

Search problems

Many AI tasks — route finding, puzzles, planning, theorem proving — are solved by searching through a space of states. A search problem is defined by:

Component	Example (route finding)
Initial state	in city S
Actions $\text{ACTIONS}(s)$	drive along a road out of $s$
Transition model $\text{RESULT}(s, a)$	the city at the other end
Goal test	in city G?
Path cost (sum of step costs $c(s, a, s')$ )	total kilometres

A solution is a sequence of actions from the initial state to a goal; an optimal solution has the lowest path cost.

Tree search and graph search

Search builds a tree of nodes (state + parent + action + path cost $g$ + depth). The frontier (open list) holds generated but unexpanded nodes; strategies differ only in which frontier node they expand next.

Tree search may revisit the same state many times (and loop forever on cycles).
Graph search keeps an explored (closed) set and skips repeated states.

Python

from collections import deque

def bfs(start, goal, succ):
    frontier = deque([[start]])
    explored = {start}
    while frontier:
        path = frontier.popleft()
        if path[-1] == goal:
            return path
        for nxt in succ(path[-1]):
            if nxt not in explored:
                explored.add(nxt)
                frontier.append(path + [nxt])
    return None

Measuring a strategy

Complete: guaranteed to find a solution when one exists?
Optimal: guaranteed to find a least-cost solution?
Time and space, in terms of the branching factor $b$ , the depth of the shallowest goal $d$ , and the maximum depth $m$ .

The uninformed strategies

Uninformed (blind) strategies use only the problem definition — no estimate of distance to the goal.

Strategy	Frontier	Complete	Optimal	Time	Space
Breadth-first (BFS)	FIFO queue	yes ( $b$ finite)	yes if step costs equal	$O(b^d)$	$O(b^d)$
Uniform-cost (UCS)	priority queue on $g(n)$	yes if costs $\ge \epsilon > 0$	yes	$O(b^{1 + \lfloor C^*/\epsilon\rfloor})$	same
Depth-first (DFS)	LIFO stack	no (infinite paths)	no	$O(b^m)$	$O(bm)$
Depth-limited (limit $\ell$ )	stack, cut at depth $\ell$	no if $\ell < d$	no	$O(b^\ell)$	$O(b\ell)$
Iterative deepening (IDDFS)	DLS with $\ell = 0, 1, 2, \dots$	yes	yes if step costs equal	$O(b^d)$	$O(bd)$
Bidirectional (BFS both ways)	two queues	yes	yes if step costs equal	$O(b^{d/2})$	$O(b^{d/2})$

( $C^*$ is the optimal cost and $\epsilon$ the smallest step cost.)

Breadth-first search

Expands the shallowest node first; finds the solution with the fewest steps. Memory is the real problem: at $b = 10$ , $d = 10$ it stores $10^{10}$ nodes.

Uniform-cost search

Expands the node with the lowest path cost $g(n)$ — Dijkstra's algorithm on an implicit graph (see shortest paths). To be optimal, the goal test must be applied when a node is selected for expansion, not when it is generated; a cheaper path to an already-generated node replaces the costlier one.

Depth-first search and its fixes

DFS dives down one branch and backtracks — tiny memory, but it can wander down an infinite path or return a poor solution. Depth-limited search cuts it off at depth $\ell$ ; iterative deepening repeats DLS with growing limits, combining BFS's completeness and optimality (for unit costs) with DFS's memory. Re-generating the shallow levels is cheap because most nodes are at the deepest level.

The same tree expanded in breadth-first and depth-first order.

Quick revision

Practice questions

GATE-style questions: 2 one-mark and 7 two-mark. Wrong MCQs cost ⅓ of their marks in the real exam; MSQ and NAT have no negative marking. Attempt each before opening the solution.

Q1MCQ2 marks

Directed graph with step costs (neighbours are generated in alphabetical order): S→A (1), S→B (4), A→C (2), A→D (5), B→D (1), C→G (6), D→G (2). Start S, goal G. Graph search is used (a state is not added again once generated/expanded), and the goal test is applied when a node is expanded.

In which order does uniform-cost search expand the nodes?

Q2NAT2 marks

The cost of the path to G returned by uniform-cost search is ______.

Q3NAT2 marks

The cost of the path to G returned by breadth-first search is ______.

Q4MCQ1 mark

Which uninformed strategy is complete and optimal for unit step costs while using only $O(bd)$ memory?

Q5NAT2 marks

A search tree has branching factor $b = 10$ . The number of nodes generated at depths 1, 2 and 3 combined (excluding the root) is ______.

Q6MSQ2 marks

Which statements about uninformed search are correct (finite branching factor $b$ , solution depth $d$ )?

One or more options are correct.

Q7NAT2 marks

Iterative deepening search with $b = 10$ reaches a goal at depth $d = 5$ (in the worst case, on the last node of depth 5). Nodes at depth $i$ are generated $(d + 1 - i)$ times. The total number of node generations, $\sum_{i=1}^{d}(d + 1 - i)\,b^i$ , is ______.

Q8MCQ1 mark

The space complexity of depth-first (tree) search with branching factor $b$ and maximum depth $m$ is

Q9MCQ2 marks

Bidirectional search runs a forward search from the start and a backward search from the goal (both breadth-first) until they meet. Its time complexity is