动态规划 --- 算法思想介绍

一.动态规划的基本概念

动态规划在五种算法设计方法中难度最大，它建立在最优原则的基础上.采用动态规划方法，可以高效地解决许多用贪婪算法或分治法无法解决的问题.动态规划(dynamic programming)属运筹学中的规划论分支，是求解决策过程最优化的数学方法.20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划.

二.动态规划的适用条件

任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用.同样，动态规划也并不是万能的.适用动态规划的问题必须满足最优化原理和无后效性.

1.最优化原理（最优子结构性质） 一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略.一个最优化策略的子策略总是最优的.一个问题满足最优化原理又称其具有最优子结构性质.

如图，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线. 反证法证明：假设有另一路径J'是B到C的最优路径，则A到C的路线取I和J'比I和J更优，矛盾.从而证明J'必是B到C的最优路径. 最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法计算.哪些问题满足最优化原理？ 动态规划的最优化理在其指标函数的可分离性和单调性中得到体现.根据最优化原理导出的动态规划基本方程是解决一切动态规划问题的基本方法.

2.无后向性 将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态.换句话说，每个状态都是过去历史的一个完整总结.这就是无后向性，又称为无后效性.如果用前面的记号来描述无后向性，就是：对于确定的xk，无论p1,k-1如何，最优子策略pkn*是唯一确定的，这种性质称为无后向性.

3.子问题的重叠性 动态规划将一些具有指数级复杂度的搜索算法改进成了具有多项式时间的算法.其中的关键在于解决冗余，这是动态规划算法的根本目的.动态规划实质上是一种以空间换时间的技术，在实现中往往存储各种状态，故空间复杂度大于其它的算法.例如Bitonic旅行路线问题：动态规划的时间复杂度为O(n2)，搜索算法的时间复杂度为O(n!) ，但从空间复杂度来看，动态规划算法为O(n2)，而搜索算法为O(n) .选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题.但是经分解得到的子问题往往不是互相独立的.不同子问题的数目常常只有多项式量级.在用分治法求解时，有些子问题被重复计算了许多次.

如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法.

设原问题的规模为n，当子问题树中的子问题总数是n的超多项式函数，而不同的子问题数只是n的多项式函数时，动态规划法显得特别有意义，此时动态规划法具有线性时间复杂性.所以，能够用动态规划解决的问题还有一个显著特征：子问题的重叠性.这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势.

三.动态规划的基本思想:

前面介绍了动态规划理论，称为标准动态规划，因为它具有明显的阶段划分和状态转移特征.这是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析.在实际应用中，许多问题的阶段划分并不明显，这时如果刻意地划分阶段法反而麻烦.一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决.

动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略. 动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解.其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题.因此贪心法自顶向下，一步一步地作出贪心选择；

而分治法中的各个子问题是独立的 (即不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解.但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题.

动态规划法用于最优化问题，这类问题会有多种可能的解，而动态规划找出其中最优值的解.若存在若干个取最优值的解的话，它只取其中的一个.该方法通过求解局部子问题的解达到全局最优解.与分治法和贪心法不同的是，动态规划允许这些子问题不独立，(各子问题可包含公共的子子问题) ，该方法对每一个子问题只解一次，并保存结果，避免每次碰到时都要重复计算.

动态规划法所针对的问题的特征：对应的子问题树中的子问题呈现大量的重复.关键：对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，以后再遇到时不必重新求解. 实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行：

• 分析最优解的性质，并刻划其结构特征.

• 递归地定义最优值.

• 以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值.

• 根据计算最优值时得到的信息，构造一最优解.

步骤(1)--(3)是基本步骤.在只需要求出最优值的情形，步骤(4)可以省略.若需要求出问题的一个最优解，则必须执行步骤(4).此时，需要利用在步骤(3)中计算最优值时记录的许多信息.

参考毕方明老师《算法设计与分析》课件.

欢迎大家访问个人博客网站---乔治的编程小屋,和我一起为大厂offer努力!