Informed Search (also called heuristic search) uses additional knowledge (heuristics) about the problem to guide the search towards the goal more efficiently.
A heuristic is a function, denoted as h(n), that estimates the cost or distance from a given state n to the goal.
| 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 |
Evaluation function:
A* expands nodes with the lowest value first.
It balances between exploring nodes close to the start and those close to the goal.
| 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 |
| 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) |
Open this section to load past papers