1
$\begingroup$

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?

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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)? $\endgroup$
    – nbro
    Nov 7 '20 at 14:41
  • $\begingroup$ See Lemma 1 in this paper: 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. $\endgroup$
    – Nathan S.
    Dec 9 '20 at 17:14

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.