I4 · Problem Solving and Reasoning: Classical AI

Uninformed Search

Uninformed, or blind, search algorithms explore a state space using only the problem definition, with no estimate of how close a state is to the goal. Breadth-first search expands the shallowest states first, using a queue; depth-first search expands the deepest first, using a stack; uniform-cost search expands the cheapest path first, using a priority queue; and iterative deepening runs depth-limited searches with increasing limits.

15 min Intermediate · Sublevel Intermediate Jump to the activity

What you need: The earlier topics of this module.

Definition

You are in a maze with no map and no idea which way the exit is. You could try every path one step deep, then two steps, then three; or follow one path as far as it goes before backing up. Which is better?

Uninformed, or blind, search algorithms explore a state space using only the problem definition, with no estimate of how close a state is to the goal. Breadth-first search expands the shallowest states first, using a queue; depth-first search expands the deepest first, using a stack; uniform-cost search expands the cheapest path first, using a priority queue; and iterative deepening runs depth-limited searches with increasing limits.

In simple words

Breadth-first is like ripples spreading from a stone dropped in water: everything one step away, then two, then three. Depth-first is like exploring a cave by always taking the first tunnel until it ends, then backing up to try the next.

Overview

  • Uninformed (blind) search explores the state space using only the problem definition, with no hints about where the goal is.
  • Algorithms differ only in the order in which they expand nodes from the frontier.
  • They are judged by completeness, optimality, time and memory.
  • b is the branching factor and d the depth of the shallowest goal; many costs grow like bᵈ.
  • Queues and stacks from module I1 are the frontier data structures.
  • Blind search is the foundation that informed search improves on.

Why it matters

These algorithms are the foundation of all search in AI, from puzzles and route finding to game playing and planning. Their trade-offs between completeness, optimality, time and memory explain why smarter, informed search was needed.

Key terms

Frontier
The set of discovered states waiting to be expanded.
Breadth-first search (BFS)
Expands states in order of depth using a FIFO queue.
Depth-first search (DFS)
Expands the deepest state first using a LIFO stack.
Uniform-cost search
Expands the path with the lowest total cost so far; Dijkstra's algorithm.
Completeness and optimality
Whether an algorithm always finds a solution if one exists, and whether it finds the best one.
Iterative deepening
Repeated depth-limited DFS with limits 0, 1, 2…, combining BFS's guarantees with DFS's memory use.

Types

There are five classic uninformed search strategies. They trade off memory, speed and whether they find the best solution.

1. Breadth-first search (BFS)

Expanding the shallowest unexplored node first, level by level.

  • How it works: The frontier is a FIFO queue; BFS is complete and finds the fewest-step solution, but memory grows as O(bᵈ).
  • Example: Finding the fewest metro changes between two stations.
  • When to use it: Use it when all steps cost the same and the solution is not too deep.

2. Depth-first search (DFS)

Expanding the deepest node first, following one path as far as possible before backtracking.

  • How it works: The frontier is a LIFO stack; memory is only O(bm) for depth m, but it is not optimal and can get lost in infinite paths.
  • Example: Exploring a maze by always taking the leftmost unexplored passage.
  • When to use it: Use it when memory is tight, solutions are plentiful or the search space is finite.

3. Uniform-cost search (UCS)

Expanding the node with the lowest path cost so far.

  • How it works: The frontier is a priority queue ordered by g(n); it is complete and optimal when costs are positive, and is Dijkstra's algorithm in search form.
  • Example: Finding the shortest road distance from Pune to Nagpur when roads have different lengths.
  • When to use it: Use it when actions have different costs and no heuristic is available.

4. Depth-limited and iterative deepening search

DFS with a depth limit, and repeating it with limits 0, 1, 2, … until a goal is found.

  • How it works: Iterative deepening combines BFS's completeness and optimality (for equal costs) with DFS's small memory; re-expanding shallow nodes costs surprisingly little.
  • Example: Solving the 8-puzzle with limited memory.
  • When to use it: Use iterative deepening as the default blind search for large spaces with unknown solution depth.

5. Bidirectional search

Running two searches at once, forward from the start and backward from the goal, until they meet.

  • How it works: Each search goes only half as deep, so the work is about 2 × b^(d/2) instead of bᵈ, a huge saving.
  • Example: Finding the connection between two people in a social network by searching from both ends.
  • When to use it: Use it when the goal state is known and actions can be reversed.

Explained in detail

One loop, different frontiers

All these algorithms share the same skeleton. Put the initial state in the frontier. Repeatedly remove a state, check whether it is the goal, and if not add its unvisited neighbours to the frontier. What differs is which state is removed next, and that is decided by the type of frontier. A first-in, first-out queue gives breadth-first search; a last-in, first-out stack gives depth-first search; a priority queue ordered by path cost gives uniform-cost search. Recognising this shared structure makes all of them easy to write and compare.

