Artificial Intelligence

Problem Solving By Search

Uninformed Search

Uninformed vs Informed (Preview of Chapter 3)

JrCodex·7 min read

Jr Codex AI Notes

Level: Intermediate Prerequisites: Chapter 1 Time to complete: ~30 minutes

Table of Contents

  1. What Makes Search "Uninformed"?
  2. Breadth-First Search (BFS)
  3. Depth-First Search (DFS)
  4. Uniform-Cost Search (UCS)
  5. Comparing BFS, DFS, and UCS
  6. Evaluating Search Algorithms — Four Criteria
  7. Summary & Next Steps

1. What Makes Search "Uninformed"?

Uninformed (or "blind") search algorithms have no additional information about how close a state is to the goal — they only know what Chapter 1's five-component problem definition provides: states, actions, and costs. Chapter 3's informed search adds a heuristic (an estimate of remaining distance to the goal) — the key thing that's absent here.

Uninformed vs Informed (Preview of Chapter 3)
─────────────────────────────────────────
  Uninformed:  "I don't know which direction is more promising —
                 I'll explore systematically until I find the goal."

  Informed:      "I have an ESTIMATE of how far each state is from
                   the goal — I'll explore the most PROMISING
                   states first." (Chapter 3)
─────────────────────────────────────────

2. Breadth-First Search (BFS)

BFS explores the state space level by level — all states 1 step away, then all states 2 steps away, and so on. The frontier is a queue (first-in-first-out), following the generic template from Chapter 1, Section 6.

from collections import deque
 
def breadth_first_search(problem):
    frontier = deque([(problem.initial_state, [])])      # queue: FIFO
    visited = {problem.initial_state}
 
    while frontier:
        state, path = frontier.popleft()      # remove from the FRONT
 
        if problem.goal_test(state):
            return path
 
        for action in problem.actions(state):
            next_state = problem.result(state, action)
            if next_state not in visited:
                visited.add(next_state)
                frontier.append((next_state, path + [action]))      # add to the BACK
 
    return None
 
# Using Chapter 1's romania_map and SearchProblem
from_arad_to_bucharest = SearchProblem("Arad", "Bucharest", romania_map)
solution = breadth_first_search(from_arad_to_bucharest)
print(solution)      # e.g. ['Sibiu', 'Fagaras', 'Bucharest']
BFS Exploration Order (Level by Level)
─────────────────────────────────────────
              [Arad]                    ← Level 0
             /   |    \
       [Zerind][Sibiu][Timisoara]        ← Level 1 (explored FIRST, entirely)
         /        |        \
     [Oradea] [Fagaras/Rimnicu] [Lugoj]    ← Level 2 (explored SECOND, entirely)
─────────────────────────────────────────

