# Proving 2 heuristics are admissible

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,

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