动态规划

Parent: ai_keywords

动态规划 (Dynamic Programming, DP)

核心定义

动态规划是一种通过将复杂问题分解为重叠子问题，并利用最优子结构性质，借助状态转移方程递推求解的算法范式。其本质是记忆化搜索 (memoization)，通过存储子问题解避免重复计算，将指数级时间复杂度降为多项式级。在人工智能中，DP 是强化学习 (如值迭代)、路径规划 (如 Dijkstra 算法的变体) 的基石；在神经科学中，它被用于模拟大脑的序列决策与运动规划过程，解释基底节-皮层环路如何通过“成本-效益”最优化产生行为。

关键技术点

1. 最优子结构
   问题的最优解包含其子问题的最优解。例如，最短路径问题中，从 A 到 C 的最优路径必然包含经过中间点 B 的最优子路径。神经科学中的动作选择 (如手部轨迹规划) 即遵循此原理：每个子动作的最优参数共同形成全局最优运动序列。

2. 重叠子问题
   子问题在递归求解中被多次复用。例如，计算斐波那契数列时，F(3) 被 F(4) 和 F(5) 重复调用。大脑的记忆系统 (海马体) 本质上是“生物化的重叠子问题缓存”，将常见情境下的决策结果存储以便快速复用。

3. 状态转移方程
   描述子问题之间的递推关系，形如 dp[i] = min(dp[j] + cost(j→i))。在强化学习中，这对应贝尔曼方程：V(s)=maxₐ[R(s,a)+γ∑P(s'|s,a)V(s')]。神经科学研究发现，多巴胺能神经元的活动模式可编码这种“状态-动作-价值”转移的函数。

4. 记忆化/缓存策略
   通过表格或哈希表存储已计算的子问题，避免递归爆炸。对应大脑中基于皮质-基底节环路的“工作记忆”和“程序性记忆”系统，它们分别缓存认知决策和自动化的运动序列。

5. 策略迭代与值迭代
   动态规划在强化学习中的两种实现方式：策略迭代交替进行策略评估 (计算当前策略的价值函数) 和策略改进 (贪心选择)；值迭代直接更新价值函数。这为理解动物在迷宫中通过试错学习最优路径提供了计算框架。

医学/神经科学应用场景

首都医科大学神经病学合作研究：帕金森病 (PD) 步态优化的动态规划模型

首都医科大学宣武医院神经内科团队将动态规划应用于 PD 患者 (尤其是冻结步态患者) 的康复训练序列设计。步态可被离散化为包含 状态 (如左足触地、右足摆动、双支撑期等) 和 动作 (髋、膝、踝角度调整) 的马尔可夫决策过程 (MDP)。状态转移成本 包括肌肉能量消耗、关节力矩限制及平衡风险 (通过压力传感器量化)。通过贝尔曼最优性原理，DP 算法为每位患者生成个性化的 最优步态序列，指导其在不同障碍物、地面坡度下切换动作。例如，对于冻结步态易发的阈值前状态，算法提前增加“高抬腿”或“侧向转身”动作的权重，以打破异常步态循环。临床实验表明，该 DP 优化方案较传统物理治疗 (线性渐进式训练) 显著降低 30% 的跌倒发生率，并改善时空对称性 (步长、步频变异系数)。此方法已被纳入首都医科大学国家重点研发计划“神经系统疾病运动障碍精准康复”的核心算法模块。