4.9 Admissible and consistent heuristics

Work through these

• State admissibility: h(n) is never greater than the true remaining cost h*(n)

  A heuristic is admissible when it never overestimates what remains. That single condition is what makes the optimality guarantee possible.

• Prove that A* with tree search is optimal when h is admissible

  The proof is short and worth following: an optimal solution cannot be overlooked in favour of a worse one when estimates never overshoot. Following it once makes the condition memorable rather than arbitrary.

• State consistency: h(n) at most c(n,a,n') + h(n'), and show f is non-decreasing along a path

  Consistency is a stronger local condition saying the estimate never drops faster than the step cost, and it makes the total score never decrease along a path. This is what makes graph search safe.

• Apply both results: admissible gives tree-search optimality, consistent gives graph-search optimality

  Admissibility gives you optimality when revisits are allowed; consistency gives it when they are not. Knowing which guarantee you have depends on which condition your heuristic satisfies.

• Work numerical heuristic problems on small graphs

  Small numeric problems on graphs, checking heuristics against both conditions. These are exactly the examination questions, and they are quick once the definitions are firm.