3.4 动态规划与贝尔曼方程

3.4 动态规划与贝尔曼方程

本节摘要：动态规划（DP）处理多阶段决策——当前选择会改变后续可选局面。核心是最优性原理与贝尔曼方程：每个局面的最优值由"当下收益 + 下一局面的最优值"递归定义。本节以背包装载与设备更换两条战线演示正向递推与反向递归，并讨论状态维度爆炸（维数灾难）的成因与缓解。

一个背包引出的递归

港口技术员要带一批备件上岛检修，背包承重 5 公斤，备件有四类：工具包重 2 公斤价值 3，检测仪重 3 公斤价值 4，密封件重 4 公斤价值 5，耗材包重 5 公斤价值 6。带哪些组合价值最大？

枚举 2⁴ 种组合当然可以，但备件类数一多就爆炸。动态规划的视角是：把"带什么上岛"这个大决策，切成"逐件考虑、每件拿或不拿"的一串小决策；每考虑完一件，背包剩余承重就是新的"局面"（状态）。贝尔曼方程写出来很朴素：

V(k, w) = max{ V(k+1, w)（不拿第 k 件）, vₖ + V(k+1, w−wₖ)（拿，若装得下） }

含义：在还剩 k 类备件可挑、剩 w 公斤承重时，最优价值等于两条分支的较大者。最优性原理保证这样做是对的：最优决策序列的任何尾巴自身也必须是最优的——否则把尾巴换成更好的，整条序列就更优，矛盾。

def knapsack(weights, values, cap):
    n = len(weights)
    V = [[0] * (cap + 1) for _ in range(n + 1)]
    for k in range(n - 1, -1, -1):            # 反向：从最后一件往前
        for w in range(cap + 1):
            best = V[k + 1][w]                  # 不拿
            if w >= weights[k]:
                best = max(best, values[k] + V[k + 1][w - weights[k]])
            V[k][w] = best
    # 回溯取出选择
    w, picks = cap, []
    for k in range(n):
        if V[k][w] != V[k + 1][w]:
            picks.append(k); w -= weights[k]
    return V[0][cap], picks

val, picks = knapsack([2, 3, 4, 5], [3, 4, 5, 6], 5)
print("最大价值:", val, " 选择备件:", picks)   # 7 选择工具包和检测仪
​

填表只用了 n×cap 次运算——DP 把指数级的枚举折叠成了多项式级的填表，代价是必须把状态空间整个铺开存好。回溯阶段展示了一个常被忽略的事实：DP 表存的不只是终值，还有整棵决策树的最优路径信息。

正向递推：设备更换问题

背包用的是反向递归（从最后阶段往回推）。另一类问题更适合正向推进：设备更换。一台仪器可用四年，第 t 年末置换的维护成本随役龄增长：役龄 0、1、2、3 年的当年维护费为 1、2、4、7（万元），置换一次花 3。四年总成本最小化？把"役龄"当状态、每年"保养或置换"当决策，正向递推即可：

maint = {0: 1, 1: 2, 2: 4, 3: 7}
REPLACE_COST, YEARS = 3, 4
cost = {0: 0}                      # 初始役龄 0，已花 0
for year in range(YEARS):
    nxt = {}
    for age, c in cost.items():
        # 保养：役龄加一，付维护费
        nxt[age + 1] = min(nxt.get(age + 1, 1e9), c + maint[age])
        # 置换：付置换费加新机首年维护
        nxt[1] = min(nxt.get(1, 1e9), c + REPLACE_COST + maint[0])
    cost = nxt
print("四年最小总成本:", min(cost.values()))   # 13
​

两种递推方向的选择标准：如果终局状态固定（背包必须考虑完全部备件），反向自然；如果初始状态固定、要的是终点最优（设备从役龄 0 出发），正向顺手。本质都是贝尔曼方程，只是填表方向不同。

维数灾难与缓解之道

DP 的软肋在状态维度。背包加一个"体积限制"变成二维状态，表从 n×W 变成 n×W×V；设备更换若管理一个仪器队（10 台各有一个役龄），状态是役龄向量，组合数天文级增长——这就是维数灾难。缓解手段三条：近似动态规划（对值函数做函数逼近而不是查表，强化学习正在这条路上）；分解与滚动（把长时段切成近程精算 + 远程粗估的滚动窗口）；状态重构（把多个设备的役龄聚合成"平均役龄与最老役龄"两个量，牺牲精确性换维数）。第 8 章讲 MDP 与 Q-learning 时，维数灾难会再次登场，那时你已知道它的家谱。

💡 关键直觉：动态规划不是一种算法，是一种"把重叠子问题只算一次"的记账纪律。看出递归结构、定义好状态，问题就解决了一大半。

从背包到资源分配：DP 的变式演练

背包结构在工业里的马甲多得惊人，值得再做一轮变式推演。下料问题：钢管原料定长，客户要各种长度，怎么切最省料——把"剩余长度"当状态、每种切法当动作，就是一维背包。广告预算分配：总额预算分到多个渠道，各渠道的回报曲线是离散表——渠道即阶段、剩余预算即状态，与背包完全同构。机器人爬楼梯：每次一步或两步，到顶的走法数——贝尔曼方程退化成斐波那契递推，是动态规划的入门第一题。做变式时训练一个动作：先写状态定义，再写转移方程，最后才想存表与实现。状态定义错了（比如背包忘了剩余容量这个维度），后面全错；状态定义对了，方程几乎是自己写出来的。这个"状态优先"的肌肉记忆，是从会做题到会建模的分水岭，也是第 8 章建模式决策过程的直接前置。

本节要点回顾

• 贝尔曼方程：局面最优值 = 当下收益 + 下一局面最优值，递归定义；
• 最优性原理：最优路径的尾巴也是最优的，这是 DP 正确性的全部来源；
• 填表把指数枚举折叠成多项式计算，代价是状态空间必须完整存储；
• 递推方向看端点：终局定则反向，起点定则正向，方程本质相同；
• 维数灾难是 DP 唯一的天敌，函数逼近与滚动窗口是两条主流退路。

四件确定性兵器配齐。至此我们都假设沙盘上的数字是确定的——下一章开始，需求、到达、对手全部变成随机变量，战争在雾中进行。