每日科技名词|动态规划

情毒

动态规划

dynamic programming

定义：利用问题的最优子结构性，将待求解问题分解成若干个子问题求解，从这些子问题的解得到原问题的解。在此过程中，需记录已经解决的子问题的解，以避免重复计算。

学科：计算机科学技术_理论计算机科学_算法设计与分析

相关名词：运筹学 背包问题 最短路径

【延伸阅读】


图片来源：视觉中国

在现实生活中，有些事物的发展过程可以分为若干个互相联系的阶段，在每一个阶段都要作出决策，一个阶段的决策确定以后，常常影响到下一个阶段的决策，这样一个任务则可以称之为多阶段决策问题。其中，各个阶段的决策构成一个决策序列，称为一个策略。动态规划就是求解决策过程优化问题的一种思想，用一句话来描述就是：每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到，而不管之前这个状态是如何得到的。

动态规划的实质是分治思想和解决冗余。所谓分治就是将实际问题分解为更小的、相似的子问题；而解决冗余是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，目的是在求解重叠子问题时不必做重复的计算，所以它的空间复杂度要大于其他的算法，但这是可以接受的。

动态规划算法解决的问题一般有这样几个特点。1.最优子结构性质：问题的最优解所包含的子问题的解也是最优的，从局部解逐渐得到最优解。2.无后效性：即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。3.子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题会被重复计算多次，所以对每个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

动态规划广泛应用于经济管理、工业生产、自动化控制等领域，尤其在生产经营、资金管理、资源分配、最短路径和复杂系统可靠性等一些经典问题的求解中取得了显著的效果。

（延伸阅读作者：大连理工大学计算机学院教授 杨鑫 ）