Answers.Body: <blockquote>
  <p>Given a non-admissible heuristic function, A* will always give a solution if one exists, but there is no guarantee it will be optimal.</p>
  </blockquote>
  <p>I won't duplicate the proof here, but it isn't too hard to prove that any best-first search will find a solution for any measure of best, given that a path to the solution exists and infinite memory. A* is a best-first search algorithm, so it will always find a solution if one exists.</p>
  <blockquote>
  <p>Which heuristics guarantee the optimality of A*? Is the admissibility of the heuristic always a necessary condition for A* to produce an optimal solution?</p>
  </blockquote>
  <p>Admissibility is not a necessary condition. Take any admissible heuristic <span class="math-container">$h_1$</span> and make a new function <span class="math-container">$h(n) = h_1(n)+5$</span>. This heuristic is not admissible, but if you run A* on it, it will still find optimal solutions.</p>
  <p>But, we also have to ask what you mean by &quot;the optimality of A*&quot;, because optimality can have two senses here. My point in the previous paragraph is in the sense of returning optimal paths. An alternate interpretation is that no algorithm performs fewer expansions that A* with the same information. This is probably not what was meant, and the answer in that context is far more complicated. But, with an inconsistent (but admissible) heuristic, A* can perform exponentially more expansions than other known algorithms, and thus is not the optimal algorithm to use.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-07T14:41:07.610Z
Answers.Text: I am not sure what you mean here by "for any measure of best". Moreover, you say "I won't duplicate the proof here": can you please at least cite a resource that shows that any best-first algorithm finds the _optimal_ solution (even if the heuristic is not admissible)?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-09T17:14:02.470Z
Answers.Text: See Lemma 1 in this paper: https://webdocs.cs.ualberta.ca/~nathanst/papers/chen2019conditions.pdf Note that I didn't claim that the optimal solution is found in this case, only that a solution will be found.
Answers.UserDisplayName: Nathan S.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-02T05:32:45.687Z
Answers.LastActivityDate: 2020-11-07T14:40:05.440Z
Answers.LastEditDate: 2020-11-07T14:40:05.440Z
Answers.UserDisplayName: Nathan S.
Body: <p>The following is a statement and I am trying to figure out if it's true or false and why.</p>
  <blockquote>
  <p>Given a non-admissible heuristic function, A* will always give a solution if one exists, but there is no guarantee it will be optimal.</p>
  </blockquote>
  <p>I know that a non-admissible function is <span class="math-container">$h(n) &gt; h^*(n)$</span> (where <span class="math-container">$h^*(n)$</span> is the real cost to the goal), but I do not know if there is a guarantee.</p>
  <p>Which heuristics guarantee the optimality of A*? Is the admissibility of the heuristic always a necessary condition for A* to produce an optimal solution?</p>
  
Tags: <search><heuristics><a-star><admissible-heuristic>
Title: Which heuristics guarantee the optimality of A*?
UserDisplayName: ndrb
ThreadText: # Which heuristics guarantee the optimality of A*?
  
  (Asked by: username_0 on 2020-06-24)
  
  The following is a statement and I am trying to figure out if it's true or false and why.
  
  > Given a non-admissible heuristic function, A\* will always give a solution if one exists, but there is no guarantee it will be optimal.
  
  I know that a non-admissible function is $h(n) > h^\*(n)$ (where $h^\*(n)$ is the real cost to the goal), but I do not know if there is a guarantee.
  
  Which heuristics guarantee the optimality of A\*? Is the admissibility of the heuristic always a necessary condition for A\* to produce an optimal solution?
  
  **Tags:** search, heuristics, a-star, admissible-heuristic
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-07-02. Score: 0 | Accepted answer
  
  > Given a non-admissible heuristic function, A\* will always give a solution if one exists, but there is no guarantee it will be optimal.
  
  I won't duplicate the proof here, but it isn't too hard to prove that any best-first search will find a solution for any measure of best, given that a path to the solution exists and infinite memory. A\* is a best-first search algorithm, so it will always find a solution if one exists.
  
  > Which heuristics guarantee the optimality of A\*? Is the admissibility of the heuristic always a necessary condition for A\* to produce an optimal solution?
  
  Admissibility is not a necessary condition. Take any admissible heuristic $h\_1$ and make a new function $h(n) = h\_1(n)+5$. This heuristic is not admissible, but if you run A\* on it, it will still find optimal solutions.
  
  But, we also have to ask what you mean by "the optimality of A\*", because optimality can have two senses here. My point in the previous paragraph is in the sense of returning optimal paths. An alternate interpretation is that no algorithm performs fewer expansions that A\* with the same information. This is probably not what was meant, and the answer in that context is far more complicated. But, with an inconsistent (but admissible) heuristic, A\* can perform exponentially more expansions than other known algorithms, and thus is not the optimal algorithm to use.
  
  > **Comments:**
  > **username_2**: I am not sure what you mean here by "for any measure of best". Moreover, you say "I won't duplicate the proof here": can you please at least cite a resource that shows that any best-first algorithm finds the _optimal_ solution (even if the heuristic is not admissible)?  
  > **username_1**: See Lemma 1 in this paper: https://webdocs.cs.ualberta.ca/~nathanst/papers/chen2019conditions.pdf Note that I didn't claim that the optimal solution is found in this case, only that a solution will be found.  
  
  ---
  
  