Uninformed Search

Search is the computational form of asking “What would happen if I did this?” A planning agent does not need to execute every possibility in the real world. It uses a model to simulate actions, explores the resulting alternatives, and returns a sequence that reaches a goal.

An uninformed search algorithm receives no estimate of which state is closer to the goal. It can recognize a goal when it reaches one and compare accumulated path costs, but it has no domain-specific direction. This apparent limitation makes uninformed search an important foundation: its guarantees are clear, and informed methods can later be understood as disciplined changes to the same framework.

Problem Formulation

A search problem contains:

1. State space — all abstract situations relevant to the task;
2. Initial state — where planning begins;
3. Actions — choices available in a state;
4. Transition model — the state produced by an action;
5. Step cost — the cost of taking that action;
6. Goal test — whether a state satisfies the objective.

A solution is an action sequence connecting the initial state to any goal state. An optimal solution has minimum total path cost.

Abstraction

The real world contains unlimited detail. A search state should retain only information needed to predict legal actions, future states, costs, and goal satisfaction.

For campus route planning, a state might be a building identifier. The color of the traveler’s clothing is irrelevant. If elevators can close at certain times, current time may be essential. If the goal is to collect equipment from several rooms, the state must include which items have already been collected.

Too little state merges situations that have different futures. Too much state creates a combinatorial explosion.

States and Nodes

The state-space graph contains each state once, with edges representing legal transitions. A search tree represents paths generated during exploration. The same state may appear in several tree nodes because different action sequences reach it.

This distinction explains why a node needs more than a state:

node = state + parent + action + path cost + depth

It also explains repeated-state detection. Without it, a cycle such as A → B → A creates an infinite search tree even though the state graph has only two states.

Frontiers

Search maintains a frontier of generated nodes waiting to be expanded. Expanding a node means applying the successor function and adding resulting nodes to the frontier.

The family resemblance among algorithms is simple:

• BFS chooses the shallowest frontier node;
• DFS chooses the deepest most recently generated node;
• uniform-cost search chooses the node with least accumulated cost;
• greedy search chooses the node estimated closest to a goal;
• A* chooses the node with least estimated complete-solution cost.

The frontier policy determines completeness, optimality, time, and memory.

Measuring Search

Let:

• b be the branching factor, the average number of successors;
• d be the depth of the shallowest solution;
• m be the maximum search depth;
• C* be the optimal solution cost;
• ε be the smallest positive step cost.

Exponential growth dominates search. With b = 10, a tree contains roughly one million nodes by depth 6 and one billion by depth 9. Reducing unnecessary state or improving direction often matters more than low-level code optimization.

Four standard questions should be asked:

• Complete? Guaranteed to find a solution when one exists?
• Optimal? Guaranteed to find a least-cost solution?
• Time complexity? How many nodes may be generated or expanded?
• Space complexity? How many nodes must be retained?

Breadth-First Search

Breadth-first search expands states in nondecreasing depth. Its frontier is a FIFO queue.

All search implementations in this course use the same simple graph. Each key is a state, and its value is a list of (neighbor, cost) pairs. Every algorithm receives graph, start, and goal, then returns a dictionary containing the path, cost, and number of expanded states. Input and printing remain outside the algorithm.

from collections import deque

def build_path(parent, goal):
    path = []
    current = goal

    while current is not None:
        path.append(current)
        current = parent[current]

    path.reverse()
    return path

def breadth_first_search(graph, start, goal):
    if start == goal:
        return {"path": [start], "cost": 0, "expanded": 0}

    frontier = deque([start])
    visited = {start}
    parent = {start: None}
    depth = {start: 0}
    expanded = 0

    while frontier:
        state = frontier.popleft()
        expanded += 1

        for next_state, step_cost in graph[state]:
            if step_cost != 1:
                raise ValueError("BFS requires unit step costs")
            if next_state in visited:
                continue

            visited.add(next_state)
            parent[next_state] = state
            depth[next_state] = depth[state] + 1

            if next_state == goal:
                return {
                    "path": build_path(parent, goal),
                    "cost": depth[goal],
                    "expanded": expanded,
                }

            frontier.append(next_state)

    return None

Marking a state discovered when it enters the queue prevents duplicate frontier entries. For unit-cost graphs, the first discovered path to a state is also a shallowest path.

BFS Properties

• Complete when b is finite and a solution occurs at finite depth.
• Optimal when every step has equal cost.
• Time: O(b^d).
• Space: O(b^d).

Memory is the practical weakness. BFS must retain a broad final layer.

Worked Example

Suppose the graph is:

S → A, B
A → C, D
B → E
C → G
D → G
E → F

With left-to-right successor order, BFS expands S, then A, B, then C, D, E. It discovers G through C at depth 3. Even if another path to G exists through D, that path cannot be shallower because every depth-2 node is processed before any depth-3 node.

Depth-First Search

Depth-first search expands the most recently generated frontier node. Its frontier is a stack. Recursive traversal is also a stack, but an explicit stack makes limits and path reconstruction easier to control.