Key property: BFS is guaranteed to find the shortest path in terms of number of steps — but NOT necessarily the lowest-cost path if steps have different costs (that's what UCS, Section 4, guarantees instead).

3. Depth-First Search (DFS)

DFS explores as deep as possible down one path before backtracking — the frontier is a stack (last-in-first-out).

def depth_first_search(problem):
    frontier = [(problem.initial_state, [])]      # stack: LIFO
    visited = set()
 
    while frontier:
        state, path = frontier.pop()      # remove from the END (top of stack)
 
        if problem.goal_test(state):
            return path
 
        if state in visited:
            continue
        visited.add(state)
 
        for action in problem.actions(state):
            next_state = problem.result(state, action)
            if next_state not in visited:
                frontier.append((next_state, path + [action]))      # add to the END
 
    return None
 
solution = depth_first_search(from_arad_to_bucharest)
print(solution)
DFS Exploration Order (Deep Before Wide)
─────────────────────────────────────────
  [Arad] → [Zerind] → [Oradea] → [Sibiu] → ...
     (follows ONE path as deep as it goes, only backtracking
      when it hits a dead end or already-visited state)
─────────────────────────────────────────

Key trade-off: DFS uses far less memory than BFS (it only needs to remember one path at a time, not every state at the current level) — but it can find a much longer, worse solution than necessary, since it commits early to a direction without comparing alternatives.

The Recursive Formulation

DFS has a natural recursive implementation, directly connecting to Python Notes, Module 2, Chapter 4's recursion chapter:

def dfs_recursive(problem, state, path, visited):
    if problem.goal_test(state):
        return path
 
    visited.add(state)
    for action in problem.actions(state):
        next_state = problem.result(state, action)
        if next_state not in visited:
            result = dfs_recursive(problem, next_state, path + [action], visited)
            if result is not None:
                return result      # base case satisfied somewhere deeper in the recursion
    return None      # this branch is a dead end

4. Uniform-Cost Search (UCS)

UCS always expands the state with the lowest cumulative path cost so far — the frontier is a priority queue, ordered by accumulated cost.

import heapq
 
def uniform_cost_search(problem):
    frontier = [(0, problem.initial_state, [])]      # (cumulative_cost, state, path)
    visited = set()
 
    while frontier:
        cost, state, path = heapq.heappop(frontier)      # lowest cost FIRST
 
        if problem.goal_test(state):
            return path, cost
 
        if state in visited:
            continue
        visited.add(state)
 
        for action in problem.actions(state):
            next_state = problem.result(state, action)
            step_cost = problem.step_cost(state, action)
            if next_state not in visited:
                heapq.heappush(frontier, (cost + step_cost, next_state, path + [action]))
 
    return None, float("inf")
 
solution, total_cost = uniform_cost_search(from_arad_to_bucharest)
print(f"Path: {solution}, Total cost: {total_cost}")      # the OPTIMAL (lowest-cost) route
Why UCS Guarantees the OPTIMAL Path (Unlike BFS With Varying Costs)
─────────────────────────────────────────
  BFS guarantees the FEWEST STEPS — irrelevant if step costs vary
  (Arad→Sibiu costs 140, but that might be ONE step vs a longer,
  cheaper multi-step alternative).

  UCS always expands the CHEAPEST accumulated path so far — by
  the time it reaches the goal, no cheaper path could possibly
  still be waiting in the frontier.
─────────────────────────────────────────

UCS is what Chapter 1's heapq-based priority queue is really for — and it's the direct ancestor of A* (Chapter 3), which is UCS plus a heuristic.

5. Comparing BFS, DFS, and UCS

# Running all three on the same problem to see the difference directly
bfs_path = breadth_first_search(from_arad_to_bucharest)
dfs_path = depth_first_search(from_arad_to_bucharest)
ucs_path, ucs_cost = uniform_cost_search(from_arad_to_bucharest)
 
print(f"BFS path  ({len(bfs_path)} steps): {bfs_path}")
print(f"DFS path  ({len(dfs_path)} steps): {dfs_path}")
print(f"UCS path  ({len(ucs_path)} steps, cost={ucs_cost}): {ucs_path}")
AlgorithmFrontier StructureGuarantees Optimal?Memory Use
BFSQueue (FIFO)Optimal for STEP COUNT only (equal-cost steps)High — stores every state at the current level
DFSStack (LIFO)No — can find a long, wasteful pathLow — only stores the current path
UCSPriority queue (by cost)Yes — optimal for PATH COSTHigh — similar to BFS

6. Evaluating Search Algorithms — Four Criteria

Every search algorithm, uninformed or informed, is evaluated against these four standard criteria — worth memorizing as the lens for comparing every algorithm in this module:

The Four Evaluation Criteria
─────────────────────────────────────────
  Completeness:   Is the algorithm GUARANTEED to find a solution
                    if one exists?
  Optimality:        If it finds a solution, is it GUARANTEED to
                       be the best (lowest-cost) one?
  Time Complexity:      How does runtime grow as the problem gets bigger?
  Space Complexity:       How does memory usage grow as the problem
                            gets bigger?
─────────────────────────────────────────
AlgorithmComplete?Optimal?TimeSpace
BFSYes (finite branching)Only for uniform step costsO(b^d)O(b^d)
DFSOnly in finite state spacesNoO(b^m)O(bm)
UCSYesYesO(b^(C*/ε))O(b^(C*/ε))

(b = branching factor, d = depth of shallowest solution, m = maximum depth, C* = optimal cost, ε = minimum step cost — these formulas are standard AI textbook notation, worth recognizing rather than memorizing precisely.)

The practical takeaway: DFS's dramatically lower space complexity (O(bm) vs exponential for BFS/UCS) is the reason to ever choose it despite giving up optimality — for very large or deep state spaces where memory is the binding constraint, this trade-off can be decisive.

7. Summary & Next Steps

Key Takeaways

  • Uninformed search has no estimate of distance-to-goal — it explores based purely on the problem's structure (states, actions, costs).
  • BFS (queue) guarantees the fewest steps but not the lowest cost; DFS (stack) uses far less memory but gives up any optimality guarantee; UCS (priority queue by cost) guarantees the lowest-cost path.
  • Every search algorithm is judged against four criteria: completeness, optimality, time complexity, and space complexity.
  • DFS's linear-in-depth memory usage (vs BFS/UCS's exponential) is the key practical reason to accept its lack of optimality guarantees.

Concept Check

  1. Why does BFS guarantee the fewest steps but not necessarily the cheapest path?
  2. What's the core data-structure difference between BFS and DFS, and how does that difference explain their different memory usage?
  3. Under what circumstance would UCS and BFS return the identical path?

Next Chapter

→ Chapter 3: Informed Search & Heuristics

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index