deepread24｜第21章 动态规划详解

ONEPSOFT | 软考学习知识库

---

deepread24｜第21章 动态规划详解

一、定位

• 章节位置：第 21 章 项目管理科学基础 → 21.2.4 动态规划。
• 知识链条：把 " 大问题 " 拆成 " 多阶段决策 "，每阶段选一个决策，整体最优 = 各阶段最优的递推累积。两大代表：最短路（分阶段选路）、资源分配（限量分给多项目求最大收益）。
• 考试分量：综合知识考 " 研究什么问题、基本思想 "；计算/案例考逆序递推（从终点往回算每点的最优子值 fₖ，再回代路径/分配）。

二、教材原文精摘

以下依据第 4 版教材第 21 章 21.2.4 节与例 21-12/例 21-13。例 21-12 给出了 A→E 各阶段距离与逆推 f 值（f₄(D1)=3,f₄(D2)=4；f₃(C1)=8,C2=7,C3=7；f₂(B1)=13,B2=10；f₁(A)=14，最短路径 A→B₂→C₂→D₁→E，距离 14）。本次 fetch 对 " 资源分配（例 21-13）" 仅录递推式，未录具体数表，下方资源分配用构造的典型例题演示。

• 最短路思想：从终点 E 出发逆向求各点的最短子路径，最终得起点到终点最短路径，称为逆序法。
• 递推式（资源分配）：fₖ(Sₖ) = max{ vₖ(xₖ) + fₖ₊₁(Sₖ₊₁) }，状态转移 Sₖ₊₁ = Sₖ − xₖ；第三阶段（末项）直接取收益。

三、系统解读（平实分点）

1. 一句话理解：动态规划 = " 走一步看全局 "，把问题切成若干阶段，从最后阶段往回，算清楚 " 从每个岔口到终点最少/最多多少 "，再顺推回起点选路。
2. 五要素：阶段（第几步）、状态（到某点还剩什么）、决策（这步选啥）、状态转移（选完剩下啥）、指标（这步 + 后续的累计最优）。
3. 最短路（逆序法）：设 fₖ(Xₖ) = 从阶段 k 起点 Xₖ 到终点的最短距离。终点 f=0（或到 E 的距离）；往前 fₖ = min{本段距离 + 下一阶段 f}。算到起点即全局最短。
4. 资源分配：把总量 S 分给 k 个项目，第 k 阶段给项目 k 分 xₖ，余量 S−xₖ 给后面。fₖ(S) = max{本项目收益 vₖ(xₖ) + 后续最优 fₖ₊₁(S−xₖ)}。末项直接取收益。
5. 土木类比：管线路由选最短（A 搅拌站 → 多级中转 → E 工地）；有限台班/预算分给多个单项工程，求总产出最大。

四、工程举例（土木类比 + 数值）

例一 · 最短路（同例 21-12）：A→B{B1,B2}→C{C1,C2,C3}→D{D1,D2}→E。距离已配平，逆序递推：

• f₄(D1)=3, f₄(D2)=4（D→E）。
• f₃(C1)=min(5+3,6+4)=8；f₃(C2)=min(4+3,3+4)=7；f₃(C3)=min(4+3,3+4)=7。
• f₂(B1)=min(5+8,6+7,7+7)=13；f₂(B2)=min(2+8,3+7,4+7)=10。
• f₁(A)=min(2+13, 4+10)=14（取 B2）。
• 回代：A→B2→C2→D1→E，总距离 14。

例二 · 资源分配（构造）：总资源 S=5（台/单位），分给甲、乙、丙三项目，收益 v(x)：

x	0	1	2	3	4	5
甲 v₁	0	2	5	7	9	11
乙 v₂	0	4	6	8	9	10
丙 v₃	0	3	5	7	8	9

逆序：

• f₃(S)=v₃(S)：0,3,5,7,8,9。
• f₂(S)=max_x₂{v₂(x₂)+f₃(S−x₂)}：f₂=[0,4,7,9,11,13]。
• f₁(5)=max_x₁{v₁(x₁)+f₂(5−x₁)}=max{13,13,14,14,13,11}=14（x₁=2 或 3）。
• 回代（取 x₁=2）：余 3 给乙丙；f₂(3)=9 取 x₂=1（或 2）；余 2 给丙 → 丙=2。最优分配 甲 2、乙 1、丙 2（或甲 2 乙 2 丙 1），总收益 14。

高项概念	土木 / 施工类比
阶段 / 状态	管路第几段 / 到某中转点
fₖ 最优子值	从该点到终点的最短/最大
资源分配 xₖ	给某单项工程分的台班/预算

五、追问引导

• 动态规划和 " 分阶段贪心 " 有何不同？（贪心只管当前最优，动态规划管 " 当前 + 后续全局 " 最优，用 f 值传递）
• 逆序法为什么要 " 从终点往回算 "？顺推行不行？（对称也可顺推，逆序更符合 " 从后定前 " 的递推习惯）
• 最短路里 fₖ(Xₖ) 取 min，资源分配里 fₖ(Sₖ) 取 max，为什么符号不同？（最短路最小化距离、资源分配最大化收益）
• 资源分配的状态转移 Sₖ₊₁=Sₖ−xₖ 怎么理解？（给了 xₖ 后，剩下的资源给后面的项目）
• 若例一里 f₂(B2) 出现 " 两个 C 都得到 7" 的并列，回代路径会有几条？（并列最优，任选其一即可，距离相同）