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

  • 1
    $\begingroup$ Note that $\sqrt{x} \leq x$ iff $x \geq 1$. $\endgroup$ – Yuval Filmus Feb 23 '18 at 12:01
  • 1
    $\begingroup$ @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. $\endgroup$ – chi Feb 23 '18 at 15:18

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.