AI Search Strategies

Uninformed vs Informed Search Algorithms

CSET-381 | Lecture 3.3 | Artificial Intelligence

Search Strategy Types

🔍

Uninformed Search

Also called "Blind Search"

• No knowledge about goal location
• Exhaustive exploration required
• Strategies don't use goal information

🎯

Informed Search

Uses heuristic information

• Takes goal location into account
• More efficient path finding
• Uses domain knowledge

🌊 Breadth-First Search (BFS)

Level-by-Level Exploration:

Level 0: [S] ← Start
Level 1: [A, B, C]
Level 2: [D, E, F, G]
Level 3: [H, I, J, K, L, M]

Queue (FIFO):
Front → [A, B, C, D, E] ← Rear

Path Found: S → A → D → Goal

Key Characteristics:

  • Strategy: Explore all nodes at current depth before going deeper
  • Data Structure: Queue (FIFO)
  • Complete: Yes (finds solution if exists)
  • Optimal: Yes (finds shortest path)
  • Time: O(b^d)
  • Space: O(b^d)
  • Best for: Finding shortest path solutions

📊 Depth-First Search (DFS)

Deep Exploration:

Path: S → A → D → H → ...
↓ (if no goal, backtrack)
Path: S → A → E → I → ...
↓ (continue until goal found)

Stack (LIFO):
Top → [H, I, E, A, S] ← Bottom

Backtracking:
When stuck, pop from stack
Continue with next option

Key Characteristics:

  • Strategy: Go as deep as possible, then backtrack
  • Data Structure: Stack (LIFO)
  • Complete: No (can get stuck in infinite paths)
  • Optimal: No (may find suboptimal solution)
  • Time: O(b^m)
  • Space: O(bm) - Memory efficient!
  • Best for: Memory-constrained environments

🔄 Iterative Deepening Search (IDS)

Progressive Depth Limits:

Depth 0: [S]
Depth 1: [S] → [A, B, C]
Depth 2: [S,A,B,C] → [D,E,F,G]
Depth 3: Continue deeper...

Combines BFS + DFS:
✓ BFS: Optimal solution
✓ DFS: Memory efficiency

Repeated Work: Acceptable overhead

Key Characteristics:

  • Strategy: DFS with increasing depth limits
  • Data Structure: Stack with depth counter
  • Complete: Yes (like BFS)
  • Optimal: Yes (finds shortest path)
  • Time: O(b^d)
  • Space: O(bd) - Best of both worlds!
  • Best for: When optimal depth is unknown

📊 Algorithm Comparison

Algorithm Complete? Optimal? Time Complexity Space Complexity Key Advantage
BFS ✓ Yes ✓ Yes O(b^d) O(b^d) Guaranteed shortest path
DFS ✗ No* ✗ No O(b^m) O(bm) Memory efficient
IDS ✓ Yes ✓ Yes O(b^d) O(bd) Best of both worlds

Legend: b = branching factor, d = depth of optimal solution, m = maximum depth
*DFS is complete only in finite state spaces

🎯 Key Takeaways

🌊 BFS - When to Use

Perfect when you need the shortest path and have sufficient memory. Ideal for small to medium search spaces where optimality is crucial.

📊 DFS - When to Use

Choose DFS when memory is limited and you're exploring deep solution spaces. Great for constraint satisfaction problems.

🔄 IDS - When to Use

The best general-purpose algorithm combining BFS optimality with DFS memory efficiency. Use when you're unsure about solution depth.

🎯 Algorithm Selection

Consider: available memory, need for optimal solution, problem depth, and branching factor when choosing your search strategy.

1 / 7