动态规划入门(论文).doc

动态规划思想入门
作者:陈喻(2008年10月7日)
关键字:动态规划,最优子结构,记忆化搜索
引言
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decisionprocess)最优化的数学方法。(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming,这是该领域的第一本著作。
   动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。
动态规划的基本思想
动态规划是:将待求的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解得到原问题的解;对于重复出现的子问题,只在第一次遇到的时候对它直接求解,并把答案保存起来,让以后再次遇到是直接引用答案,不必从新求解,其实质是分治思想和解决冗余。
例1:求A—>B的最短路径
图1
这是一个利用动态规划思想的经典问题,通过直接观察图1我们可以枚举出20多条路径,并可以计算出其中最短的路径长度为16
阶段
用动态规划的思想来分析,我们可以把这个问题转换成下面这个模型
状态
决策
图2
阶段:根据问题的特点和需要,将问题按时间或空间特征分解为若干相互联系的阶段。在本例中,我们根据空间特性将问题分成了6个阶段。
状态: 各阶段的开始条件,本例中,A,B,C……P这些节点都属于状态,表示从该点到B的最短路径,在这里我们计做S(i),表示从第i个节点(状态)到B的最短路径
决策:某阶段状态确定后,从该状态到下阶段某状态的选择。比如S(A),它可以选择通过C到达B,也可以选择通过D到达B。
状态转移方程:系统由某阶段的一个状态转变到下一阶段的另一状态称状态转移,体现转移规律的方程称状态转移方程。在本例中,我们不难推出S(A)=MIN{S(C)+4,S(D)+3},S(C)=MIN{S(E)+5,S(F)+3}…………S(B)=0,由此我们可以得出状态转移方程S(i)=MIN{S(j)+Vij}(j为与i相邻接的节点,Vij表示邻接节点i,j之间的距离
)。
一个动态规划模型应该满足以下几个性质:

最优子结构可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。例如在图2的模型中,S(A)是A到B的最短路径(最优策略),而它所依赖的S(C)和S(D)作为S(A)的子策略分别是C到B的最短路径和D到B的最短路径,也是最优的。因此根据最优子结构性质我们得出了上面的状态转移方程。
证明:如图2设路线W1={(A,C),(C,F),(F,J)}
W2={(J,M),(M,O),(O,B)}
若路线W1和W2是A到B的最优路径,则根据最优化原理,路线W2必是从J到B的最优路线。用反证法证明:假设有另一路径W2'是J到B的最优路径,则A到B的路线取W1和W2'比W1和W2更优,矛盾。从而证明W2'必是J到B的最优路径W2。
最优子结构性质是动态规划的基础,任何问题,如果失去了最优子结构性质的支持,就不可能用动态规划方法计算。根据最优子结构性质导出的动态规划状态转移方程是解决一切动态规划问题的基本方法。
可以看出,图2的模型是满足最优子结构性质的。

在我们根据状态转移方程用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新的,而且某些子问题会被重复计算多次,比如,在求S(C)时需要递归求出S(F)的值,而在求S(D)时也需要递归求出S(F)的值,因此整个求解过程中S(F)的值会被求解两次,如果我们能把这多余的一次重复计算剔除,将可以最大程度的提高程序执行效率;动态规划正是利用了这种子问题的重叠性质,对每个子问题只计算一次,然后将其结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单的查询一下结果,从而获得较高的解题效率,这个方法就是我们常说的记忆化搜索。因此,如果我们把第一次求