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

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

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

Where:

• g(n) = cost so far to reach node n (that is, current node)
• h(n) = estimated cost to reach from node n (current) to target node

The value of h(n) is called heuristics precisely because it is an intelligent estimate. First, it is an estimate because if I had the real value I would not have to search because I would have the answer. Moreover, to calculate the real value is, in fact, to make the search. So the best you can do is to estimate as best you can.

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 house is a node of the graph), the value of g(n) is simply the grid count of the home position of the grid character to the current house n (or a very high value if there is an obstacle there). A good heuristic h(n) is the distance, in units of the space of the world (assuming the grid is built on that same unit), between the current node n and the target node (where the target is). >

To say that a heuristic is admissible is to say that it does not overestimate the actual cost at all nodes of the graph . After all, it would be a huge problem if she overestimated (that is, errs for more than the real value), because the search could be diverted from an optimal 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 straight, he will walk 1 unit from space, but if he walk diagonally he will walk a little more than that (Pythagoras explains!). Therefore, using distance units is a close estimate of the real (that is, the number of houses that have to be walked), but will always go wrong.

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

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

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

On heuristics, 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 heuristics returning a constant value, but this will make the quick and powerful search of A* slow and weak.