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).


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.