动态规划
分析解决多阶段决策过程最优化问题的方法
条目
历史版本
动态规划（Dynamic Programming，DP[3]）是分析解决多阶段决策过程最优化问题的一种方法[2]。它主要求解以时间化分阶段的动态过程的优化问题，对于静态问题，也可以用它来解决。动态规划是考察问题的一种途径，而不是具体的算法[13]。
动态规划起源于20世纪40年代人们对于水利资源多级分配、库存多级存储等问题的研究，美国数学家贝尔曼（R.Bellman）逐渐发现了多阶段决策问题的背后结构，并指出逆序归纳法到底是如何求解多阶段决策问题的[4]。1949年，他提出了著名的最优化原理（principle of optimality），次年，贝尔曼经过反复斟酌确定了“动态规划”这一名称。1957年，贝尔曼出版了他的书籍《动态规划》（Dynamic Programming），并在1961年、1962年相继再版此书，进一步阐明了动态规划的理论和方法[3]。
动态规划有求解更容易、效率更高等优势[8]，但是，它也存在着应用条件苛刻、通用性不足的限制[8]。动态规划的求解常用到阶段、状态、决策、策略、效果函数等一系列基本概念[9]，一般步骤可分为6步，核心思路为构建基本方程。[14] 动态规划具有顺序解法、逆序解法等基本求解方法[15]。
动态规划的常见类型有多维动态规划[5]、随机动态规划[6]。变分法是另一种求最优结果的方法，对于复杂的变分问题，也可以利用动态规划法进行求解。[7]动态规划问题有许多经典的案例，如背包问题、机器负荷分配问题[10][11]。动态规划在现实世界的许多领域得到了广泛的应用，例如生产调度、资源分配、设备更新、信息处理、模式识别等，成为了运筹学中的活跃分支[4]。