2 min read
Topic 5 of 19
05
Heuristics in Problem Solving
A heuristic is a technique used in informed search algorithms that provides an estimate of the cost or distance from a given state to the goal.
📘 Problem Solving by Searching: Heuristics
1. What is a Heuristic?
A heuristic is a technique used in informed search algorithms that provides an estimate of the cost or distance from a given state to the goal.
- Denoted as h(n): the estimated cost from node n to the goal.
- Used to guide the search process more intelligently by predicting which paths are more promising.
Think of it as a “rule of thumb” or a “best guess” that helps AI make decisions faster.
2. Why Use Heuristics?
- Improves efficiency by reducing the number of states explored.
- Helps avoid blind or exhaustive searching.
- Essential for complex or large problem spaces (e.g., games, maps, puzzles).
3. Good Heuristic Qualities
| Property | Description |
|---|---|
| Admissibility | A heuristic is admissible if it never overestimates the actual cost to reach the goal. Guarantees optimal solutions with A*. |
| Consistency (Monotonicity) | For every node and successor , the heuristic satisfies: |
| . | |
| Ensures A* doesn't need to revisit nodes. | |
| Efficiency | It should reduce the number of nodes expanded significantly. |
| Accuracy | The closer the heuristic is to the actual cost, the better. |
4. Common Heuristic Examples
| Problem | Heuristic | Explanation |
|---|---|---|
| Map routing | Straight-line distance (Euclidean) | Distance from current location to destination |
| 8-puzzle | Number of misplaced tiles | Counts how many tiles are not in correct position |
| 8-puzzle | Manhattan distance | Total distance tiles are away from their goal positions (row + column) |
| Chess | Material advantage | Value of current pieces vs. opponent’s |
5. Role in Informed Search Algorithms
| Algorithm | Use of Heuristic |
|---|---|
| Greedy Best-First Search | Uses only h(n) (chooses node that looks closest to goal) |
| A* Search | Uses f(n) = g(n) + h(n) (combines path cost + heuristic estimate) |
6. Designing Heuristics
A good heuristic should:
- Be problem-specific.
- Be easy to compute.
- Be admissible (for optimal A* results).
- Capture meaningful insights into the problem.
✅ Summary Table
| Term | Definition |
|---|---|
| Heuristic (h(n)) | Estimated cost from node n to the goal |
| Admissible | Never overestimates the actual cost |
| Consistent | Satisfies triangle inequality: |
| Role | Guides search, improves efficiency |
Past Papers
Open this section to view and download past papers
Click on Show Past Papers to load available exam papers.