Is using a more informed heuristic guaranteed to expand fewer nodes of the search space?
So it seems you are intrigued about the relationship between the informedness of a heuristic function and its pruning power. 

This is a well-known relationship established in the literature from the 80s (see for example Pearl, Judea. Heuristics, Addison-Wesley, 1984 who, by the way, has been awarded this year with the Alan Turing award). 

As you already mentioned, $h_1$ is said to be more informed than $h_2$ if and only if $h_1(n)\geq h_2(n), \forall n$ in the state space. Now, provided that the heuristic function is also admissible (i.e., $h_1(n)\leq h^*(n)$ so that it never overestimates the effort to reach the goal, where $h^*(n)$ is the optimal cost to reach the goal state from node $n$), $h_2(n)$ is admissible as well since $h^* (n) \geq h_1 (n)$ by definition and $h_1(n)\geq h_2(n)$ by hipothesis, so that $h^* (n) \geq h_2 (n)$.

When considering that both heuristics are admissible, the following result applies to all $A^*$-like search algorithms: $f (n)&lt;h^*(n)$ is a sufficient condition for expansion so that they expand all nodes meeting this property ---other algorithms expanding them as well include IDA$^*$ and RBFS. Since $f (n) = g(n) + h (n)$ where $g(n)$ is the (known) cost from the start state $s$ to node $n$ and $h(n)$ is your heuristic function (either $h_1$ or $h_2$) so that $f(n)$ is the estimated cost of the path $s-t$ when going through $n$, it immediately follows that there are, at least, as many nodes meeting this propertiy when $h_2$ is used instead of $h_1$.

The property mentioned above was already demonstrated in the original paper of the A$^*$ search algorithm and it is quite simple. In response to your comment, I posted a proof at the end of this message.

Hope this helps, this is my first post in this site,



Theorem: $f(n) &lt; h^*(n)$ is a sufficient condition for expansion of node $n$ in A$^*$-like search algorithms provided that $h(n)$ is an admissible heuristic function.

Proof: I will proof this by induction on the number of steps of the A$^*$ search algorithm. Since the proof relies on the monotonicity of $f(n)$ I will first prove it.

$f(n) = g(n) + h(n)$ is a monotonically increasing function (when solving minimization problems). Recall the definitions of $g(n)$ and $h(n)$ provided above. 

If $h(n)$ is a consistent heuristic function (i.e., a heuristic function is said to be consistent if it satisfies the triangular inequality $|h(n) - h(m)| \leq c(n,m)$ where $c(n,m)$ is the cost of the operator from $n$ to $m$), then the $f$-value of a node $m$ which is a descendant of node $n$ lies in the interval $[g(n)+c(n,m)+h(n)-c(n,m), g(n)+c(n,m)+h(n)+c(n,m)]=[g(n)+h(n), g(n)+h(n)+2c(n,m)]\geq g(n)+h(n) = f(n)$. 

Incidentally, the wikipedia says: "If $h(n)$ is consistent then the value of $h(n)$ for each node along a path to goal node are non decreasing" but this is not strictly speaking true, this is just a result of the original definition provided above.

If $h(n)$ is an $inconsistent$ heuristic function (so that it that does not satisfy the aforementioned property) then $f(m)$ can be arbitrarily smaller than $f(n)$. However, since $h(n)$ is an admissible heuristic function, $max\{h(n)-c(n,m), h(m)\}$ is an admissible heuristic function for node $m$ and using it the same interval results.

Now, bearing in mind that $f(n)$ increases along a path to the goal and that $h(n)$ never overestimates the effort to reach the goal state, it is straightforward to prove the theorem by induction

Base case: the start node $s$ is introduced in the OPEN list and it is selected for expansion. Since $f(s)=g(s)+h(s)=h(s) \leq h^*(s)$ (by hypothesis of the admissibility of $h(\cdotp)$) the theorem has been proved for the base case.

Induction step: at each iteration of the A$^*$ search algorithm the first node $n$ in OPEN is selected for expansion. By induction, it is assumed that $f(n) \leq h^*(n)$. If $n = t$ (the target state), the search immediately terminates and $f(n)=g(n)+h(n)=g(n)$ is the optimal cost of the path $s-t$. Otherwise, the descendants of node $n: n_1, n_2, ... n_k$ are inserted into the OPEN list in increasing order of $f(\cdotp)$. I will now proof that the expansion of $n$ leaves the OPEN list in such a state that the first node $m$ has $f(m) \leq h^*(m)$, because it will be expanded in the next iteration this would proof the theorem by induction. Two cases might arise:

Case 1: one of the descendants of node $n, n_i$ has an $f$-value $f(n_i) = f(n)$ (recall that $f(n)$ is a monotonically increasing function). In this case, it would be ranked first (maybe along with other nodes in case of a tie), since it has the same $f$-value of its ancestor which was already first in the OPEN list.

Case 2: all the descendants of node $n, n_i, \forall i=1, \ldots k$ have $f(n_i) &gt; f(n)$. In this case, these nodes would be arranged in OPEN after the second state in OPEN when $n$ was selected for expansion. Since $f(n_i)\leq h^* (n_i)$, but they are larger than the second best node in OPEN, node $m$ has to verify that $f(m) \leq h^*(m)$ and this concludes the proof.