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$ it doesn't matter). 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 bound on $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{500})$, 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?