欢迎来到动态规划 (Dynamic Programming)!
欢迎来到决策数学 (Decision Mathematics) 中最强大的工具之一！如果你曾经规划过一段需要多次转乘的长途旅行，或者尝试过如何在有限的预算下进行数个月的支出安排，其实你已经运用过动态规划 (Dynamic Programming, DP) 的逻辑了。
在本章中，我们将探讨一种“分而治之”(divide and conquer) 的方法。我们不会试图一次解决一个庞大又吓人的问题，而是将其拆解为较小、易于处理的“阶段”(stages)，并一步步完成它们。别担心一开始看起来数据量很大——一旦你掌握了表格的运作规律，这件事会变得非常有节奏感（而且是好的那种重复！）。
1. 核心概念：贝尔曼最优性原理 (Bellman’s Principle of Optimality)
在我们研究表格和数字之前，必须先理解 DP 的黄金法则，这被称为贝尔曼最优性原理 (Bellman’s Principle of Optimality)。
原理： 一个最优策略具有这样的属性：无论初始状态和初始决策为何，剩余的决策对于由第一次决策所产生的状态而言，必然构成一个最优策略。
等等，能说人话吗？
想象一下，从伦敦到爱丁堡的最短路线经过约克 (York)。贝尔曼其实只是说：这段旅程中“约克到爱丁堡”的部分，必须是从约克到爱丁堡所有可能路径中的最短路径。如果不是，你只需要换一条从约克到爱丁堡更好的路，整段伦敦到爱丁堡的旅程就会变得更短！
小贴士： 在考试中，你几乎总是需要逆向 (backwards) 思考。我们从终点线开始，一路往起点回推。这确保了我们找到的每一个子路径都已经是“最佳”的选择。
重点总结： 最优路径的任何一部分，本身也必然是一条最优路径。
2. 动态规划的术语
要建立表格，我们需要先熟悉这些专有名词。有两个主要的变量是你必须知道的：
- 阶段 (Stage)： 这通常代表“距离终点还有多少步”。如果你距离终点还有 3 个站，你就是在第 3 阶段。
- 状态 (State)： 这描述了你在某个阶段开始时的当前状况或位置。（例如：“我现在位于顶点 C”）。
比喻：电子游戏
想象一个有 5 个关卡的游戏。
阶段 (Stage) 是你正处于第几关（倒数至最终头目）。
状态 (State) 是你在进入该关卡开始时，拥有多少生命值或弹药。
3. 通过列表法 (Tabulation) 解决问题
Edexcel 课程大纲要求你使用特定的表格格式。它看起来可能让人望而生畏，但它遵循着逻辑流向。我们通常从阶段 \(n\)（最后一步）向后工作，回到阶段 1（第一步）。
标准表格栏位：
- 阶段 (Stage)： 剩余的步数。
- 状态 (State)： 在此阶段你的起点。
- 动作 (Action)： 你决定下一步要去哪里。
- 目的地 (Destination)： 下一个阶段你所到达的状态。
- 数值 (Value)： 当前动作的成本/利润 + 从前一个阶段得出的最佳值。
- 最优值 (Optimal Value)： 该特定状态的“最佳”结果。
你知道吗？
这种逆向工作的过程称为自下而上法 (Bottom-up approach)。从目的地规划路径回起点感觉可能有点反直觉，但它能防止你重复计算相同的路径，效率极高！
4. 不同类型的目标
根据题目不同，你可能需要寻找不同类型的“最优”路径。请仔细留意以下词汇：
A. 最小化 (Minimising，如最短路径或最低成本)
你想要的是总和最小。
公式： \(Value = (\text{当前成本}) + (\text{前一阶段的最优值})\)
B. 最大化 (Maximising，如最高利润)
你想要的是总和最大。
公式： \(Value = (\text{当前利润}) + (\text{前一阶段的最优值})\)
C. 极小极大化 (Minimax，即“安全第一”路线)
你想要找到一条路径，使得你面临的最大惩罚尽可能小。这常见于涉及风险或桥梁“最大载重”的问题。
公式： \(Value = \max(\text{当前值, 前一阶段的最优值})\)
然后，在你的最优值栏位中选择这些最大值中的最小值。
D. 极大极小化 (Maximin，即“最坏情况下的最好”路线)
你想要确保你的最小收益尽可能大。
公式： \(Value = \min(\text{当前值, 前一阶段的最优值})\)
然后，在你的最优值栏位中选择这些最小值中的最大值。
快速复习盒：
- 最小化 (Minimise)： 总和最小。
- 最大化 (Maximise)： 总和最大。
- 极小极大化 (Minimax)： 最大值中的最小值。
- 极大极小化 (Maximin)： 最小值中的最大值。
5. 逐步建立表格
如果一开始觉得棘手别担心！请依照以下步骤解决标准的最小路径问题：
- 识别阶段： 在网络图上画出垂直线。最终目的地是第 0 阶段（无后续动作）。直接连向目的地的节点属于第 1 阶段。
- 开始绘表： 建立你的栏位，从第 1 阶段开始。
- 填写第 1 阶段： 列出所有能到达目的地的状态。其“最优值”就是该弧线前往目的地的权重。
- 移至第 2 阶段： 列出所有能到达第 1 阶段中那些节点的状态。对于每一个动作，将弧线权重与你刚刚在第 1 阶段找到的“最优值”相加。
- 挑选优胜者： 对于每个状态，查看所有可能的动作，并选择能产生最佳结果（例如：最小值）的那一个，填入“最优值”栏。
- 重复： 继续操作，直到到达第 \(n\) 阶段（你的起点）。
- 回溯： 表格完成后，从初始节点开始，依照“动作”栏位的指引，即可找出你的路径。
6. 避免常见错误
- 顺向工作： 除非题目明确要求（在 DM2 中这很罕见），否则请务必从目的地向起点逆向工作。
- 计算失误： 由于 DP 是链式结构，在第 1 阶段的一个微小加法错误都会摧毁之后所有的阶段。务必仔细检查你的加总！
- 搞混极大极小化与极小极大化： 记住：极小极大化 (Minimax) 是最小化一个最大值；极大极小化 (Maximin) 是最大化一个最小值。将公式写在试卷顶端以防混乱。
- 遗漏动作： 确保表格中考虑了从某个状态出发的所有可能路径。
总结与重点回顾
恭喜！ 你已经掌握了动态规划的基础。以下是复习时需要记住的要点：
- 贝尔曼原理： 最优路径由最优子路径组成。
- 逆向规划： 我们从终点往起点构建表格。
- 列表法： 精确的表格是满分的关键。保持栏位整洁！
- 状态与阶段： 阶段是时间/距离上的“步数”；状态则是该步数时你“身处何处”。
继续练习表格的排版——这是考试最常见的考察方式。你能行的！