Page 185 - 数学建模算法与应用

第七章 动态规划研究

第七章 动态规划研究

第一节 动态规划的引言

一、 动态规划的发展及研究内容

动态规划（dynamic programming）是运筹学的分支，其是求解决策过程最优
化的数学方法。在 20 世纪 50 年代初 由 R. E. Bellman 等学者在对多阶段策过程
的优化问题研究中提出了著名的最优性原理，其把多阶段过程转化为一系列单阶
段的问题，再逐个求解，从而创立了解决这类过程优化问题的新方法。在 1957

年 R. E. Bellman 出版了他的名著《Dynamic Programming》，这是该专业领域的
第一本著作。早期概念与提出在 1950 年代，动态规划的概念最早由美国数学家
理查德·贝尔曼（Richard Bellman）在 20 世纪 50 年代提出。1951 年，贝尔曼提

出了“最优化原理”（Principle of Optimality），这是动态规划的核心理论基础。
最优化原理指出，一个最优策略的子策略也必须是最优的。1957 年贝尔曼出版
了《动态规划》（Dynamic Programming）一书，这是第一本系统介绍动态规划
理论的专著，奠定了动态规划的理论基础。

初步发展与应用于 1960 年代，动态规划开始在多个领域得到应用。这一
时期，动态规划被广泛用于解决生产调度、资源分配、库存管理等实际问题。
1962 年，贝尔曼和 Dreyfus 合作出版了《应用动态规划》（Applied Dynamic
Programming），进一步推广了动态规划的应用。1960 年代中期，动态规划在计

算机科学中开始受到关注。研究人员开始将动态规划应用于算法设计，如字符串
匹配、最长公共子序列等问题。
理论与算法的深化于 1970 年代，动态规划的理论和算法得到了进一步的发

展。1970 年代初，研究人员提出了多种优化动态规划算法的方法，如状态压缩、
状态合并和状态剪枝等，这些方法显著提高了动态规划的计算效率。在 1970 年
代末，动态规划在计算机科学中的应用进一步扩展，特别是在数据结构和算法设
计中。1977 年，Eugene Lawler 出版了《组合优化：网络和图》（Combinatorial

175