Back

Explore Courses Blog Tutorials Interview Questions
0 votes
1 view
in AI and Deep Learning by (50.2k points)

Where can I find a proof for the following theorem:

Theorem: If h(n) is consistent, A* using GRAPH-SEARCH is optimal

Thanks.

1 Answer

0 votes
by (108k points)

First, we have to define these functions:

  • g(n) = it is the cost to reach node from start node
  • f(n) = g(n) + h(n)

Steps:

  1. Verify that the values of f(n) along any path are nondecreasing if h(n) is consistent.
  2. Confirm that whenever A* selects a node for expansion, the optimal path to that node has been found.
Welcome to Intellipaat Community. Get your technical queries answered by top developers!

28.4k questions

29.7k answers

500 comments

94.1k users

Browse Categories

...