1
$\begingroup$

In the textbook "Artificial Intelligence - A Modern Approach" (Russel, Norvig), it mentions that a sufficient criteria for the A* search algorithm to complete in polynomial time is for the heuristic estimate h(n) and actual cost h*(n) to never be different by more than O(log(h*(n)), i.e.:

|h(n) - h*(n)| <= O(log(h*(n)))

The textbook mentions this result without proof. I am looking for the proof. Does anyone know where I can find this result proven?


Edit: I discovered that the proof is most likely available in Judea Pearl's textbook "Heuristics: Intelligent Search Strategies for Computer Problem Solving" (http://www.amazon.com/exec/obidos/ASIN/0201055945/acmorg-20) (I should have guessed that this was by Pearl). It appears that the textbook is not available except through pay walls.

I do not want anyone to violate copyright laws and post the content, but if someone can validate that the proof is in this text, I will happily go out and buy the textbook (or get it from the university library).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.