def depth_first_search(graph, start, goal):
    frontier = [(start, [start], 0.0)]
    visited = {start}
    expanded = 0

    while frontier:
        state, path, cost = frontier.pop()
        expanded += 1

        if state == goal:
            return {
                "path": path,
                "cost": cost,
                "expanded": expanded,
            }

        successors = graph[state]
        for next_state, step_cost in reversed(successors):
            if next_state in visited:
                continue
            visited.add(next_state)
            new_path = path + [next_state]
            new_cost = cost + step_cost
            frontier.append((next_state, new_path, new_cost))

    return None

The reversal preserves intuitive left-to-right expansion because the stack removes the last item first.

DFS Properties

• Not complete in infinite-depth spaces without additional safeguards.
• Not optimal.
• Time: O(b^m) in the worst case.
• Space: O(bm) for tree-style depth-first exploration.

DFS is valuable when memory is tight, solutions may be deep, and any solution is acceptable. Its performance depends strongly on successor order.

Cycle Checks

A global explored set prevents every repeated expansion. That is efficient, but in some problems a later path to the same state may matter because it has a different cost or context. A path-level set prevents only cycles in the current route. The correct policy depends on whether the state representation contains everything relevant to future decisions.

Depth-Limited Search

Depth-limited search treats nodes at a chosen limit ℓ as having no successors. It has three possible results:

• success;
• failure, meaning no solution exists within the explored finite tree;
• cutoff, meaning the limit prevented a conclusion.

Failure and cutoff must remain distinct. If a search at depth 5 cuts off, it does not prove the problem unsolvable.

def depth_limited_search(graph, start, goal, limit):
    if limit < 0:
        raise ValueError("limit must be non-negative")

    def visit(state, remaining, path, cost):
        if state == goal:
            return {
                "status": "found",
                "path": path,
                "cost": cost,
                "expanded": 0,
            }

        if remaining == 0:
            return {
                "status": "cutoff",
                "path": [],
                "cost": 0,
                "expanded": 0,
            }

        expanded = 1
        saw_cutoff = False

        for next_state, step_cost in graph[state]:
            if next_state in path:
                continue

            new_path = path + [next_state]
            child = visit(
                next_state, remaining - 1,
                new_path, cost + step_cost
            )
            expanded += child["expanded"]

            if child["status"] == "found":
                child["expanded"] = expanded
                return child
            if child["status"] == "cutoff":
                saw_cutoff = True

        status = "cutoff" if saw_cutoff else "failure"
        return {
            "status": status,
            "path": [],
            "cost": 0,
            "expanded": expanded,
        }

    return visit(start, limit, [start], 0)

Iterative Deepening

Iterative deepening repeatedly runs depth-limited search with limits 0, 1, 2, ... until it finds a solution.

At first, repeating the upper levels appears wasteful. In an exponential tree, however, most nodes are in the deepest layer. If b = 10 and the solution depth is 5, nodes near depth 5 dominate the work; regenerating the tiny upper layers adds a modest fraction.

ID Properties

• Complete for finite branching factor.
• Optimal for equal step costs.
• Time: O(b^d).
• Space: O(bd).

It combines BFS’s shallow-solution guarantee with DFS’s low memory. It is especially useful when the solution depth is unknown.

def iterative_deepening_search(graph, start, goal, max_depth):
    total_expanded = 0

    for limit in range(max_depth + 1):
        result = depth_limited_search(
            graph, start, goal, limit
        )
        total_expanded += result["expanded"]

        if result["status"] == "found":
            return {
                "path": result["path"],
                "cost": result["cost"],
                "expanded": total_expanded,
            }
        if result["status"] == "failure":
            return None

    return None

max_depth is an engineering guard against an unbounded or incorrectly modelled state space. An idealized iterative-deepening search can continue without it; production code should have a resource boundary.

Grid Example

A grid gives BFS and DFS the same state model and exposes their different frontier policies. # marks a blocked cell, while every other cell is traversable. The neighbor order is fixed as down, right, up, left, making experiments reproducible.

GRID = (
    "..#..",
    ".#...",
    ".#.#.",
    "...#.",
    ".....",
)

MOVES = ((1, 0), (0, 1), (-1, 0), (0, -1))

def grid_to_graph(grid):
    graph = {}
    rows = len(grid)
    columns = len(grid[0])

    for row in range(rows):
        for column in range(columns):
            if grid[row][column] == "#":
                continue

            state = (row, column)
            graph[state] = []

            for row_step, column_step in MOVES:
                next_row = row + row_step
                next_column = column + column_step
                inside = (
                    0 <= next_row < rows
                    and 0 <= next_column < columns
                )

                if inside and grid[next_row][next_column] != "#":
                    next_state = (next_row, next_column)
                    graph[state].append((next_state, 1))

    return graph

graph = grid_to_graph(GRID)
start = (0, 0)
goal = (4, 4)

