A *最优，具有一致的启发式

Question

在哪里可以找到以下定理的证明：

定理：如果h（n）是一致的，则使用GRAPH-SEARCH的A *是最优的

谢谢。

Answer 1

您可以在第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'）