4. Uninformed Search Strategies

Source: AIMA 4th Ed., Chapter 3 (Section 3.4) Status: Complete

Overview

Uninformed search (also called blind search) algorithms have access only to the problem definition — the state space, actions, transition model, and action costs. They have no domain-specific knowledge about which states are closer to the goal. Every strategy below is a special case of BEST-FIRST-SEARCH with a particular choice of f(n).

1. Breadth-First Search (BFS)

Core idea: Expand the shallowest unexpanded node. Explore all nodes at depth d before any node at depth d+1.

Evaluation function: f(n) = depth(n) — frontier is a FIFO queue.

Algorithm

function BREADTH-FIRST-SEARCH(problem) returns solution node or failure
    node <- NODE(problem.INITIAL)
    if problem.IS-GOAL(node.STATE) then return node   -- early goal test
    frontier <- FIFO queue, with node as element
    reached <- {problem.INITIAL}
    while not IS-EMPTY(frontier) do
        node <- POP(frontier)
        for each child in EXPAND(problem, node) do
            s <- child.STATE
            if problem.IS-GOAL(s) then return child   -- early goal test
            if s not in reached then
                add s to reached
                add child to frontier
    return failure

Note on goal test timing: BFS uses an early goal test (check when generating, not when expanding). This is safe for BFS because all actions have cost 1 (or equal cost) — the first time we generate a goal state, it is guaranteed to be via the shallowest path.

Properties

b = branching factor, d = depth of shallowest solution.

Why BFS is cost-optimal only for unit costs

BFS guarantees fewest steps, not lowest cost. If action costs differ (e.g., some roads are longer), a shallower path may cost more than a deeper one. Use UCS for general action costs.

Practical note

Space is BFS’s critical weakness. For b=10, d=12: - Time: 10^12 = 1 trillion nodes - Space: 10^12 nodes in memory simultaneously

At modern speeds and memory, d > 15 becomes completely infeasible without heuristics.

2. Uniform-Cost Search (UCS) / Dijkstra’s Algorithm

Core idea: Expand the node with the lowest path cost g(n). Equivalent to Dijkstra’s single-source shortest path algorithm.

Evaluation function: f(n) = g(n) = PATH-COST(n)

function UNIFORM-COST-SEARCH(problem) returns solution node or failure
    return BEST-FIRST-SEARCH(problem, PATH-COST)

Uses late goal test (check when popping, not when generating). This is required for optimality with general action costs.

Why late goal test is required for UCS

When a node is generated, we know a path to it, but not necessarily the cheapest one — a cheaper path may still be on the frontier. A node is guaranteed to have its optimal cost only when it is popped from the priority queue (because all remaining frontier nodes have equal or higher cost).

Properties

Explanation of time complexity: The algorithm explores all states with cost ≤ C. In the worst case, if each action costs ε, that’s up to C/ε actions, giving depth ≈ C/ε and O(b^(C/ε)) nodes.

UCS vs BFS

• UCS subsumes BFS when all action costs are equal (both are O(b^d))
• UCS is strictly more general — it handles nonuniform costs
• UCS is also equivalent to Dijkstra’s algorithm on explicit graphs

3. Depth-First Search (DFS)

Core idea: Expand the deepest unexpanded node (most recently added to frontier). Implemented with a LIFO stack.

Evaluation function: f(n) = -depth(n) — always expand deepest node.

Properties

Key advantage of DFS: its space complexity is linear in depth. For very deep state spaces, DFS uses far less memory than BFS, even if it is slower.

Key weakness: DFS can go infinitely deep in graphs with cycles or infinite depth. Graph search (with reached table) prevents infinite loops but restores O(b^m) space. Tree-like DFS with a cycle check (IS-CYCLE) limits space to O(m) but requires the cycle check at each step.

4. Depth-Limited Search (DLS)

Core idea: DFS with a hard depth cutoff l. Do not expand any node at depth > l.

function DEPTH-LIMITED-SEARCH(problem, l) returns node or failure or cutoff
    frontier <- LIFO queue (stack) with NODE(problem.INITIAL) as element
    result <- failure
    while not IS-EMPTY(frontier) do
        node <- POP(frontier)
        if problem.IS-GOAL(node.STATE) then return node
        if DEPTH(node) > l then
            result <- cutoff           -- record that we were cut off
        else if not IS-CYCLE(node) do
            for each child in EXPAND(problem, node) do
                add child to frontier
    return result

