Intellipaat Back

Explore Courses Blog Tutorials Interview Questions
0 votes
2 views
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 (107k 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.

31k questions

32.8k answers

501 comments

693 users

Browse Categories

...