All Questions
5 questions
3
votes
1
answer
224
views
Is there an error in A* optimality proof Russel-Norvig 4th edition?
In "AI: A Modern Approach", 4th edition, by Russell and Norvig, they give a purported proof that A* is cost-optimal for any admissible heuristic. The given proof seems most certainly wrong. ...
- 81
2
votes
1
answer
401
views
If $h_1(n)$ is admissible, why does A* tree search with $h_2(n) = 3h_1(n)$ return a path that is at most thrice as long as the optimal path?
Consider a heuristic function $h_2(n) = 3h_1(n)$. Where $h_1(n)$ is admissible.
Why are the following statements true?
$A^*$ tree search with $h_2(n)$ will return a path that is at most thrice as ...
- 21
2
votes
1
answer
4k
views
Understanding the proof that A* search is optimal
I don't understand the proof that $A^*$ is optimal.
The proof is by contradiction:
Assume $A^*$ returns $p$ but there exists a $p'$ that is cheaper. When $p$ is chosen from the frontier, assume $...
- 351
5
votes
1
answer
14k
views
How do I show that uniform-cost search is a special case of A*?
How do I show that uniform-cost search is a special case of A*? How do I prove this?
- 323
13
votes
1
answer
31k
views
Why is A* optimal if the heuristic function is admissible?
A heuristic is admissible if it never overestimates the true cost to reach the goal node from $n$. If a heuristic is consistent, then the heuristic value of $n$ is never greater than the cost of its ...
- 303