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 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).

StepExpandChoice and reason
1Aradchildren Sibiu 253, Timisoara 329, Zerind 374, pick Sibiu
2Sibiuchildren Fagaras 176, Rimnicu Vilcea 193, Oradea 380, Arad 366, pick Fagaras
3Fagaraschild Bucharest 0, goal

Path Arad, Sibiu, Fagaras, Bucharest costs , but the best route costs 418. Greedy is fast here but not optimal.

Properties

CriterionGreedy
CompleteNo, 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
OptimalNo

Combining with the real cost so far fixes both problems, which is A* search.