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)$
  • $\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
    Feb 28 '21 at 10:42

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.