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).

| cite | improve this answer | |

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.