I am studying the concept of heuristics in search algorithms, and the $A^*$ search algorithm in particular. I am told the following:
Greedy search minimises estimated path-cost to goal.
- But it's neither optimal nor even always complete.
Uniform-cost search minimises path-cost from the start.
- Complete and optimal, but expensive.
Can we get the best of both worlds?
- Yes - use estimate of total path-cost as our heuristic.
$f(n) = g(n) + h(n)$
- $g(n) =$ actual cost from start to $n$
- $h(n) =$ estimated cost from $n$ to goal
- $f(n) =$ estimated total cost from start to goal via n
$A^*$ search is complete and optimal under two conditions:
- The heuristic must be admissible.
- The costs along a given path must be monotonic.
A heuristic $h$ is admissible iff $h(n) \le h^*(n)$ for all $n$.
- $h^*(n)$ is the actual path-cost from $n$ to the goal.
i.e., $h$ must never over-estimate the cost.
- e.g., $h_{SLD}$ never over-estimates
A heuristic $h$ is monotonic iff $h(n) \le c(n, a, n^\prime) + h(n^\prime)$, for all $n$, $a$, $n^\prime$.
- $n^\prime$ is a successor to $n$ by action $a$. – This is basically the triangle inequality.
- $n$ to the goal "directly" should be no more than $n$ to the goal via any successor $n^\prime$.
Pathmax modification: $f(n^\prime) = \max(g(n^\prime) + h(n^\prime), f(n))$.
Note that optimal here means "finds the best goal."
We are not arguing that $h$ itself is optimal in any sense.
How is this "pathmax modification," $f(n^\prime) = \max(g(n^\prime) + h(n^\prime), f(n))$, useful? I can understand what it's doing by looking at the individual components, but I don't really understand the point of it. I get the impression that I'm missing/misunderstanding/overlooking something here.
