# If $h(s)$ is an admissible heuristic, is $\sqrt{h(s)}$ admissible?

I was thinking yes because $0 \leq \sqrt{h(s)} < h(s)$ but I'm not entirely sure.

Yes, the basic condition for a heuristic being admissible is that it is always less than the actual cost, and the rest follows by the transitivity of the less-than-or-equal-to relation.

See the all-knowing wiki for the background. I'll steal the notation from there for some measure of consistency.

Or, in a rather unnecessary mathematical formulation, if $\forall s, h(s) \leq h^{\ast}(s)$, where $h^{*}(s)$ is the actual cost then $h$ is admissible.

Assuming $x \in \mathbb{R}^{\geq 0}$ and (thanks Yuval) $x\geq 1$ (i.e. we don't have some weird situation where $\leq$ breaks, etc.), $\sqrt{x} \leq x$.

So $$\forall s, h(s) \leq h^{\ast}(s) \Rightarrow \forall s, \sqrt{h(s)} \leq h(s) \leq h^{\ast}(s) \Rightarrow \forall s, \sqrt{h(s)} \leq h^{\ast}(s)$$ therefore $\sqrt{h(s)}$ is admissible.

If $0\leq h(s) < 1$, then $\sqrt{h(s)} \geq h(s)$, and is not necessarily admissible (it may still happen to be, but there's no guarantee).

• Note that $\sqrt{x} \leq x$ iff $x \geq 1$. – Yuval Filmus Feb 23 '18 at 12:01
• @YuvalFilmus ... $\lor x=0$ :-P This corner case can be convenient since when we are working with $x\in\mathbb{N}$ then $\sqrt{x}\leq x$ becomes always true. – chi Feb 23 '18 at 15:18