A*算法最优性证明（反证法）

A*算法最优性证明（反证法）

1. 前提与定义

• g(n): 从初始节点到节点n的真实路径代价。
• h(n): 从节点n到目标节点的启发式估计代价。
• h*(n): 从节点n到目标节点的真实最小代价。
• f(n): 节点n的评估函数，f(n) = g(n) + h(n)。
• 核心前提 - 可采纳性 (Admissibility): 我们假设使用的启发式函数h(n)是可采纳的，即对于所有节点n，都满足：
  $$h(n) \le h^*(n)$$
  （即，估计值永远不会超过真实值，是一种“乐观”的估计）。
• C*: 从初始节点到目标节点的真实最优路径的代价。

2. 证明目标

证明：当启发式函数h(n)满足可采纳性时，A*算法找到的解一定是最优解。

3. 证明过程

我们使用反证法来证明。

第一步：做出假设

假设A*算法是次优的。即它终止时找到了一个从起点到终点G的次优路径 P_sub，其代价为 C_sub。同时，存在一条我们“错过”了的真实最优路径 P_opt，其代价为 C*，并且满足：
$$C_{sub} > C^*$$

第二步：分析算法终止时的状态

• 因为算法在路径 P_sub 上终止，这意味着终点G是从OPEN表中被选中并扩展的。此时，终点G的评价值为：
  $$f(G) = g_{sub}(G) + h(G)$$
• 其中，g_sub(G) 是次优路径 P_sub 的代价，即 C_sub。
• h(G) 是终点的启发式值，按定义h(G) = 0。
• 所以，我们得到：f(G) = C_sub。这说明算法是从OPEN表中选择了一个f值为C_sub的节点并结束。

第三步：分析被错过的最优路径

• 现在考虑真实的最优路径 P_opt。既然算法没有沿着这条路径走到终点，那么在算法终止的那一刻，这条最优路径上必定至少存在一个节点还留在OPEN表中。
• 我们把这条最优路径上，仍在OPEN表中的那个节点称为 n。

第四步：计算最优路径上节点n的评价值

• 根据评估函数定义：
  $$f(n) = g(n) + h(n)$$
• g(n) 是从起点沿最优路径 P_opt 到达节点 n 的真实代价。
• h(n) 是节点 n 的启发式估计。根据可采纳性这个核心前提，我们有 h(n) ≤ h*(n)。
• 因此，我们可以推导出：
  $$f(n) = g(n) + h(n) \le g(n) + h^*(n)$$
• 而 g(n) + h*(n) 正是从起点出发，经过节点n，再沿最优路径到达终点的总代价，这个值就是最优路径的真实代价 C*。
• 所以，我们得到了最关键的不等式：
  $$f(n) \le C^*$$

第五步：导出矛盾

我们来总结一下现在的情况：

1. 根据步骤二，算法选择终止，意味着它从OPEN表中取出的节点G的评价值为 f(G) = C_sub。
2. 根据步骤四，在同一时刻，OPEN表中其实还存在着另一个节点n，其评价值满足 f(n) ≤ C*。
3. 根据我们的初始假设，C* < C_sub。

将这三点结合起来，我们得到：
$$f(n) \le C^* < C_{sub} = f(G)$$
$$ \implies f(n) < f(G)$$

这就产生了矛盾。A*算法的设计原理是永远从OPEN表中选择f值最小的节点进行扩展。既然OPEN表中存在一个f值更小的节点n，算法绝对不可能去选择那个f值更大的终点G。因此，我们的初始假设（“A*算法会找到次优解”）不成立。

4. 最终结论

假设不成立，故当启发式函数h(n)可采纳时，A*算法保证能找到最优解。