If $h_1(s)$ is a consistent heuristic and $h_2(s)$ is a admissible heuristic, is $\min(h_1(s),\ h_2(s))$ consistent?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You can easily find a counterexample. Suppose that there are three nodes $s$, $p$, and $goal$ such that $s \rightarrow p \rightarrow goal$. The real cost of going from $s$ to $p$ is $c(s,p) = 10$ and $c(p, goal) = 10$. Also, $h_1(s) = 18$, $h_1(p) = 9$, $h_1(goal) = 0$, $h_2(s) = 17$, $h_2(p) = 1$.On the other hand, $h^*(s) = 19$ and $h^*(p) = 10$.
Now, $h_1(s) \leqslant c(s,p) + h_1(p)$ and $h_1(s) \leqslant c(s, goal) + h_1(goal)$ that satisfies the consistency constraint of $h_1$. Also, $h_2(s) \leqslant h^*(s)$ and $h_2(s) \leqslant h^*(p)$ that approve $h_2$ is admissible.
However, for any node $n$, if we define $h_3(n) = \min(h_1(n), h_2(n))$:
$$h_3(s) = \min(h_1(s), h_2(s)) = 17 \not\leqslant c(s,p) + \min(h_1(p), h_2(p)) = $$ $$c(s,p) + h_3(p) = 10 + 1 = 11. $$ It means that $h_3$ as a heuristic function is not consistent.
