# How is this "pathmax modification," $f(n^\prime) = \max(g(n^\prime) + h(n^\prime), f(n))$, useful?

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.

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

• We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing. Please edit your post accordingly.
– D.W.
Oct 26, 2022 at 16:43
• 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.
– D.W.
Oct 26, 2022 at 16:44
• @D.W. This is just what was mentioned on some slides. I was hoping that someone more knowledgeable would clarify. Oct 26, 2022 at 16:50
• 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. Oct 26, 2022 at 17:48
• @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). Oct 26, 2022 at 17:53