Why is it the lower the h(n) cost the more nodes need to be expanded in A*?

As found here - http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

If h(n) is always lower than (or equal to) the cost of moving from n to the goal, then A* is guaranteed to find a shortest path. The lower h(n) is, the more node A* expands, making it slower.

  • $\begingroup$ What have you tried? Have you tried a few examples? We expect you to make a serious effort to figure it out on your own before asking here, and to show us in the question what you've tried -- that generally makes a much better question that will help you get more specific answers. $\endgroup$ – D.W. Jan 5 '15 at 23:30

A* expands the search tree by expanding the node for which the past cost ($d(n)$; cost of path from the start point to the node) plus the heuristic value ($h(n)$) is minimum. Because the heuristic $h(n)$ is admissible, $d(n)+h(n)$ is a lower bound on the cost of the path to the goal that may be obtained by expanding the node $n$.

If we have found a path of cost $L$, we can (only) conclude that path is shortest when there are no more nodes for which $d(n)+h(n)<L$. If there were such nodes then expanding them could possibly give a path of cost $<L$.

Assume the shortest path has cost $L$. Consider the graph, but restricted to the nodes for which $d(n)+h(n)<L$. Then the nodes that A* expands are exactly the nodes in the connected component of the start point in this restricted graph.

If we have an alternative heuristic function $h'(n)$ such that for all nodes $n$, $h'(n)\leq h(n)$ then clearly the size of the connected component containing the start point in the graph restricted to nodes where $d(n)+h'(n)<L$ is greater (or equal to) the size of the same connected component in the graph restricted to nodes where $d(n)+h(n)<L$ because $d(n)+h'(n)\leq d(n)+h(n)$ for all nodes $n$.

This analysis assumes that there are no other nodes (other than the goal node) for which $d(n)+h(n)=L$, if not this is the case then how many nodes are expanded depends on the tie-breaking order (and we can not say anything useful about that).


Im not completely sure about the hints im giving but i think it makes sense.
Since $h(n)$ is the estimation of min distance (cost) from current node to the goal node so the lower it is the lower effect it has on $f(n)$ which $f(n)=g(n)+h(n)$ so $f(n)$ will rely more on $g(n)$.
As you know if $h(n)=0$ then $A^*$ will change to Dijkstra's algorithm which checks all nodes. So if $h(n)$ is so small and close to zero it will act like Dijkstra's.


Your Answer

