我在哪里可以找到以下定理的证明：
定理：如果h(n)是一致的，那么使用GRAPH-SEARCH的A*算法是最优的。
谢谢。
A*算法的最优性及一致启发式函数
4
- Jack
1
看起来这是一个问题，需要在http://cstheory.stackexchange.com/上提问。 - Volker Stolz
2个回答
5
您可以在第95-97页的这本书中找到相关内容：
http://www.amazon.com/Artificial-Intelligence-Modern-Approach-3rd/dp/0136042597/ref=sr_1_1?ie=UTF8&s=books&qid=1295781411&sr=8-1
证明的基本框架如下：
首先我们定义以下函数：
g(n) = 从起点到达节点的成本
f(n) = g(n) + h(n)
步骤：
1. 如果h(n)是一致的，则建立沿任何路径的f(n)值都是非递减的。 2. 证明只要A*选择扩展一个节点，就已经找到了该节点的最优路径。
第1步直接遵循一致性的定义。
第2步是通过看到，如果不是真实的，则必须在起点到n的最优路径上有另一个边界节点n'，但这是不可能的，因为路径是非递减的，因此该节点将具有比n更低的f成本。即f(n) = g(n) + h(n) > f(n') = g(n') + h(n')
首先我们定义以下函数：
g(n) = 从起点到达节点的成本
f(n) = g(n) + h(n)
步骤：
1. 如果h(n)是一致的，则建立沿任何路径的f(n)值都是非递减的。 2. 证明只要A*选择扩展一个节点，就已经找到了该节点的最优路径。
第1步直接遵循一致性的定义。
第2步是通过看到，如果不是真实的，则必须在起点到n的最优路径上有另一个边界节点n'，但这是不可能的，因为路径是非递减的，因此该节点将具有比n更低的f成本。即f(n) = g(n) + h(n) > f(n') = g(n') + h(n')
- bassen
0
阅读此页面
证明的两个步骤：
1- Establish that the values of f(n) along any path are nondecreasing, if h(n) is consistent.
2- Prove that whenever A* selects a node for expansion, the optimal path to that node has been found.
- Mohammad Mahdi KouchakYazdi
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接