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:

1. Start at S → Expand → {A, B}

2. Next level → Expand A → {C, D}

3. 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:

1. Start at S → Go to A → C (dead end).

2. Backtrack → A → D → E (dead end).

3. 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:

1. Start at S → Insert {A(2), B(5)}.

2. Expand A first → {C(6), D(8)}.

3. 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.

---