How to avoid costly square root operations in A* algorithm?

Question

As a reminder, in an A* algorithm, vertices in the priority queue are sorted according to their priority $f = g + h$, where $g$ is the cost of getting to this vertex from the start vertex, and $h$ is an estimation on remaining cost to get from this vertex to the destination vertex. In my specific A* path finding algorithm, my estimation function has a square root operation. It isn't the standard $h = \sqrt{a^2 + b^2}$; for simplicity, let's say it's $h = \sqrt{d}$ where $d$ is some easily computable value. My problem is that my algorithm can take quite some time on some instances. Should I have a look at replacing my estimation function for a faster one, say without any square root operations?

I've looked around and some people simply ignore the square root (so $H = d$) which makes A* run faster but then it may overestimate, resulting in non-optimal solutions. I'd like to keep optimality, so next I was thinking about the priority function $F = f^2$ so as to accommodate for this overdominating $H = d$ (note that $F$ overestimates as well, but since the priority queue order for $f$ is the same as for $F$ optimality is preserved). However, since $f^2 = g^2 + 2gh + h^2 = g^2 + 2gh + H$, I would still need to compute $h = \sqrt{d}$. My first question is: could I use priority function $F_2 = g^2 + 2g + H$ instead? It's missing the $h$ from priority function $F$, could this create a problem, like $g$ being too dominant and the A* algorithm regressing too much to a Dijkstra algorithm?

Another idea I had was to construct an array during precomputation with the square root values of $d$ up to some upper bound on $d$, say $D$. I have such a bound, of about 500 say, so I could construct an array of values $1^2$, $2^2$, $3^2$, ..., $24^2= 576$. Then, when I need to compute a square root of $d$, for example $d=200$, a binary search in my array could give me highest value $\leq 200$, being $196$ at index 13, implying $h = 14$ with possibly some decimal notation which I don't care too much about. My second question is: would this method, of time complexity $\log(\sqrt{D})$, be faster than the standard (Java) square root?

Finally, more generally speaking, my third question is: how would one generally avoid such costly square root computations in A* algorithms?

Answer 1

Here’s a suggestion to verify that the square root is a problem: Measure how fast your code is. Replace sqrt(d) with sqrt(sqrt(d*d)). How much slower does your code get?

Answer 2

If you can use square root with limited precision, then you may try this approach:

1. use g^2 + 2gh + H formula, so you have exact value of H
2. compute leading zeroes in H so you can represent H=x*2^n
3. shift H so only 10 bits remain: H2 = H >> (n-10)
4. compute sqrtH2 = sqrt_table[H2]
5. now h = sqrtH2 * 32 * 2^(n/2)