Artificial Intelligence - Unit 2 - Topic 2 - Uninformed Search Strategies

 

UNIT - II

2. UNINFORMED SEARCH STRATEGIES

---

Part A: Introduction to Uninformed Search

---

1. What is Uninformed Search?

Uninformed search, also known as blind search, is a search strategy that does not use any domain-specific knowledge (no heuristics) to guide the search process.

• The agent knows only the initial state, goal test, and available actions.
• It explores the search space uniformly until a solution is found.
• It’s called “uninformed” because it doesn't know how close it is to the goal.

---

2. Elements Required for Uninformed Search

Element	Description
Initial State	Starting point of the agent
Action Set	All possible actions from a given state
Transition Model	Describes results of actions
Goal Test	Checks whether the agent has reached the goal state
Path Cost	Cost of a path (used to choose the best path, if applicable)

---

Part B: Types of Uninformed Search Strategies

---

 1. Breadth First Search (BFS)

Explores the search tree level by level, from the root outward.

• Uses a Queue (FIFO).
• Always finds the shortest path in terms of steps (if all steps have equal cost).
• Complete and Optimal

Example:
Searching in a maze or map to find the shortest path to the exit.

---

2. Depth First Search (DFS)

Explores as deep as possible along one branch before backtracking.

• Uses a Stack (LIFO).
• May go deep without reaching the goal.
• Not optimal, but memory efficient.

Example:
Exploring all folder structures in a computer directory.

---

 3. Depth Limited Search

DFS with a predefined limit on how deep the search can go.

• Prevents infinite search in large or cyclic state spaces.
• Might miss the solution if the depth limit is too small.

Example:
Searching within 3 steps in a chess game.

---

 4. Iterative Deepening Search (IDS)

Combines DFS and BFS by performing DFS repeatedly with increasing depth limits.

• Uses less memory than BFS.
• Finds the shortest path like BFS.
• Best of both BFS and DFS.

Example:
Used in Chess-playing programs.

---

5. Uniform Cost Search (UCS)

Expands the node with the lowest path cost (not depth).

• Uses a Priority Queue based on path cost.
• Best for problems with different step costs.
• Complete and Optimal

Example:
Finding the cheapest route in a road map (shortest distance or time).

---

Part C: Comparison Table

Strategy	Data Structure	Complete	Optimal	Time Complexity	Space Complexity	Example Use Case
BFS	Queue (FIFO)	✅ Yes	✅ Yes	O(b^d)	O(b^d)	Shortest path finding (equal cost)
DFS	Stack (LIFO)	✅/❌	❌ No	O(b^m)	O(bm)	Solving mazes, folder search
Depth-Limited	Stack + Limit	✅/❌	❌ No	O(b^l)	O(bl)	Limited depth game solving
Iterative Deepening	Stack	✅ Yes	✅ Yes	O(b^d)	O(bd)	Game tree search (e.g., Chess)
Uniform Cost Search	Priority Queue	✅ Yes	✅ Yes	O(b^(1+⌊C*/ε))	O(b^(1+⌊C*/ε))	Cost-sensitive problems (map routing)

b = branching factor, d = depth of goal, m = max depth, C* = cost of optimal solution, ε = minimum step cost

---

Summary

• Uninformed search strategies explore the state space without any knowledge of the goal’s location.
• Suitable for general-purpose problem solving.
• Includes BFS, DFS, Depth Limited, Iterative Deepening, and Uniform Cost Search.
• Each algorithm has trade-offs in speed, memory, and optimality.
• Choose the best strategy based on problem type and resource limits.

"Uninformed search is like finding a way in the dark — you try every door until one opens the path to the goal."