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.

  • $\begingroup$ We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing. Please edit your post accordingly. $\endgroup$
    – D.W.
    Commented Oct 26, 2022 at 16:43
  • $\begingroup$ What resources have you checked? Have you looked for a textbook that explains pathmax in more detail? Slides or bullet points are not an ideal learning resource; they are not a substitute for a textbook, lecture notes, or other primary resource. $\endgroup$
    – D.W.
    Commented Oct 26, 2022 at 16:44
  • $\begingroup$ @D.W. This is just what was mentioned on some slides. I was hoping that someone more knowledgeable would clarify. $\endgroup$ Commented Oct 26, 2022 at 16:50
  • $\begingroup$ The heuristic will be monotone, and furthermore the higher value (as long as it's admissible) the better. Meaning that if the heuristic value ($f+g$) actually drops from one node to the next, we can just keep the higher value. $\endgroup$
    – Pål GD
    Commented Oct 26, 2022 at 17:48
  • $\begingroup$ @PålGD Hmm, yes, I think your comment touches on something that I suspect I'm not fully understanding. I've been doing some thinking and have some related, fundamental questions to ask about heuristics (in another question). $\endgroup$ Commented Oct 26, 2022 at 17:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.