Heuristic Functions

Oracle function

Heuristic function

Heuristic Adequancy

Monotonicity (or Local Admissibility)

Variable-Cost Actions

Informedness

Given two heuristics h’(n) and h’‘(n), if:

  1. For all n, h’(n) ≤ h’‘(n)
  2. There exists n such that h’(n) < h’‘(n)
  3. For all n, h’‘(n) ≤ h(n) (i.e., h’‘(n) is monotonic)

then we conclude that h’‘(n) is better informed than h’(n).