I am trying to solve a maze puzzle using the A* algorithm. I am trying to analyze the algorithm based on different applicable heuristic functions.
Currently, I explored the Manhattan and Euclidean distances. Which other heuristic functions are available? How do we compare them? How do we know whether a heuristic function is better than another?
In the A* algorithm, at each iteration, a node is chosen which minimizes a certain function, called the evaluation function, which, in the case of A*, is defined as
$$f(n)=g(n)+h(n)$$
where $g(n)$ is the length (or cost) of the cheapest path from the start node to the current node $n$ and $h(n)$ is the heuristic function that estimates the cost of the cheapest path from current node $n$ to goal node.
There is potentially more than one path to the goal from a given node $n$. However, one of these paths is the cheapest path. An admissible heuristic function is a heuristic function that does not overestimate the cost to reach the goal node, that is, it estimates a cost to reach a goal that is smaller or equal to the cheapest path from $n$, which is denoted by $h^*(n)$. Therefore, an admissible heuristic $h$ satisfies $h(n) \leq h^*(n), \forall n$. Given that the goal is to find the cheapest path from a start to a goal node, intuitively, an admissible heuristic is an optimistic predictive function.
A* is guaranteed to find the optimal solution (or path) if it uses an admissible heuristic. In section 2.4 of the book Principles of Artificial Intelligence (1982), Nils J. Nilsson provides the proof of this fact.
However, not all admissible heuristics give the same information, so not all admissible heuristics are equally efficient. For instance, a heuristic function that is trivially admissible is $h(n) = 0, \forall n$. However, in this case, the only actual information that is used to choose the next node to expand is only based on $g(n)$, that is, $f(n) = g(n)$. This evaluation function corresponds to the evaluation function of the uniform-cost search algorithm, which is an uninformed-search algorithm (as opposed to A*, which, nonetheless, is considered an informed-search algorithm).
Which admissible heuristic is thus more informed? Consider two versions of A*, each with a different admissible heuristic function
$$ f_1(n) = g_1(n) + h_1(n) $$
and
$$ f_2(n) = g_1(n) + h_2(n) $$
where $h_1(n) \leq h^*(n), \forall n$ and $h_2(n) \leq h^*(n), \forall n$. Then A* with the evaluation function $f_1$ is more informed than A* with $f_2$ if, for all non-goal nodes $n$, $h_1(n) > h_2(n)$. See section 2.4.4. of the cited book where an example that attempts to show this is given.
The admissibility of a heuristic depends on the problem. For example, in the case of the Fifteen Puzzle problem, both Manhattan and the Hamming distances are admissible heuristics. However, in other problems, these distances might not induce an admissible heuristic.
