算法设计与分析讲义-中科院-陈玉福ch6

《算法设计与分析讲义-中科院-陈玉福ch6》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、100第六章动态规划算法§1.动态规划算法的基本思想动态规划方法是处理分段过程最优化问题的一类及其有效的方法。在实际生活中，有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程是如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。20世纪50年代，贝尔曼（RichardBellman）等人提出了解决这类问题的“最优化原则”，从而创建了最优化问题的一种新的算法――动态规划算法。最优化原则指出，多阶段过程的最优决策序列应当具有性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状

2、态构成一个最优决策序列。这要求原问题的最优解需包含其（相干）子问题的一个最优解（称为最优子结构性质）。动态规划算法采用最优化原则来建立递归关系式（关于求最优值的），在求解问题时有必要验证该递归关系式是否保持最优化原则。若不保持，则不可用动态规划算法。在得到最优值的递归式之后，需要执行回溯以构造最优解。在使用动态规划算法自顶向下（Top-Down）求解时，每次产生的子问题并不总是新问题，有些子问题反复计算多次，动态规划算法正是利用了这种子问题重叠性质。对每一个子问题只计算一次，而后将其解保存在一个表格中，当再次要解此子问题时，只是简单地调用（用常数时间）一下已有

3、的结果。通常，不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。例1．多段图问题设G=(V,E)是一个赋权有向图，其顶点集V被划分成k>2个不相交的子集Vi:1≤i≤k，其中，V1和Vk分别只有一个顶点s(称为源)和一个顶点t(称为汇)，图6-1-1中所有的边(u,v)的始点和终点都在相邻的两个子集Vi和Vi＋1中，而且u∈Vi，v∈Vi＋1。多阶段图问题：求由s到t的最小成本路径（也叫最短路径）。对于每一条由s到t的路径，可以把它看成

4、在k-2个阶段做出的某个决策序列的相应结果：第i步决策就是确定Vi+1中哪个顶点在这条路径上。101V1V2V3V4V57724647992692544s167352732t1710318112411572118551511586图6-1-1一个5段图假设s,v2,v3,…,vk-1,t是一条由s到t的最短路径，再假定从源点s(初始状态)开始，已经作出了到顶点v2的决策(初始决策)，则v2就是初始决策产生的状态。若将v2看成是原问题的子问题的初始状态，这个子问题就是找一条由v2到t的最短路径。事实上，路径v2,v3,…,vk-1,t一定是v2到t的一条最短路径

5、。不然，设v2,q3,…,qk-1,t是一条由v2到t的比v2,v3,…,vk-1,t更短的路径，则s,v2,q3,…,qk-1,t是一条由s到t的比s,v2,v3,…,vk-1,t更短的路径，与前面的假设矛盾。这说明多段图问题具有最优子结构性质。例2．0/1背包问题有n件物品，第i件重量和价值分别是wi和pi,i=1,2,…,n。要将这n件物品的某些件装入容量为c的背包中，要求每件物品或整个装入或不装入，不许分割出一部分装入。0/1背包问题就是要给出装包方法，使得装入背包的物品的总价值最大。这个问题归结为数学规划问题：max∑pixi1≤i≤ns.t.∑wx

6、≤c,x∈1,0{},i=,2,1",n(6.1.1)iii1≤i≤n0/1背包问题具有最优子结构性质。事实上，若y,y,",y是原问题的最12n优解，则y,",y将是0/1背包问题的下述子问题：2nmax∑pixi2≤i≤ns.t.∑wx≤c−yw,x∈1,0{},i=,2",n(6.1.2)ii11i2≤i≤n102的最优解。因为，若y,'",y'是子问题(6.1.2)的最优解，且使得2n∑piy'i>∑piyi(6.1.3)2≤i≤n2≤i≤n则y,y,'",y'将是原问题(6.1.1)的可行解，并且使得12npy+∑py'>∑py(6.1.4)11ii

7、ii2≤i≤n1≤i≤n这与y,y,",y是最优解相悖。12n例3.矩阵连乘问题给定n个数字矩阵A1，A2，…，An，其中Ai与Ai+1是可乘的，i=1,2,…,n-1.求矩阵连乘A1A2⋅⋅⋅An的加括号方法，使得所用的数乘次数最少。考察两个矩阵相成的情形：C=AB。如果矩阵A，B分别是p×r和r×q矩阵，则它们的乘积C将是p×q矩阵，其(i,j)元素为rc=∑ab(6.1.5)ijikkjk=1i=1,…,p,j=1,…,q,因而AB所用的数乘次数是prq。如果有至少3个以上的矩阵连乘，则涉及到乘积次序问题，即加括号方法。例如3个矩阵连乘的加括号方法有两种

8、：(A1A2)A3和A1(A2A3)。