We have $h_1(n)$ and $h_2(n)$ which are both admissible heuristics. We know that $h_1(n) < h_2(n)$ for every state $n$ in a search problem.

Now we are given two heuristics $h_3(n)=\frac{h_1(n)}{1+h_2(n)}$ and $h_4(n)=\frac{h_2(n)}{1+h1(n)}$ and we want to prove $h_3(n)$ and $h_4(n)$ are both admissible.


The only additional constraint which is required for $h_3$ and $h_4$ to be admissible is that both $h_1(n)$ and $h_2(n)$ return non-negative values for any state $n$, but this is always accomplished ---even if a heuristic function might return a negative value it just suffices to take the maximum between the value returned and 0, and this operation clearly preserves admissibility.

Thus, given that $h_1(n), h_2(n) \geq 0$ for every state $n$ and that both are admissible, it is easy to see that the values of $h_3(n)$ are upper bounded by those of $h_1(n)$ (the maximum value taking place when $h_2(n)=0$) Since $h_1$ is admissible so it is $h_3$; conversely, if $h_2(n)$ returns any strictly positive value then $h_3(n) < h_1(n)$. Now, if $h_1(n)$ is not overestimating the effort to reach the goal, then $h_3(n)$ is neither as well and thus, $h_3$ is admissible in this case also.

The proof of admissibility of $h_4$ follows the same lines.

Note that in these proofs it is never required for any heuristic function to strictly dominate another, i.e., the condition $h_1(n) < h_2(n)$ is useless and not necessary at all. The only important requirement is that none ever return negative values, but this is a trivial requirement.

To conclude, I think this is mostly a theoretical exercise. Note that as mentioned above $h_3$ and $h_4$ are upper bounded by $h_1$ and $h_2$ respectively so that, in other words, they are less informed than them. In other words, these transformations are of no interest.

Hope this helps,

  • $\begingroup$ Thanks for the help. $\endgroup$ – Alex Apr 19 '20 at 12:54
  • $\begingroup$ You are very welcome @Alex! $\endgroup$ – Carlos Linares López Apr 20 '20 at 1:38

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.