In AI, problem solving by searching involves exploring a search space (all possible states or actions) to find a solution path from the initial state to the goal state.
This is used in games, pathfinding, planning, and more.
Uninformed Search is a type of search strategy where the algorithm has no knowledge about the goal's location other than how to generate next states from current states.
It doesn't use any domain-specific knowledge or heuristics.
Every search problem can be defined by:
| Search Type | Description | Complete? | Optimal? | Time Complexity |
|---|---|---|---|---|
| Breadth-First Search (BFS) | Explores all nodes at the current depth before going deeper | ✅ Yes | ✅ Yes (if cost = 1) | O(b^d) |
| Depth-First Search (DFS) | Explores as far as possible along a branch before backtracking | ✅ (if finite) | ❌ No | O(b^m) |
| Uniform Cost Search (UCS) | Expands node with lowest path cost first | ✅ Yes | ✅ Yes | O(b^c*/ε) |
| Depth-Limited Search | DFS with a depth limit to prevent infinite loops | ❌ Not always | ❌ No | O(b^l) |
| Iterative Deepening DFS (IDDFS) | Repeated DFS with increasing depth limit | ✅ Yes | ✅ Yes (if cost = 1) | O(b^d) |
Where:
- b = branching factor (average number of successors)
- d = depth of the shallowest goal node
- m = maximum depth of the tree
- c* = cost of the optimal solution
- ε = smallest cost of any step
Imagine a maze:
| Algorithm | Use When |
|---|---|
| BFS | You want the shortest path (cost = 1) |
| DFS | Memory is limited and solution is deep |
| UCS | Path cost varies and optimality is important |
| IDDFS | You want completeness + low memory usage |
| Depth-Limited | Infinite-depth problem; limit known |
Open this section to load past papers