Return to Question

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?

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.

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.

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?

EDIT:

In Luger '02 I found the explanation:

This can be verified by assuming the opposite (that there is at least one state expanded by h2 and not by h,). But since h2 is more informed than h1, for all n, h2(n) $\le$ h1(n), and both are bounded above by h*, our assumption is contradictory.

But I didn't quite get it.

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?

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.