heuristica h(n)=0 is permissible for algorithm A*

Question

Hello folks someone can answer this question I’m in doubt.

heuristic h(n)=0 is permissible for algorithm A*

Answer 1

If you remember the basic principle of algorithm A*, it decides the next node of a graph to "pursue" based on an evaluation function f(n) given by:

f(n) = g(n) + h(n)

Where:

• g(n) = cost up to the moment to reach the node n (that is, the current knot)
• h(n) = estimated cost to reach from node n (current) up to the objective node

The value of h(n) is called heuristics precisely because it is an intelligent estimate. First of all, it’s an estimate because if I had the real value I wouldn’t have to do the search because I already had the answer. Moreover, calculating the real value is, in fact, doing the search. So, the best thing to do is to estimate the best way possible.

These estimates are usually simple and easy to calculate, and that’s what makes this algorithm so interesting. In a game, for example, where a character needs to locate a target under a discrete grid (where each grid box is a graph node), the value of g(n) is simply the count of houses from the grid from the character’s initial position to the current house n (or a very high value if there is an obstacle). A good heuristic h(n) is the distance, in units of world space (assuming the grid is built on that same unit), between the current node n and the destination node (where the target is).

To say that a heuristic is admissible is to say that it does not overestimate the real cost at all nodes of the graph. After all, it would be a huge problem if it overestimated (that is, it was wrong for more than the real value), because the search could be diverted from a great path. In the previous example, the grid is discreet, so the character will always have to walk from one house to another. If he walks in a straight line, he will walk 1 unit of space, but if he walks diagonally will walk a little more than that (Pythagoras explains!). Therefore, using distance units is an estimate close to the real (that is, the number of houses that are missing to be walked), but will always go wrong down.

Thus, in a correct implementation of A* to heuristics h(n) should only be equal to 0 at the objective node. If it is 0 always, that is, for all nodes n, will be the same as not using any heuristic and make your evaluation function be:

f(n) = g(n) + h(n) = g(n) + 0 = g(n)

Works? Yes, but then the search is only based on cost, without using any path estimate (which is the big difference of A*, allowing you to find an optimal result if it exists). In fact, the algorithm that is based only on cost exists, and is called Search for Uniform Cost.

Answer 2

On the heuristic, if you put h(n) = 0, this implies that there will be no guided search. Without heuristics, there are no search optimizations.

So yes, it is plausible that you put the heuristic returning a constant value, but this will make the fast and powerful search of A* become slow and weak.