Uninformed Search
What Is Uninformed Search?
An uninformed (or blind) search algorithm explores a graph using only the structure of the search problem — the start node, the successor function, and the goal test — without any estimate of how close a given node is to a solution (Russell and Norvig 2020). This contrasts with informed (heuristic) search methods such as A*, which use domain knowledge to guide exploration.
Motivation
Uninformed search matters because it is what remains when a problem offers no reliable heuristic. It gives the reference guarantees — completeness, optimality under unit costs, and memory use — against which more specialized search methods are judged. Understanding these baselines also makes the trade-offs in A* search, adversarial search, and constraint search much clearer.
Uninformed search is the baseline: correct and general, but potentially slow. The three principal methods are breadth-first search, depth-first search, and iterative deepening search.
Comparison
Let \(b\) be the branching factor, \(d\) the depth of the shallowest solution, and \(m\) the maximum depth of the graph.
| Property | BFS | DFS | IDS |
|---|---|---|---|
| Complete | yes | yes (finite graphs) | yes |
| Optimal (unit cost) | yes | no | yes |
| Time complexity | \(O(b^d)\) | \(O(b^m)\) | \(O(b^d)\) |
| Space complexity | \(O(b^d)\) | \(O(bm)\) | \(O(bd)\) |
Completeness
All three methods are complete on finite graphs with cycle detection. DFS can fail on infinite graphs by descending forever into an unbounded branch that contains no solution. BFS and IDS avoid this by processing nodes in non-decreasing depth order, guaranteeing a solution at depth \(d\) is found before any node at depth \(d+1\).
Optimality
BFS and IDS both return a solution at the minimum depth. (proof for BFS, proof for IDS) For graphs where all edges have unit cost, minimum depth equals minimum cost, so both are cost-optimal. DFS returns the first solution encountered along the chosen path, which may be arbitrarily deep. (proof)
Time Complexity
BFS and IDS share the same asymptotic time cost \(O(b^d)\). IDS re-explores nodes at shallower depths on each iteration, but the total extra work is a small constant factor \(b/(b-1)\). (proof) DFS can be faster in practice if a solution happens to lie along the first branch explored, but in the worst case it visits all \(O(b^m)\) nodes.
Space Complexity
Space is where the methods diverge most sharply:
- BFS stores the entire frontier at depth \(d\): \(O(b^d)\) nodes. For \(b = 10\) and \(d = 10\) this is \(10^{10}\) nodes — impractical without enormous memory.
- DFS stores only the current path and its unexplored siblings: \(O(bm)\) nodes. Memory use is linear in the search depth.
- IDS inherits DFS’s memory profile: \(O(bd)\) nodes. It has the same space advantage as DFS while being complete and optimal like BFS.
When to Use Each
BFS is appropriate when:
- The solution depth \(d\) is small and memory is not a concern.
- A level-by-level traversal is itself the goal (e.g., finding all nodes at distance exactly \(k\)).
DFS is appropriate when:
- Memory is severely limited.
- Optimality is not required and solutions may be deep.
- The goal is to visit every node (e.g., topological sort, cycle detection, connected components), not to find the shallowest one.
IDS is the default uninformed strategy when:
- The solution depth is unknown or large.
- Both completeness and optimality are required.
- Memory is a concern.
IDS strictly dominates BFS on space with equivalent asymptotic time, and it is complete and optimal where DFS is not. In most tree-search settings where no heuristic is available, IDS is the preferred choice.