1.1 State Space, BFS, DFS, and Uniform Cost Search: First, define what counts as the same state

The difference between search algorithms is often reduced to "queue or stack." What truly determines correctness and efficiency is the problem representation, edge costs, state repetition, and stopping conditions.

This lesson's objectives

• Define a search problem using state, action, transition, goal, and path cost;
• Distinguish tree search from graph search;
• Explain the completeness and optimality conditions of BFS, DFS, and Uniform-Cost Search;
• Return a verifiable path, rather than True/False alone.

1. Six Components of a Search Problem

Represent the problem with these six components:

initial_state: Where do we start?
actions(state): What actions are currently allowed?
transition(state, action): What is the next state after taking an action
goal_test(state): How do you know you've reached the goal?
step_cost(state, action, next_state): step cost
state_key(state): How are equivalent states identified?

A path is a sequence of actions or states; a solution is a path leading to the goal; an optimal solution must also specify the total cost. If the goal is simply "fewest steps," assign a cost of 1 per step; if road distances, risks, or time differ, BFS cannot replace lowest-cost search.

2. State representation alters the search space

The same maze can be represented as:

• The complete world state including pixels, direction, speed, and inventory contents;
• Only retain the current grid state;
• Treat rooms as nodes and corridors as edges to form a topological map.

An overly detailed abstraction makes branching and depth explode. An overly coarse one merges distinct situations and may return a path that cannot be executed.

The state key must include all information that affects future actions, goals, and costs. For example, whether a door is open affects reachability, so you can't just use coordinates for hashing. Conversely, if the history of the path taken doesn't matter for future decisions, including the entire path in the key would prevent effective merging.

3. Tree Search vs. Graph Search

Tree search treats each different path as a new node. When cycles exist in the graph, it may endlessly loop. Graph search uses frontier and reached/visited sets to record discovered states, preventing or limiting repetition.

But "seen once and never again" is only true under specific algorithms:

• BFS with unit edge costs finds the first occurrence of a state to be the minimum number of steps;
• DFS the first time it reaches a node does not guarantee the shortest or lowest cost path;
• Uniform-Cost/A* If a lower g is found, the state must be updated and may need to be re-opened.

If BFS marks a node as visited only after popping it, several copies can enter the queue first. Record discovery when enqueuing; for UCS, track the best known cost. Three copies of the same state do not make the answer more convincing.

4. BFS: Expand level by level by depth

This Python 3 function fragment (partial) needs caller-provided neighbor and goal functions. States must be hashable; this example reserves None as the parent sentinel, so it cannot represent a real state.

from collections import deque

def reconstruct(parent, goal):
    path = [goal]
    while parent[path[-1]] is not None:
        path.append(parent[path[-1]])
    return list(reversed(path))

def bfs(neighbors, start, is_goal):
    frontier = deque([start])
    parent = {start: None}  # Also indicates reached

    while frontier:
        state = frontier.popleft()
        if is_goal(state):
            return reconstruct(parent, state)

        for next_state in neighbors(state):
            if next_state not in parent:
                parent[next_state] = state
                frontier.append(next_state)

    return None

BFS is complete with finite branching and a finite goal depth. It guarantees minimum cost when step costs are equal and non-negative. With a shallowest goal at depth $d$ and branching factor $b>1$, this implementation tests the goal on removal and may already have generated depth $d+1$, giving time and space bounds of $O(b^{d+1})$. Testing goals on generation yields the familiar $O(b^d)$ bound. Either version can fill memory quickly.

5. DFS: Trade memory for search risk

DFS dives into one branch at a time, suitable for:

• Memory pressure;
• Solutions may be very deep;
• Just any solution;
• The search tree is finite or has a reliable depth bound.

It doesn't guarantee the shallowest or lowest-cost solution; in infinitely deep branches, it might never reach a nearby goal. Graph DFS uses a global visited set, so space also includes the visited set, and it's not accurate to say "only $O(d)$" in general; tree DFS has a smaller frontier, but it may revisit states.

Depth-limited search prevents infinite descent, and by gradually increasing the depth, we form iterative deepening DFS (IDDFS). Under unit cost and finite branching, IDDFS achieves BFS's shallow optimality while maintaining frontier space similar to DFS, at the cost of repeatedly expanding shallow nodes.

6. Uniform-Cost Search: Expand Based on Total Cost

For unequal non-negative edge costs, use a priority queue to expand the state with the smallest accumulated cost $g$. This Python 3 fragment reuses reconstruct above; edges(state) returns (successor, finite_nonnegative_cost) pairs.

import heapq
from itertools import count

def uniform_cost_search(edges, start, is_goal):
    tie = count()
    frontier = [(0.0, next(tie), start)]
    best_g = {start: 0.0}
    parent = {start: None}

    while frontier:
        g, _, state = heapq.heappop(frontier)
        if g != best_g.get(state):       # Skip old queue item
            continue
        if is_goal(state):
            return reconstruct(parent, state), g

        for next_state, step_cost in edges(state):
            if step_cost < 0:
                raise ValueError("UCS requires non-negative edge costs")
            new_g = g + step_cost
            if new_g < best_g.get(next_state, float("inf")):
                best_g[next_state] = new_g
                parent[next_state] = state
                heapq.heappush(frontier, (new_g, next(tie), next_state))

    return None

UCS shares its core with Dijkstra. Finite graphs can contain zero-cost edges. On infinite graphs, finite branching and a positive lower bound ε on every step cost are common sufficient conditions for completeness. Bounding only the positive costs is insufficient: an infinite zero-cost chain can also keep the goal from being popped.

7. Complexity Goes Beyond the number of nodes

The real system also needs to calculate:

• The cost of generating the successor;
• The size of the state key and hash cost;
• parent/action storage;
• Repeat state rate;
• Target testing and edge cost calculation;
• Can graphs be pre-materialized?

Implicit graphs (puzzles, planning, games) typically can't list all nodes; they generate successors on demand.

8. Correctness Testing

The starting point is the destination.
Target not reachable
cycles and self-loops
The same state is reached through multiple paths
Unit cost versus non-unit cost
Zero-cost edge
Multiple objectives
State key is too coarse/too fine

For small graphs, enumerate all simple paths or compare with a trusted shortest-path implementation to verify continuity, goal arrival, and total cost.

For example, let S→G cost 9, and let S→A and A→G each cost 2. With successors supplied in that order, BFS returns [S, G]; UCS returns [S, A, G] with cost 4. Add a zero-cost A→S edge and both searches should still terminate. This checks duplicate handling as well as cost selection.

Common Misconceptions

• BFS Always Finds the Shortest Path: Only under the meaning of step count or equal cost.
• DFS space is always $O(d)$: graph search also keeps track of visited nodes.
• The visited mark makes no difference when a node is dequeued: the frontier might accumulate a large number of duplicates.
• State equals all the information visible on the screen: Keep the minimal sufficient state that affects the future.

Practice

1. Design a state key for a maze with keys and doors, and explain why coordinates alone are insufficient.
2. On a cyclic graph, compare the number of node expansions between tree BFS and graph BFS.
3. Construct a graph where BFS chooses the fewest-step, higher-cost path, and UCS chooses the longer-step, lower-cost path.
4. Add action records to UCS and verify the total path cost returned.

Summary

Search begins with problem modeling. BFS, DFS, and UCS are merely different frontier strategies; their guarantees depend on edge costs, state equivalence, and search space conditions.

Next lesson, we'll introduce heuristics: how A* uses a lower bound on the goal to reduce unnecessary expansions, and why inconsistent heuristics require re-expanding nodes.