bfs_result = breadth_first_search(
    graph, start, goal
)
dfs_result = depth_first_search(
    graph, start, goal
)
iddfs_result = iterative_deepening_search(
    graph, start, goal, max_depth=20
)

assert bfs_result is not None
assert bfs_result["path"][0] == start
assert bfs_result["path"][-1] == goal
assert len(bfs_result["path"]) - 1 == bfs_result["cost"]
assert iddfs_result is not None
assert iddfs_result["cost"] == bfs_result["cost"]

The assertions test properties, not a fragile exact route. If two shortest routes exist, changing neighbor order may select a different path with the same valid cost.

Uniform-Cost Search

BFS minimizes the number of steps. Uniform-cost search (UCS) minimizes the sum of step costs. It expands the frontier node with smallest g(n), where g(n) is the cost from the start to node n.

from heapq import heappop, heappush
from itertools import count

def uniform_cost_search(graph, start, goal):
    serial = count()
    frontier = [(0.0, next(serial), start)]
    best_cost = {start: 0.0}
    parent = {start: None}
    expanded = 0

    while frontier:
        cost, _, state = heappop(frontier)

        if cost != best_cost.get(state):
            continue
        expanded += 1
        if state == goal:
            return {
                "path": build_path(parent, goal),
                "cost": cost,
                "expanded": expanded,
            }

        for next_state, step in graph[state]:
            if step < 0:
                raise ValueError("UCS requires non-negative costs")

            new_cost = cost + step
            if new_cost < best_cost.get(next_state, float("inf")):
                best_cost[next_state] = new_cost
                parent[next_state] = state
                heappush(
                    frontier,
                    (new_cost, next(serial), next_state),
                )

    return None

The goal test occurs when a goal is removed from the priority queue, not when it is inserted. A more expensive goal path may be generated before a cheaper unfinished path.

Cost Example

Consider:

S → G  cost 10
S → A  cost 2
A → B  cost 2
B → G  cost 2

The direct goal enters the frontier with cost 10. UCS next removes A with cost 2, then B with cost 4, then a second path to G with cost 6. The cost-6 entry is removed before the cost-10 entry, so UCS returns the cheaper three-step route.

UCS Properties

With positive minimum step cost ε:

• Complete when an optimal solution has finite cost.
• Optimal for non-negative step costs.
• Time and space are exponential in approximately C*/ε.

Zero-cost cycles require careful duplicate handling. Negative edges invalidate the guarantee because a supposedly settled state may later become cheaper.

Comparison

Applications

Uninformed search remains useful in:

• shortest paths in unweighted networks;
• puzzle and maze baselines;
• web crawling with depth policies;
• dependency traversal;
• minimum-cost routing when no reliable heuristic exists;
• model checking over finite state systems;
• comparison baselines for heuristic algorithms.

A baseline is scientifically important. If a complicated heuristic search does not improve on UCS in expansions, runtime, or memory, its complexity is not justified.

Implementation Method

Run every algorithm on the same grid family rather than presenting one successful maze. Vary obstacle density, grid size, solution depth, and whether a route exists. For each run record:

• path cost;
• states expanded;
• maximum frontier size;
• elapsed time;
• success or failure;
• fixed neighbor order and random seed.

Do not compare BFS’s shortest route with DFS’s first route as if both optimize the same objective. First verify correctness, then compare resources under clearly stated guarantees. An unsolvable maze is especially useful: it reveals whether duplicate detection is correct and forces an algorithm to expose its full reachable-state cost.

Failure Modes

• State explosion: Revisit the abstraction before tuning the implementation.
• Repeated states: Add correct hashing and duplicate detection.
• Wrong optimality claim: BFS is not least-cost when actions have unequal cost.
• Premature goal test: UCS must stop when the cheapest goal is popped.
• Hidden negative costs: Validate model assumptions.
• Path copying: Parent links reduce memory.
• Misleading runtime: Count generated and expanded nodes as well as wall time.
• DFS recursion overflow: Use an explicit stack for deep spaces.

Exercises

1. Formulate the water-jug problem with two containers as a search problem. Specify states, actions, transitions, costs, and goal test.
2. Trace BFS and DFS by hand on the same graph using a fixed successor order. Record frontier contents after every expansion.
3. Construct a weighted graph where BFS returns a more expensive path than UCS.
4. Modify depth-limited search to return both the action path and number of expanded nodes.
5. Implement iterative deepening and compare its peak frontier size with BFS on a balanced tree.
6. Explain why a global explored set is safe for BFS on a static unweighted graph.
7. Design an experiment comparing BFS, DFS, iterative deepening, and UCS across solvable and unsolvable mazes. State the metrics before running it.
8. Modify the grid experiment to report maximum frontier size without changing the returned path.
9. Construct a cyclic graph on which path-level and global duplicate detection expand different numbers of states.
10. Add diagonal moves with cost √2; explain why BFS is no longer the appropriate optimal algorithm.