# If $h_1(n)$ is admissible, why does A* tree search with $h_2(n) = 3h_1(n)$ return a path that is at most thrice as long as the optimal path?

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)$$
• 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.
– nbro
Feb 28, 2021 at 10:42

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