patternModerate
Is using a more informed heuristic guaranteed to expand fewer nodes of the search space?
Viewed 0 times
expandnodestheinformedspacesearchmoreheuristicusingguaranteed
Problem
I'm reading through the RMIT course notes on state space search.
Consider a state space $S$, a set of nodes in which we look for an element having a certain property.
A heuristic function $h:S\to\mathbb{R}$ measures how promising a node is.
$h_2$ is said to dominate (or to be more informed than) $h_1$ if $h_2(n) \ge h_1(n)$ for every node $n$. How does this definition imply that using $h_2$ will lead to expanding fewer nodes? - not only fewer but subset of the others.
In Luger '02 I found the explanation:
This can be verified by assuming the opposite (that there is at least one state expanded by $h_2$ and not by $h_1$). But since $h_2$ is more informed than $h_1$, for all $n$, $h_2(n) \le h_1(n)$, and both are bounded above by $h^*$, our assumption is contradictory.
But I didn't quite get it.
Consider a state space $S$, a set of nodes in which we look for an element having a certain property.
A heuristic function $h:S\to\mathbb{R}$ measures how promising a node is.
$h_2$ is said to dominate (or to be more informed than) $h_1$ if $h_2(n) \ge h_1(n)$ for every node $n$. How does this definition imply that using $h_2$ will lead to expanding fewer nodes? - not only fewer but subset of the others.
In Luger '02 I found the explanation:
This can be verified by assuming the opposite (that there is at least one state expanded by $h_2$ and not by $h_1$). But since $h_2$ is more informed than $h_1$, for all $n$, $h_2(n) \le h_1(n)$, and both are bounded above by $h^*$, our assumption is contradictory.
But I didn't quite get it.
Solution
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) 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.
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) 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.
Context
StackExchange Computer Science Q#1579, answer score: 11
Revisions (0)
No revisions yet.