Uninformed Search Techniques
Uninformed Search Techniques
1. Introduction
Uninformed search strategies, also known as blind search, are techniques that explore the search space without using any heuristic knowledge about the problem.
-
They only use the problem definition: initial state, operators, and goal test.
-
These algorithms may not be efficient, but they form the foundation of AI problem-solving.
2. Example Graph (Common for All Strategies)
We will use this search graph to explain each strategy:
(S)
/ \
(A) (B)
/ \ \
(C) (D) (G)
|
(E)
-
Start Node (S)
-
Goal Node (G)
3. Types of Uninformed Search
3.1 Breadth-First Search (BFS)
-
Approach: Explores all nodes at the current depth before going deeper.
-
Data Structure: Queue (FIFO).
-
Properties:
-
Complete: ✅ Yes
-
Optimal: ✅ Yes (if step costs are equal)
-
Process on Graph:
-
Start at S → Expand → {A, B}
-
Next level → Expand A → {C, D}
-
Expand B → {G} ✅ Goal found.
Solution Path: S → B → G
Characteristic: Finds the shortest path in steps.
3.2 Depth-First Search (DFS)
-
Approach: Explores as deep as possible before backtracking.
-
Data Structure: Stack (LIFO) or recursion.
-
Properties:
-
Complete: ❌ No (may get stuck in infinite path)
-
Optimal: ❌ No
-
Process on Graph:
-
Start at S → Go to A → C (dead end).
-
Backtrack → A → D → E (dead end).
-
Backtrack → S → B → G ✅ Goal found.
Solution Path: S → B → G
Characteristic: May not give shortest path, but memory-efficient.
3.3 Depth-Limited Search (DLS)
-
Approach: DFS but limited to depth = L.
-
Properties:
-
Complete: ✅ Yes (if depth of goal ≤ L)
-
Optimal: ❌ No
-
Process on Graph:
-
If L = 2 → S → A → C, D and S → B → stops (cannot reach G). ❌ Failure.
-
If L = 3 → can expand deeper and reach G ✅.
Characteristic: Works only when approximate depth of solution is known.
3.4 Iterative Deepening DFS (IDDFS)
-
Approach: Runs DFS repeatedly with increasing depth limits.
-
Properties:
-
Complete: ✅ Yes
-
Optimal: ✅ Yes (for uniform step cost)
-
Process on Graph:
-
Depth 0 → {S} (No goal).
-
Depth 1 → {S, A, B} (No goal).
-
Depth 2 → {S, A, B, C, D, G} ✅ Goal found.
Solution Path: S → B → G
Characteristic: Combines BFS optimality with DFS memory efficiency.
3.5 Uniform Cost Search (UCS)
-
Approach: Expands the node with lowest cumulative path cost.
-
Data Structure: Priority Queue.
-
Properties:
-
Complete: ✅ Yes (if step costs > 0)
-
Optimal: ✅ Yes
-
Assume Edge Costs:
-
S → A = 2
-
S → B = 5
-
A → C = 4
-
A → D = 6
-
B → G = 2
Process on Graph:
-
Start at S → Insert {A(2), B(5)}.
-
Expand A first → {C(6), D(8)}.
-
Next expand B(5) → {G(7)} ✅ Goal found.
Solution Path: S → B → G (Cost = 7).
Characteristic: Finds least-cost solution, not just shortest path.
4. Comparison of Strategies
| Strategy | Data Structure | Complete? | Optimal? | Example Path Found |
|---|---|---|---|---|
| BFS | Queue (FIFO) | Yes | Yes (equal costs) | S → B → G |
| DFS | Stack (LIFO) | No | No | S → B → G (after exploring deep) |
| DLS | Stack + Limit | Yes (if L ≥ depth) | No | Fails if L < goal depth |
| IDDFS | Stack (iterative) | Yes | Yes | S → B → G |
| UCS | Priority Queue | Yes | Yes | S → B → G (least cost) |
5. Summary
-
BFS → Level-order, finds shortest path.
-
DFS → Deep search, not guaranteed shortest.
-
DLS → DFS with cutoff depth.
-
IDDFS → Hybrid of BFS + DFS.
-
UCS → Expands least-cost path, always optimal.
Uninformed strategies are the foundation of AI problem-solving and prepare the ground for more advanced informed (heuristic) search methods.
Labels: AI(BMC-021) Unit-2