动态规划的核心性质——最优化原理 (Principle of Optimality)
好的，我们来详细解释一下动态规划的另一个核心性质——最优化原理 (Principle of Optimality)。
这个原理是动态规划算法能够成立的基石，它与我们之前讨论的“无后效性”密切相关。
1. 什么是“最优化原理”？
最优化原理最早由动态规划的提出者、美国数学家理查德·贝尔曼 (Richard Bellman) 提出。其经典描述是：
“一个最优策略的子策略，对于它所对应的子问题来说，也必须是最优的。”
(An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.)
这句话听起来有点绕，我们把它拆解成更通俗的语言：
- 如果一个大问题的最优解包含了一个小问题的解，那么这个小问题的解也必须是它本身的最优解。
- 换句话说，最优解的组成部分也必须是局部的最优解。
2. 一个直观的类比：最短路径
假设你要开车从北京到广州，并且找到了最短的一条路线。这条路线恰好经过了武汉。
北京 → … → 武汉 → … → 广州 (这是全程的最短路线)
那么，最优化原理告诉我们：
- 从北京到武汉的这段路，必然是所有从北京到武汉的路线中最短的。
- 从武汉到广州的这段路，也必然是所有从武汉到广州的路线中最短的。
为什么？
我们可以用反证法来思考：假设从北京到武汉的这段路不是最短的，那么肯定存在另一条更短的路从北京到武汉。如果我们用这条更短的路替换掉原来路线中的北京-武汉部分，那么全程的总路程就会变得更短。这就与我们“已经找到了全程最短路线”的前提相矛盾了。
因此，一个全局最优解，其内部的每一个子决策序列，相对于其起点和终点，也必须是局部最优的。这就是最优化原理。
3. 在动态规划问题中的体现
动态规划通过状态转移方程来求解问题。这个方程的设计本身就蕴含了最优化原理。
我们以经典的0-1背包问题为例：
-
问题：有一组物品，每个物品有自己的重量和价值。给定一个固定容量的背包，如何选择物品，使得装入背包的物品总价值最高？
-
状态定义：
dp[i][w]表示在前i个物品中，选择若干个放入容量为w的背包中所能获得的最大价值。 -
决策：对于第
i个物品，我们只有两种选择：- 不放入背包：那么
dp[i][w]的值就等于只考虑前i-1个物品在容量w下的最大价值，即dp[i-1][w]。 - 放入背包：前提是背包能装得下。此时的价值等于第
i个物品的价值，加上“在前i-1个物品中，选择若干个放入容量为w - weight[i]的背包中所能获得的最大价值”。这个子问题的解就是dp[i-1][w - weight[i]]。
- 不放入背包：那么
-
状态转移方程：
dp[i][w] = max( dp[i-1][w], value[i] + dp[i-1][w - weight[i]] ) -
最优化原理的体现：
这个方程明确地告诉我们：要求解“前i个物品，容量w”这个大问题的最优解，我们依赖于两个子问题的最优解：- “前
i-1个物品，容量w”的最优解 (dp[i-1][w]) - “前
i-1个物品，容量w-weight[i]”的最优解 (dp[i-1][w-weight[i]])
我们相信
dp[i-1][w]和dp[i-1][w - weight[i]]已经包含了它们各自子问题的最优信息。我们用这些子问题的最优解来构造当前问题的最优解。这正是最优化原理的直接应用。 - “前
总结：最优化原理 vs. 无后效性
- 最优化原理（Optimal Substructure）：关注的是解的结构。它断言全局最优解可以由局部最优解构建而成。这是我们能够写出状态转移方程的理论依据。
- 无后效性（No Aftereffect）：关注的是状态的定义。它要求当前状态包含了所有对未来决策有用的信息，我们不需要回头看历史路径。这是最优化原理能够成立的前提条件。
可以说，正因为状态的定义满足“无后效性”，我们才能够保证子问题的最优解可以被直接用于构建父问题的最优解，从而使得“最优化原理”成立。 这两个性质是动态规划一体两面、相辅相成的核心支柱。
但是像是下围棋和象棋总是存在着某种程度上的先弃后取?
难道AI能够判断出先手和势的存在并且放到价值函数的计算里面?
那这可真的是太厉害了…