I got this question that's been troubling me for some time.

If $h_1$ and $h_2$ are admissible heuristic functions, prove that $h_3 = (c-1)\,h_1 + c\,h_2$, $0 < c < 1$, is also an admissible heuristic function.

The thing that I get stuck on, and maybe get a little tunnel-vision, is that $(c-1)$ is negative which prevents me from "building" the inequality starting from $h_1(n) \leq a(n)$, where $a(n)$ the actual cost to the end node. Any help with a mathematical explanation or using an example is greatly appreciated.

  • 1
    $\begingroup$ That looks like a typo to me. Convex combinations require all coefficients to be >=0 and the sum of all coefficients to be 1. So a (1-c) would make more sense here. $\endgroup$ – adrianN Sep 6 '17 at 10:17
  • $\begingroup$ @adrianN I can't really give a definitive answer to this. It might have been a typo but i can't really confirm it, since this problem is from 3 years ago. The only thing i can say is that i got a lot of people, except the original author, confirming that, that was the problem. (c-1) $\endgroup$ – pascalH Sep 6 '17 at 10:30
  • 1
    $\begingroup$ It's a typo. It should have been $1-c$. People confirm it since the typo is in the source, but that doesn't mean it's not a typo. It's a classical example of the importance of having independent pieces of evidence. $\endgroup$ – Yuval Filmus Sep 6 '17 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.