Lecture 03.2: Uninformed Search (BFS & DFS)

Uninformed Search Strategies: Looking Blindly

Uninformed search (also called blind search) strategies use only the information available in the formal problem definition.

• They can generate successors and distinguish a goal state from a non-goal state.
• They have no information about whether one non-goal state is "more promising" or closer to the goal than another.

By contrast, strategies that can judge whether one non-goal state is more promising than another are called informed search or heuristic search strategies.

All uninformed search strategies are distinguished primarily by the order in which nodes are expanded.

---

Evaluation Criteria for Search Algorithms

Search strategies are evaluated across four fundamental dimensions:

1. Completeness: Is the algorithm guaranteed to find a solution when at least one exists?
2. Optimality: Does the strategy find the optimal (lowest path cost) solution?
3. Time Complexity: How long (how many generated/expanded nodes) does it take to find a solution?
4. Space Complexity: How much memory is required to perform the search (maximum size of the frontier)?

---

1. Breadth-First Search (BFS)

Breadth-First Search (BFS) is a simple strategy in which the root node is expanded first, followed by all successors of the root node, and then their successors, exploring the search tree level by level (breadth-wise).

BFS uses a First-In, First-Out (FIFO) Queue for its frontier, ensuring that nodes discovered first are expanded first.

Visualizing BFS Expansion in Search Trees

The diagram below shows node expansion order in a search tree. BFS explores all nodes at depth $k$ before any node at depth $k+1$:

Grid / Maze Navigation Example

Consider an agent navigating a 2D grid containing obstacles to reach a target goal star ($\star$):

• State: $(x, y)$ coordinate position of the agent on the grid.
• Actions: Move $\{\text{Down}, \text{Right}, \text{Left}, \text{Up}\}$.
• Frontier: A FIFO Queue storing partial path nodes ordered by depth.

At Depth 1, the agent expands the start state, queueing all valid 1-step moves. At Depth 2, it expands all 2-step neighbors, gradually fanning out like a ripple in water around obstacle walls. By Depth 12, BFS systematically visits every reachable cell at distance 12 and reaches the goal star ($\star$), guaranteeing the shortest step path.

BFS Complexity Analysis

Let $b$ be the branching factor (maximum number of successors per node) and $d$ be the depth of the shallowest goal node:

• Complete? Yes (if $b$ is finite).
• Optimal? Yes (if step cost is uniform, e.g., 1 per step, so path cost is a non-decreasing function of depth).
• Time Complexity: $1 + b + b^2 + b^3 + \dots + b^d = O(b^{d+1})$ generated nodes.
• Space Complexity: $O(b^{d+1})$ nodes stored in the frontier queue. Memory footprint is the primary bottleneck for BFS!

---

2. Depth-First Search (DFS)

Depth-First Search (DFS) plunges as deep as possible down the current search path before backtracking. It expands the deepest unexpanded node first, using a Last-In, First-Out (LIFO) Stack (or recursion).

Visualizing DFS Expansion

Notice how DFS explores down the left-most branch to maximum depth before backtracking to explore siblings:

DFS Complexity Analysis

Let $m$ be the maximum depth of the state space and $b$ be the branching factor:

• Complete? No. DFS can get trapped in infinite-depth paths or cyclic loops. (It is complete in finite state spaces if graph search checks for repeated states).
• Optimal? No. DFS returns the first goal it finds, which may be on a very deep path even if a shallow goal exists.
• Time Complexity: $O(b^m)$. Can be significantly worse than BFS if $m \gg d$, but can find goals quickly if solutions are abundant.
• Space Complexity: $O(bm)$. DFS only needs to store a single path from root to leaf along with unexpanded sibling nodes at each level. Linear space requirement is the chief advantage of DFS.