Three return values: - A solution node — success - failure — no solution exists in the explored space (not due to cutoff) - cutoff — all paths at depth ≤ l were explored, no solution found (but one may exist deeper)

Properties

5. Iterative Deepening Search (IDS)

Core idea: Run depth-limited search with increasing depth limits (l = 0, 1, 2, …) until a solution is found. This combines DFS’s space efficiency with BFS’s completeness and optimality (for unit costs).

function ITERATIVE-DEEPENING-SEARCH(problem) returns solution node or failure
    for depth = 0 to infinity do
        result <- DEPTH-LIMITED-SEARCH(problem, depth)
        if result != cutoff then return result

Why re-expansion is not wasteful

IDS appears to waste work by re-expanding nodes at every depth limit. The actual overhead is small. Consider the total nodes generated:

At depth d, BFS generates: 1 + b + b^2 + … + b^d ≈ b^d nodes.

IDS generates at each iteration: - Iteration d: b^d nodes at depth d (dominant term) - Iteration d-1: b^(d-1) nodes - …

Total = b^d + b^(d-1) + … + b ≈ b^d * (b/(b-1)) ≈ b/(b-1) * b^d

For b=10: overhead factor = 10/9 ≈ 1.11 (11% more nodes than BFS). This is negligible.

Properties

IDS is the preferred uninformed search method when the search space is large and the depth of solution is unknown, because it has BFS’s completeness and near-BFS time complexity with DFS’s linear space.

6. Bidirectional Search

Core idea: Run two simultaneous searches — one forward from the initial state, one backward from the goal state — and stop when the two frontiers meet.

Key savings: Each search needs only go to depth d/2, so time is O(b^(d/2)) instead of O(b^d). For b=10, d=10: unidirectional needs 10^10 = 10B nodes; bidirectional needs 2 × 10^5 = 200K nodes.

BIBF-SEARCH (Bidirectional Best-First Search) — Figure 3.14

The forward search uses evaluation function f_F; backward search uses f_B. The key challenge: when the two frontiers meet, the joined path may not be optimal — we must keep searching until we can certify optimality.

function BIBF-SEARCH(problem_F, f_F, problem_B, f_B) returns solution or failure
    node_F <- NODE(problem_F.INITIAL)
    node_B <- NODE(problem_B.INITIAL)    -- problem_B starts from goal
    frontier_F <- priority queue with node_F, ordered by f_F
    frontier_B <- priority queue with node_B, ordered by f_B
    reached_F <- {problem_F.INITIAL: node_F}
    reached_B <- {problem_B.INITIAL: node_B}
    solution <- failure
    while not TERMINATED(solution, frontier_F, frontier_B) do
        if f_F(TOP(frontier_F)) <= f_B(TOP(frontier_B)) then
            solution <- PROCEED(F, problem_F, frontier_F, reached_F,
                                reached_B, solution)
        else
            solution <- PROCEED(B, problem_B, frontier_B, reached_B,
                                reached_F, solution)
    return solution

function PROCEED(dir, problem, frontier, reached, reached2, solution)
    node <- POP(frontier)
    for each child in EXPAND(problem, node) do
        s <- child.STATE
        if s not in reached or child.PATH-COST < reached[s].PATH-COST then
            reached[s] <- child
            add child to frontier
            if s in reached2 then
                -- Found a path joining forward and backward frontiers
                solution2 <- JOIN-NODES(dir, child, reached2[s])
                if PATH-COST(solution2) < PATH-COST(solution) then
                    solution <- solution2
    return solution

TERMINATED condition: stop when the best path found so far is at most as long as the minimum f-value in either frontier. Once both frontiers have expanded past C*/2, no better path can be found.

Properties

Challenge with backward search: we need to know the predecessors of a state (which states can reach it), requiring an explicit inverse transition model or a fully reversible problem.

Algorithm Comparison Summary

Common Exam Pitfalls

1. BFS is not cost-optimal for unequal action costs — use UCS instead.
2. DFS is not complete in general — only in finite acyclic state spaces.
3. IDS re-expansion overhead is O(b/(b-1)), not a doubling — it is negligible for large b.
4. UCS requires late goal test — early goal test breaks optimality.
5. Bidirectional search requires an inverse model — for most problems this is natural, but not always.
6. The 8-puzzle has 181,440 states, not 362,880 — exactly half of 9! are reachable from any given state.