Uninformed Search

Uninformed (blind) search strategies explore the state space without domain-specific knowledge about which states are closer to the goal.

Problem Formulation

State space: Set of all possible states. Initial state: Starting point. Actions: Available moves at each state. Transition model: Result of applying an action. Goal test: Is this a goal state? Path cost: Cost of a path (sum of action costs).

Search Tree vs Search Graph

Tree search: May revisit states (explore the same state multiple times). Simpler but potentially exponential blowup.

Graph search: Track visited states (closed set). Never revisit. Uses more memory but avoids infinite loops and redundant work. Preferred in practice.

BFS (Breadth-First Search)

Explore nodes in FIFO order — all nodes at depth d before any at depth d+1.

PROCEDURE BFS(start, goal) → path or NONE
    queue ← empty FIFO queue
    visited ← empty set
    ENQUEUE(queue, (start, empty_path))
    ADD start TO visited

    WHILE queue IS NOT empty DO
        (state, path) ← DEQUEUE(queue)
        IF goal(state) THEN RETURN path
        FOR EACH (action, next) IN SUCCESSORS(state) DO
            IF next NOT IN visited THEN
                ADD next TO visited
                new_path ← path + [action]
                ENQUEUE(queue, (next, new_path))
    RETURN NONE

| Property | Value | |---|---| | Complete? | Yes (if branching factor b is finite) | | Optimal? | Yes (if all step costs are equal) | | Time | O(b^d) where d = depth of shallowest goal | | Space | O(b^d) — stores entire frontier |

Space is the bottleneck: At b=10, d=10: ~10¹⁰ nodes. BFS is impractical for deep goals.

DFS (Depth-First Search)

Explore the deepest unexpanded node first. Uses a stack (or recursion).

| Property | Value | |---|---| | Complete? | No (infinite paths). Yes with graph search on finite graphs. | | Optimal? | No (may find a deep solution before a shallow one) | | Time | O(b^m) where m = maximum depth | | Space | O(bm) — only stores current path + siblings |

Advantage: O(bm) space — dramatically less than BFS.

Uniform-Cost Search (UCS)

Expand the node with the lowest path cost g(n). Uses a priority queue.

| Property | Value | |---|---| | Complete? | Yes (if step costs ≥ ε > 0) | | Optimal? | Yes | | Time | O(b^(1 + ⌊C*/ε⌋)) where C* = optimal cost | | Space | Same as time |

UCS is BFS generalized to weighted graphs. Equivalent to Dijkstra's algorithm.

Depth-Limited Search

DFS with a depth limit L. Avoids infinite paths. Incomplete if L < d (goal depth).

Iterative Deepening DFS (IDDFS)

Run depth-limited DFS with limits 0, 1, 2, 3, ... until the goal is found.

PROCEDURE IDDFS(start, goal) → path or NONE
    FOR depth_limit ← 0, 1, 2, ... DO
        result ← DLS(start, goal, depth_limit)
        IF result IS NOT NONE THEN
            RETURN result
    RETURN NONE

| Property | Value | |---|---| | Complete? | Yes | | Optimal? | Yes (uniform step costs) | | Time | O(b^d) — same as BFS | | Space | O(bd) — same as DFS! |

Combines the best of BFS (completeness, optimality) and DFS (space efficiency). The repeated work is bounded by a constant factor: (b/(b-1))². For b=10: only 11% overhead.

IDDFS is the preferred uninformed search for most problems.

Bidirectional Search

Search simultaneously from the start and goal, meeting in the middle.

Time: O(b^(d/2)) — exponential improvement! Space: O(b^(d/2)).

Requirement: Must be able to search backward (know the goal state, generate predecessors). Checking intersection of two frontiers must be efficient (hash set).

Comparison

| Algorithm | Complete | Optimal | Time | Space | |---|---|---|---|---| | BFS | Yes | Yes* | O(b^d) | O(b^d) | | DFS | No | No | O(b^m) | O(bm) | | UCS | Yes | Yes | O(b^(1+C*/ε)) | Same | | DLS | No | No | O(b^L) | O(bL) | | IDDFS | Yes | Yes* | O(b^d) | O(bd) | | Bidirectional | Yes | Yes* | O(b^(d/2)) | O(b^(d/2)) |

(*with uniform step costs)

Applications in CS

Pathfinding: Grid-based navigation (games, robotics) when no heuristic is available.
Puzzle solving: 8-puzzle, 15-puzzle, Rubik's cube (BFS/IDDFS for optimal solutions).
Web crawling: BFS from seed URLs to discover web pages.
Network analysis: BFS for shortest paths in unweighted graphs, connected components.
Version control: Git uses graph search for merge-base finding, reachability.