Comparing them

AlgorithmComplete?Optimal?MemoryGood for
Breadth-firstYes, if branching is finiteYes, when every step costs the sameHigh: stores a whole levelFewest steps, such as degrees of separation
Depth-firstNo, can go down endless pathsNoLow: stores one pathDeep spaces with many solutions; puzzles with backtracking
Uniform-costYes, if costs are positiveYesCan be highCheapest routes with varied costs
Iterative deepeningYesYes, for equal step costsLowLarge spaces where depth is unknown

The cost of being blind

With branching factor b and the shallowest solution at depth d, breadth-first search may generate about bᵈ states. With b = 10 and d = 10, that is ten billion states, and breadth-first search must keep a large share of them in memory at once. Depth-first search uses far less memory but may wander down a deep, useless branch, and without a visited set it can loop forever in graphs with cycles. Iterative deepening repeats work at shallow levels, which sounds wasteful, but because most states are at the deepest level the overhead is small, which is why it is often the preferred uninformed method for large problems.

  • Edsger Dijkstra published his shortest-path algorithm in 1959; uniform-cost search is essentially the same idea.
  • Keeping a visited set turns tree search into graph search, avoiding repeated work on states reached by different paths.
  • Uninformed search is practical for small or moderate spaces; for large ones, heuristics are needed.

Search also appears outside puzzles: social networks use breadth-first search to compute degrees of connection, web crawlers explore links in breadth-first order, and compilers use depth-first search to order the steps of a build.

How it works

  1. Put the initial state in the frontier and in a visited set.
  2. Remove the next state according to the frontier type.
  3. If it is the goal, return its path.
  4. Otherwise add each unvisited neighbour to the frontier and the visited set.
  5. Repeat until the goal is found or the frontier is empty.

In code

bfs_dfs.py
from collections import deque
import heapq

graph = {  # travel times in minutes between metro stations
    "A": {"B": 4, "C": 2}, "B": {"D": 5}, "C": {"B": 1, "D": 8, "E": 10},
    "D": {"F": 2}, "E": {"F": 3}, "F": {},
}

def bfs(start, goal):
    frontier, seen = deque([[start]]), {start}
    while frontier:
        path = frontier.popleft()
        if path[-1] == goal:
            return path
        for nxt in graph[path[-1]]:
            if nxt not in seen:
                seen.add(nxt)
                frontier.append(path + [nxt])

def dfs(start, goal):
    frontier, seen = [[start]], set()
    while frontier:
        path = frontier.pop()
        node = path[-1]
        if node == goal:
            return path
        if node not in seen:
            seen.add(node)
            frontier.extend(path + [n] for n in graph[node])

def ucs(start, goal):
    frontier, best = [(0, [start])], {}
    while frontier:
        cost, path = heapq.heappop(frontier)
        node = path[-1]
        if node == goal:
            return cost, path
        if best.get(node, float("inf")) <= cost:
            continue
        best[node] = cost
        for nxt, step in graph[node].items():
            heapq.heappush(frontier, (cost + step, path + [nxt]))

print("BFS (fewest stops):", bfs("A", "F"))
print("DFS (some path):   ", dfs("A", "F"))
print("UCS (least time):  ", ucs("A", "F"))

Output

BFS (fewest stops): ['A', 'B', 'D', 'F']
DFS (some path):    ['A', 'C', 'E', 'F']
UCS (least time):   (10, ['A', 'C', 'B', 'D', 'F'])

Try it yourself

Explore a maze

Watch an agent explore step by step. Notice how much of the maze it must visit before finding the goal when it has no sense of direction.

Fewest stops or least time?

A commuter travels from station A to station F on a metro network.

Common mistakes

  • Running DFS on a graph with cycles without a visited set.
  • Using BFS when step costs differ and expecting the cheapest route.
  • Underestimating how quickly BFS's memory grows.

Check yourself

Question 1

1. Which data structure gives breadth-first search?

Question 2

2. When is BFS guaranteed to find the cheapest path?

Question 3

3. What is DFS's main advantage?

Summary

  • Uninformed search uses only the problem definition; the frontier type decides the algorithm.
  • BFS is complete and finds fewest steps but uses lots of memory; DFS is memory-light but not complete or optimal.
  • Uniform-cost finds the cheapest path; iterative deepening combines BFS guarantees with low memory.

Read it. Now try it yourself.

Open the interactive activity

Finished reading?

Sources: Russell and Norvig, Artificial Intelligence: A Modern Approach (4th edition) · Red Blob Games: Introduction to the A* algorithm