2
$\begingroup$

Consider a heuristic function $h_2(n) = 3h_1(n)$. Where $h_1(n)$ is admissible.

Why are the following statements true?

  1. $A^*$ tree search with $h_2(n)$ will return a path that is at most thrice as long as the optimal path.
  2. $h_2(n) + 1$ is guaranteed to be inadmissible for any $h_1(n)$
$\endgroup$
1
  • $\begingroup$ Hello. You can use latex/mathjax on this site, so please edit your post to format it properly with it. Moreover, this seems to be a homework problem. Is this true? If yes, tell us what have you tried so far. $\endgroup$
    – nbro
    Commented Feb 28, 2021 at 10:42

1 Answer 1

1
$\begingroup$

The sketch of the proof for your first question:

for an open node $n$, if $f_1(n) = g(n) + h_1(n)$, in the same situation in using $h_2$, it will be $f_2(n) = g(n) + 3 h_1(n)$. Hence, all the time for any node $n$, $f_2(n) \leqslant 3f_1(n)$. On the other hand, we know that A* with the admissible husritic function $h_1$ will be admissible (from Theorem 2 of Chapter 3 in "Heuristics Intelligent Search Strategies for Computer Problem Solving" book by Judera Pearl), i.e., for the node $n^*$ with optimal value, $f_1(n^*) \leqslant C^*$ that $C^*$ is the optimal value. Therefore, A* with $h_2$ will return a solution in node $n'$ by the cost of $f_2(n') \leqslant 3 f_1(n^*) \leqslant 3C^*$, as $f_1(n') \leqslant 3 f_1(n^*)$ (see more details of the proof in Theorem 13 of Chapter 13 in the same reference).

You can find more about $h_2$ under the title of $\epsilon$-admissibility as it is $(1 + \epsilon) h_1$ that $h_1$ is an admissible heuristic function. In your case, $\epsilon = 2$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .