0
$\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 nonadmissible function is $h(n) > \text{real cost}(n)$, 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
$\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 h1 and make a new function h(n) = h1(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.

| improve this answer | |
$\endgroup$

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.