3 min read
Topic 3 of 19
03
Problem Solving by Searching: Informed searching
Informed Search (also called heuristic search ) uses additional knowledge (heuristics) about the problem to guide the search towards the goal more efficiently.
📘 Problem Solving by Searching: Informed Searching
1. What is Informed Search?
Informed Search (also called heuristic search) uses additional knowledge (heuristics) about the problem to guide the search towards the goal more efficiently.
- Unlike uninformed search, it uses information about the goal’s location.
- This helps reduce the number of states explored and find solutions faster.
2. What is a Heuristic?
A heuristic is a function, denoted as h(n), that estimates the cost or distance from a given state n to the goal.
- Good heuristics improve search efficiency.
- Example: In pathfinding, h(n) might be the straight-line distance from node n to the goal.
3. Popular Informed Search Algorithms
| Algorithm | Description | Uses | Optimal? | Complete? |
|---|---|---|---|---|
| Greedy Best-First Search | Expands the node that appears closest to the goal based on h(n) | Fastest search when heuristic is good | No | No (can get stuck) |
| A* | Combines path cost so far (g(n)) + heuristic estimate (h(n)) to select nodes | Finds optimal path efficiently | Yes (if h(n) is admissible) | Yes |
4. How Does A* Work?
-
Evaluation function:
- = cost from start node to current node
- = estimated cost from to goal
-
A* expands nodes with the lowest value first.
-
It balances between exploring nodes close to the start and those close to the goal.
5. Properties of Heuristics
| Property | Meaning |
|---|---|
| Admissible | Heuristic never overestimates the true cost to reach the goal (always optimistic) |
| Consistent (Monotonic) | For every node and successor , , where is the step cost |
| Effective heuristic | One that is as close as possible to the actual cost |
6. Example: Finding Route on a Map
- Goal: Find shortest path from city A to city B.
- Heuristic (h(n)): Straight-line distance (Euclidean distance) to city B.
- Using A*, the search will prioritize routes that seem promising based on the combined actual cost so far and the heuristic estimate.
✅ Summary
| Concept | Explanation |
|---|---|
| Informed Search | Search that uses heuristics to guide search |
| Heuristic (h(n)) | Estimates cost from current state to goal |
| Greedy Best-First | Uses only heuristic, fast but not guaranteed |
| A* | Uses cost so far + heuristic, guaranteed optimal (with admissible heuristic) |
Past Papers
Open this section to view and download past papers
Click on Show Past Papers to load available exam papers.