Lecture 03.2: Uninformed Search (BFS & DFS)

Uninformed Search Strategies: Looking Blindly

Uninformed search strategies use only the information available in the problem definition. They can generate successors and distinguish a goal state from a non-goal state, but they have no concept of which non-goal states are "more promising."

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

Search algorithms are evaluated based on four criteria:

1. Completeness: Is the algorithm guaranteed to find a solution when there is one?
2. Optimality: Does the strategy find the optimal (lowest cost) solution?
3. Time complexity: How long does it take to find a solution?
4. Space complexity: How much memory is needed to perform the search?

---

1. Breadth-First Search (BFS)

In BFS, the root node is expanded first, followed by all successors of the root node, and then their successors, level by level. It uses a FIFO Queue to ensure nodes are visited in the order they are discovered.

Visualizing BFS Expansion

The following tree demonstrates the order of node expansion in BFS. Notice how it completes an entire depth level before moving deeper.

BFS Complexity

Assume every node has $b$ successors (branching factor), and the shallowest goal is at depth $d$.

• Complete? Yes (if $b$ is finite).
• Optimal? Yes (but only if the path cost is a non-decreasing function of the depth, e.g., if step cost is always 1).
• Time Complexity: $1 + b + b^2 + b^3 + ... + b^d = O(b^{d+1})$.
• Space Complexity: $O(b^{d+1})$. Every node must reside in memory (the queue). Space is the biggest problem for BFS!

---

2. Depth-First Search (DFS)

In DFS, the search algorithm dives as deep as possible down one path before backtracking. It expands the deepest unexpanded node first, typically using a LIFO Stack (or recursion).

Visualizing DFS Expansion

Notice how DFS plunges down the left-most branch entirely before exploring siblings.

DFS Complexity

Assume a maximum depth of the state space $m$, and branching factor $b$.

• Complete? No. It fails in infinite-depth spaces or spaces with loops. It can be made complete in finite spaces if modified to avoid repeated states.
• Optimal? No. It will return the first solution it finds, even if a shallower one exists on another branch.
• Time Complexity: $O(b^m)$. This is terrible if $m$ is much larger than $d$. However, if solutions are dense, it may be much faster than BFS.
• Space Complexity: $O(bm)$. DFS only needs to store a single path from the root to a leaf node, alongside the unexpanded sibling nodes for each node on the path. This linear space requirement is its biggest advantage!