Answers.Body: <p>The sketch of the proof for your first question:</p>
  <p>for an open node <span class="math-container">$n$</span>, if <span class="math-container">$f_1(n) = g(n) + h_1(n)$</span>, in the same situation in using <span class="math-container">$h_2$</span>, it will be <span class="math-container">$f_2(n) = g(n) + 3  h_1(n)$</span>. Hence, all the time for any node <span class="math-container">$n$</span>, <span class="math-container">$f_2(n) \leqslant 3f_1(n)$</span>. On the other hand, we know that A* with the admissible husritic function <span class="math-container">$h_1$</span> will be admissible (from Theorem 2 of Chapter 3 in <a href="https://mat.uab.cat/%7Ealseda/MasterOpt/Judea_Pearl-Heuristics_Intelligent_Search_Strategies_for_Computer_Problem_Solving.pdf" rel="nofollow noreferrer">&quot;Heuristics Intelligent Search Strategies for Computer Problem Solving&quot; book by Judera Pearl</a>), i.e., for the node <span class="math-container">$n^*$</span> with optimal value, <span class="math-container">$f_1(n^*) \leqslant C^*$</span> that <span class="math-container">$C^*$</span> is the optimal value. Therefore, A* with <span class="math-container">$h_2$</span> will return a solution in node <span class="math-container">$n'$</span> by the cost of <span class="math-container">$f_2(n') \leqslant 3 f_1(n^*) \leqslant 3C^*$</span>, as <span class="math-container">$f_1(n') \leqslant 3 f_1(n^*)$</span> (see more details of the proof in Theorem 13 of Chapter 13 in the same reference).</p>
  <p>You can find more about <span class="math-container">$h_2$</span> under the title of <span class="math-container">$\epsilon$</span>-admissibility as it is <span class="math-container">$(1 + \epsilon) h_1$</span> that <span class="math-container">$h_1$</span> is an admissible heuristic function. In your case, <span class="math-container">$\epsilon = 2$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-28T16:25:06.853Z
Answers.LastActivityDate: 2021-03-06T14:25:53.197Z
Answers.LastEditDate: 2021-03-06T14:25:53.197Z
Answers.UserDisplayName: OmG
Body: <p>Consider a heuristic function <span class="math-container">$h_2(n) = 3h_1(n)$</span>. Where <span class="math-container">$h_1(n)$</span> is admissible.</p>
  <p>Why are the following statements true?</p>
  <ol>
  <li><span class="math-container">$A^*$</span> tree search with <span class="math-container">$h_2(n)$</span> will return a path that is at most thrice as long as the optimal path.</li>
  <li><span class="math-container">$h_2(n)  + 1$</span> is guaranteed to be inadmissible for any <span class="math-container">$h_1(n)$</span></li>
  </ol>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-02-28T10:42:10.070Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Tags: <proofs><a-star><admissible-heuristic><tree-search><heuristic-functions>
Title: 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?
UserDisplayName: Jia Rong
ThreadText: # 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?
  
  (Asked by: username_0 on 2021-02-28)
  
  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)$
  
  **Tags:** proofs, a-star, admissible-heuristic, tree-search, heuristic-functions
  > **Comments:**
  > **username_1**: 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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-02-28. Score: 1
  
  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](https://mat.uab.cat/%7Ealseda/MasterOpt/Judea_Pearl-Heuristics_Intelligent_Search_Strategies_for_Computer_Problem_Solving.pdf)), 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$.
  
  
  ---
  
  