0
$\begingroup$

The book "Artificial Intelligence: A Modern Approach" (4th edition, global version) says

"With an admissible heuristic, A* is cost-optimal...".

An admissible heuristic is one that never overestimates the distance to the goal, while a consistent heuristic is one that satisfies the triangle inequality, meaning that the cost of reaching the goal through a particular path is no more than the cost of reaching the goal through any other path. A* is cost-optimal in a tree search when using an admissible heuristic function, but it needs the heuristic function to be both admissible and consistent for optimal results in graph search.

I'm a bit confused by the AIMA statement. Are they saying that A* can be non-optimal if it uses an admissible but inconsistent heuristic with the graph search version?

Improve this question
$\endgroup$
6
  • $\begingroup$ Make sure my edits are consistent with your actual question. Please, can you also precede the paragraph that you're quoting with >. In that way, we know what was copied from the book. $\endgroup$
    – nbro
    Commented Jan 29, 2023 at 9:48
  • $\begingroup$ So, you didn't copy the part "An admissible heuristic is one that never overestimates the..." from the AIMA book? $\endgroup$
    – nbro
    Commented Jan 31, 2023 at 11:18
  • $\begingroup$ @nbro I. got it from my courses' slides, which are probably also based on the book. $\endgroup$
    – numq
    Commented Jan 31, 2023 at 22:33
  • 1
    $\begingroup$ Ok, so please edit your post to also precede that part with > because you copied then and so you should actually be quoting it and not pretend you wrote it. Thanks. $\endgroup$
    – nbro
    Commented Feb 1, 2023 at 8:37
  • $\begingroup$ @nbro should I put everything in quotes apart from the last paragraph? everything I learnt is from the book (4th or 3rd) in some way or another. $\endgroup$
    – numq
    Commented Feb 1, 2023 at 17:14

1 Answer 1

Reset to default
1
$\begingroup$

TL;DR: All A* requires to find the optimal path is an admissible heuristic

I'll read that section of the book for more clarity and extend this answer; though, I believe the way to interpret that statement is as follows:

Heuristics help reduce the number of computations required to reach the goal node. An admissible heuristic guarantees that the path we find is the optimal path but we might have made a few unnecessary computations along the way. An admissible and consistent heuristic helps to remove these unnecessary computations while finding the optimal path.

Further clarification:

"With an admissible heuristic, A* is cost-optimal...".

Means that the path you find using A* with an admissible heuristic is always the the optimal path. It does not mean that you'll find that path as fast as possible.

For some additional mathematical analysis on the proof of A* optimality you can read a proof I wrote here. I developed this proof because I found the proof in AIMA to be unsatisfactory.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ so why does the third edition say "the tree-search version of A∗ is optimal if h(n) is admissible, while the graph-search version is optimal if h(n) is consistent." $\endgroup$
    – numq
    Commented Feb 1, 2023 at 5:41
  • $\begingroup$ @numq I will investigate what they've written to see if there are some other mathematical points that they may not have expounded. $\endgroup$
    – respectful
    Commented Feb 1, 2023 at 16:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .