4.1 What is Problem Solving in AI?
AI agents often face situations where:
- The goal is known
- The current state is known
- But the steps to reach the goal are unknown
In such cases, they search through a space of possible actions and outcomes to reach a solution.
4.2 Components of a Problem
| Component | Description | Example (8-puzzle) |
|---|---|---|
| Initial State | Starting point | Tiles in a scrambled order |
| Actions | Possible moves from each state | Slide left, right, up, down |
| Transition Model | Result of an action | New arrangement of tiles after a move |
| Goal Test | Checks if current state = goal | Are all tiles in order? |
| Path Cost | Cost for the solution (e.g., steps taken) | Each move = 1 step |
4.3 State Space
The state space is the set of all possible configurations (states) the system can be in.
Example: In 8-puzzle, there are 9! = 362,880 possible states (positions of 9 tiles).
4.4 Search Types: Informed vs. Uninformed
| Type | Has Heuristic? | Examples |
|---|---|---|
| Uninformed | ❌ | BFS, DFS, UCS |
| Informed | ✅ | Greedy, A* Search |
4.5 Uninformed (Blind) Search Algorithms
Breadth-First Search (BFS)
Explores the shallowest (closest to root) nodes first.
- Complete
- Optimal (if cost = 1 per step)
- Memory-intensive
Time/Space Complexity: O(bd)
Depth-First Search (DFS)
Explores the deepest node first.
- Space-efficient
- Not complete (can get stuck in infinite paths)
- Not optimal
Time Complexity: O(bm)
Uniform Cost Search (UCS)
Expands the node with the lowest path cost.
- Complete
- Optimal
- Slower if many nodes have equal costs
4.6 Informed (Heuristic) Search
Informed search algorithms use problem-specific knowledge to guide the search.
What is a Heuristic?
A heuristic is a function that estimates the cost to reach the goal from a given node n.
Common Heuristics:
- 8-puzzle: Number of misplaced tiles, or Manhattan distance
- Pathfinding: Straight-line distance (Euclidean) to the goal
- Word ladder: Number of letters that differ from goal word
4.7 Frequently Asked Exam Questions
- Define BFS and explain how it differs from DFS.
- Compare the performance of UCS vs. IDS.
- Solve a simple state graph using UCS and list node expansions.
- Explain iterative deepening search with an example.