Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Evaluation Functions
Best-first search expands the most desirable frontier node, judged by an evaluation function. Two building blocks:
- path cost : cost from the initial state to node , it says nothing about the cost still to go
- heuristic : an estimate of the cheapest cost from to a goal, depends only on the state at , with
A heuristic is admissible if it never overestimates the true cost to the goal. Heuristics are problem specific and useful but fallible.
Greedy Search
Greedy search expands the node that appears closest to the goal, using only :
function GREEDY-SEARCH(problem) returns solution:
return BEST-FIRST-SEARCH(problem, h)Example: Arad to Bucharest
Heuristic = straight line distance to Bucharest (Arad 366, Sibiu 253, Timisoara 329, Zerind 374, Fagaras 176, Rimnicu Vilcea 193, Oradea 380, Bucharest 0).
| Step | Expand | Choice and reason |
|---|---|---|
| 1 | Arad | children Sibiu 253, Timisoara 329, Zerind 374, pick Sibiu |
| 2 | Sibiu | children Fagaras 176, Rimnicu Vilcea 193, Oradea 380, Arad 366, pick Fagaras |
| 3 | Fagaras | child Bucharest 0, goal |
Path Arad, Sibiu, Fagaras, Bucharest costs , but the best route costs 418. Greedy is fast here but not optimal.
Properties
| Criterion | Greedy |
|---|---|
| Complete | No, can get stuck in loops (e.g. Iasi to Fagaras keeps going to Neamt, which is closer in straight line but a dead end) |
| Time | , a good heuristic cuts this a lot |
| Space | , keeps all nodes in memory |
| Optimal | No |
Combining with the real cost so far fixes both problems, which is A* search.