AI Notes
Learn uninformed search algorithms: BFS, DFS, DLS, IDS. Complete guide for artificial intelligence students. BTech notes 2024.
What is Uninformed Search?
Uninformed search, also called blind search, refers to search strategies that explore the state space without any domain-specific knowledge about how close a given state might be to the goal. These algorithms have no heuristic guidance—they rely entirely on the structure of the search tree or graph and the order in which nodes are generated and expanded.
Despite their simplicity, uninformed search strategies form the theoretical backbone of AI search. Understanding them is essential before studying informed (heuristic) search, because concepts like completeness, optimality, time complexity, and space complexity are most clearly demonstrated in the uninformed setting.
The five classical uninformed search strategies are: Breadth-First Search (BFS), Depth-First Search (DFS), Depth-Limited Search (DLS), Iterative Deepening Search (IDS), and Uniform Cost Search (UCS). Each makes different trade-offs between memory, time, and solution quality.
Breadth-First Search (BFS)
BFS explores the search tree level by level. It uses a FIFO queue to maintain the frontier, ensuring that all nodes at depth d are expanded before any node at depth d+1.
Algorithm Pseudocode
function BFS(problem):
node ← problem.initial_state
if node is goal: return solution
frontier ← Queue containing node
explored ← empty set
while frontier is not empty:
node ← frontier.dequeue()
explored.add(node)
for each action in problem.actions(node):
child ← result of applying action to node
if child not in explored and child not in frontier:
if child is goal: return solution
frontier.enqueue(child)
return failureWorked Example: BFS Trace
Consider a graph with edges: A→B, A→C, B→D, B→E, C→F, C→G. Goal is G.
| Step 1: Frontier = [A] | Expand A | children B, C |
| Step 2: Frontier = [B, C] | Expand B | children D, E |
| Step 3: Frontier = [C, D, E] | Expand C | children F, G |
| Step 4: G found! Path: A | C → G |
BFS explored depth 0 (A), then depth 1 (B, C), and found G at depth 2. It always finds the shallowest goal first.
Properties
- Complete: Yes (if branching factor b is finite)
- Optimal: Yes (if all step costs are identical)
- Time Complexity: O(b^d) where d is the depth of the shallowest goal
- Space Complexity: O(b^d) — stores the entire frontier level
The space complexity is BFS's major weakness. At branching factor 10 and depth 12, BFS would store approximately 10^12 nodes—impractical for most machines.
Depth-First Search (DFS)
DFS explores as deep as possible before backtracking. It uses a LIFO stack (or recursion) for the frontier, always expanding the most recently generated node.
Algorithm Pseudocode
function DFS(problem):
frontier ← Stack containing initial_state
explored ← empty set
while frontier is not empty:
node ← frontier.pop()
if node is goal: return solution
explored.add(node)
for each child of node (reverse order for left-to-right):
if child not in explored:
frontier.push(child)
return failureWorked Example: DFS Trace
Same graph: A→B, A→C, B→D, B→E, C→F, C→G. Goal is G.
| Step 1 | Stack = [A] | Pop A, push C, B (B on top) |
| Step 2 | Stack = [C, B] | Pop B, push E, D (D on top) — Wait, actually push children |
| Step 2: Stack = [C, B] | Pop B | children D, E → push E, D |
| Step 3: Stack = [C, E, D] | Pop D | no children (leaf) |
| Step 4: Stack = [C, E] | Pop E | no children (leaf) |
| Step 5: Stack = [C] | Pop C | children F, G → push G, F |
| Step 6: Stack = [G, F] | Pop G | GOAL FOUND! Path: A → C → G |
DFS explored A → B → D → E → C → G. It went deep into the left branch first.
Properties
- Complete: No (can loop in infinite graphs without cycle detection)
- Optimal: No (may find a deeper solution before a shallower one)
- Time Complexity: O(b^m) where m is the maximum depth
- Space Complexity: O(b·m) — only stores the current path plus siblings
The key advantage of DFS is its linear space complexity. For problems with deep solutions where memory is limited, DFS is often the practical choice.
Depth-Limited Search (DLS)
DLS addresses DFS's incompleteness in infinite state spaces by imposing a depth limit l. The algorithm behaves exactly like DFS but refuses to expand nodes beyond depth l.
| if node is goal | return solution |
| if limit == 0 | return cutoff |
| if result == cutoff | cutoff_occurred ← true |
| else if result ≠ failure | return result |
| if cutoff_occurred | return cutoff |
| else | return failure |
If the goal is within depth l, DLS finds it. If l < d (solution depth), DLS returns "cutoff" indicating the limit was too shallow. Choosing l requires domain knowledge or trial.
Iterative Deepening Search (IDS)
IDS combines the space efficiency of DFS with the completeness of BFS. It runs DLS repeatedly with increasing depth limits: l = 0, 1, 2, 3, ... until a solution is found.
Algorithm
function IDS(problem):
for depth = 0 to ∞:
result ← DLS(problem, depth)
if result ≠ cutoff:
return resultWhy IDS Works
The repeated expansion of shallow nodes seems wasteful, but the overhead is minimal. Consider branching factor b = 10:
The overhead factor is b/(b-1). For b = 10, IDS expands only about 11% more nodes than BFS while using O(b·d) memory instead of O(b^d). This makes IDS the preferred uninformed search strategy when solution depth is unknown.
Properties
- Complete: Yes
- Optimal: Yes (if step costs are uniform)
- Time Complexity: O(b^d)
- Space Complexity: O(b·d)
Comparison Table
| Strategy | Complete? | Optimal? | Time | Space |
|---|---|---|---|---|
| BFS | Yes | Yes* | O(b^d) | O(b^d) |
| DFS | No | No | O(b^m) | O(bm) |
| DLS | No | No | O(b^l) | O(bl) |
| IDS | Yes | Yes* | O(b^d) | O(bd) |
| UCS | Yes | Yes | O(b^(C*/ε)) | O(b^(C*/ε)) |
*When all step costs are equal.
When to Use Each Strategy
BFS: When the solution is shallow and memory is not a constraint. Network broadcasting, shortest-path in unweighted graphs.
DFS: When solutions are deep and any solution suffices. Topological sorting, maze generation, constraint satisfaction with backtracking.
IDS: When you want BFS guarantees with DFS memory. The default choice when solution depth is unknown—always prefer IDS over plain BFS.
DLS: When you have strong domain knowledge about maximum solution depth. Chess engines with fixed-depth evaluation.
Common Interview Questions
Q: Why is IDS preferred over BFS despite re-expanding nodes? A: The space savings from O(b^d) to O(bd) far outweigh the ~11% time overhead (for typical b ≥ 2). Memory is usually the bottleneck, not time.
Q: Can DFS find optimal solutions? A: Only in specific cases where all solutions are at the same depth (like in satisfiability problems). In general graphs, DFS may find arbitrarily suboptimal solutions.
Q: How does cycle detection affect completeness? A: Without cycle detection, DFS can loop forever in cyclic graphs. Adding a visited set makes DFS complete for finite graphs but increases space complexity. Graph-search (with explored set) versus tree-search (without) is the key distinction.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Uninformed Search Strategies - AI Fundamentals.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Artificial Intelligence topic.
Search Terms
artificial-intelligence, artificial intelligence, artificial, intelligence, search, algorithms, uninformed, uninformed search strategies - ai fundamentals
Related Artificial Intelligence Topics