Answers.Body: <p>It depends on what you mean by optimal.</p>
  <ol>
  <li><p>A* will always find the optimal solution (that is, the algorithm is <em>admissible</em>) as long as the heuristic is admissible. (Note that the definition of admissible is overloaded and means something slightly different for an algorithm and a heuristic.)</p>
  </li>
  <li><p>If you talk about the <em>set</em> of nodes expanded by A*, then it expands the minimal <em>set</em> of nodes up to tie-breaking even with an inconsistent heuristic.</p>
  </li>
  <li><p>If you talk about the number of <em>expansions</em>, then A* is not optimal. A* can perform up to <span class="math-container">$2^N$</span> expansions of <span class="math-container">$N$</span> states with an inconsistent heuristic. This result comes from <a href="https://www.sciencedirect.com/science/article/abs/pii/0004370277900029" rel="nofollow noreferrer">Martelli, 1977</a>.</p>
  </li>
  <li><p>Algorithm B has worst-case <span class="math-container">$N^2$</span> expansions and <a href="https://webdocs.cs.ualberta.ca/%7Enathanst/papers/IBEX.pdf" rel="nofollow noreferrer">budgeted graph search (BGS)</a> has worst-case <span class="math-container">$N \log C$</span>, where <span class="math-container">$C$</span> is the optimal solution cost.</p>
  </li>
  </ol>
  <p>You can see a demo that shows the worst-case performance of A* as well as the performance of BGS here:</p>
  <p><a href="https://www.movingai.com/SAS/INC/" rel="nofollow noreferrer">https://www.movingai.com/SAS/INC/</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-20T23:03:07.703Z
Answers.LastActivityDate: 2020-11-08T16:43:15.040Z
Answers.LastEditDate: 2020-11-08T16:43:15.040Z
Answers.UserDisplayName: Nathan S.
Body: <p>I understand that, in tree search, an admissible heuristic implies that <span class="math-container">$A*$</span> is optimal. The intuitive way I think about this is as follows:</p>
  <p>Let <span class="math-container">$P$</span> and <span class="math-container">$Q$</span> be two costs from any respective nodes <span class="math-container">$p$</span> and <span class="math-container">$q$</span> to the goal. Assume <span class="math-container">$P&lt;Q$</span>. Let <span class="math-container">$P'$</span> be an estimation of <span class="math-container">$P$</span>. <span class="math-container">$P'\le P \Rightarrow P'&lt;Q$</span>. It follows from uniform-cost-search that the path through <span class="math-container">$p$</span> must be explored.</p>
  <p>What I don't understand, is why the idea of an admissible heuristic does not apply as well to &quot;graph-search&quot;. If a heuristic is admissible but inconsistent, would that imply that <span class="math-container">$A*$</span> is not optimal? Could you please provide an example of an admissible heuristic that results in a non-optimal solution?</p>
  
Tags: <search><heuristics><a-star><admissible-heuristic><consistent-heuristic>
Title: Is A* with an admissible but inconsistent heuristic optimal?
UserDisplayName: Harry Stuart
ThreadText: # Is A* with an admissible but inconsistent heuristic optimal?
  
  (Asked by: username_0 on 2020-07-18)
  
  I understand that, in tree search, an admissible heuristic implies that $A\*$ is optimal. The intuitive way I think about this is as follows:
  
  Let $P$ and $Q$ be two costs from any respective nodes $p$ and $q$ to the goal. Assume $P. Let $P'$ be an estimation of $P$. $P'\le P \Rightarrow P'. It follows from uniform-cost-search that the path through $p$ must be explored.
  
  What I don't understand, is why the idea of an admissible heuristic does not apply as well to "graph-search". If a heuristic is admissible but inconsistent, would that imply that $A\*$ is not optimal? Could you please provide an example of an admissible heuristic that results in a non-optimal solution?
  
  **Tags:** search, heuristics, a-star, admissible-heuristic, consistent-heuristic
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-07-20. Score: 2
  
  It depends on what you mean by optimal.
  
  1. A\* will always find the optimal solution (that is, the algorithm is *admissible*) as long as the heuristic is admissible. (Note that the definition of admissible is overloaded and means something slightly different for an algorithm and a heuristic.)
  2. If you talk about the *set* of nodes expanded by A\*, then it expands the minimal *set* of nodes up to tie-breaking even with an inconsistent heuristic.
  3. If you talk about the number of *expansions*, then A\* is not optimal. A\* can perform up to $2^N$ expansions of $N$ states with an inconsistent heuristic. This result comes from [Martelli, 1977](https://www.sciencedirect.com/science/article/abs/pii/0004370277900029).
  4. Algorithm B has worst-case $N^2$ expansions and [budgeted graph search (BGS)](https://webdocs.cs.ualberta.ca/%7Enathanst/papers/IBEX.pdf) has worst-case $N \log C$, where $C$ is the optimal solution cost.
  
  You can see a demo that shows the worst-case performance of A\* as well as the performance of BGS here:
  
  <https://www.movingai.com/SAS/INC/>
  
  
  ---
  
  