《Chapter 15 Dynamic Programming_图文》由会员分享，可在线阅读，更多相关《Chapter 15 Dynamic Programming_图文（69页珍藏版）》请在金锄头文库上搜索。
1、第15章动态规划,引论,动态规划法在本课程介绍的算法设计方法中是最难的应用：（1）0/1背包问题（2）矩阵乘法链（4）最短路径,15.1动态规划原理,从算法设计的角度看,动态规划是一种在各个不同大小(size)的子问题的优化值之间建立递归关系并求解的过程.能用动态规划求解的问题必须满足优化原理:优化解包含的子问题的解也是优化的.利用优化原理,使用枚举法建立不同长度子问题的优化值之间的递归关系动态规划方程.动态规划得到的是精确解.子问题的数目决定算法的复杂性.实现时要尽可能消去递归.,例15-1 多段图,例15-1 最短路经（结论）,多段图问题满足优化原理: 最短路(1-3-5-7)上的子路径(
2、3-5-7) 是3到目的节点7在子图上的最短路.无论最短路的下一跳是2,3,4中的那个节点,其后的路径也应是最短路.节点1到目的节点的最短路长度c(1)可从2,3,4到目的节点的最短路长度c(i)节点1到这些节点的边成本cost(1,i)经枚举得到:c(1)=mini2,3,4c(i)+cost(1,i),多段图的动态规划算法,但2,3,4到目的节点的最短路长度c(2), c(3), c(4) 还不知道!我们须计算c(2),c(3),c(4);仍使用优化原理.一般情形: 设c(i)为i到目的节点的最短路长度, A(i)为与i相邻的结点集合,有: c(i)=minjA(i)c(j)+cost(i
3、, j)但c(i)由i 到目的节点的子图来决定,和节点1怎样走到i 没关系(Markov 性质).我们有c(7)=0,从c(7)开始向前计算,初始c(7)=0依次计算c(6),c(1)：C(6)=1,c(5)=2,c(4)=8+c(6)C(3)=min1+c(5),5+c(6)C(2)=min7+c(5),6+c(6)C(1)=min1+c(2),4+c(3),6+c(4)递归还可从前向后：c(i)=节点1到节点i的最短路的长度；递归从c(1)=0开始。,例15-2 0/1背包问题,0/1背包问题的解指物品1,n的一种放法(x1, ,xn的0/1赋值), 使得效益值最大.假定背包容量不足以装入
4、所有物品:面临选择.因为目标函数是非负数之和=优化原理:无论优化解是否放物品1,相对剩余背包容量,优化解对物品2,n的放法, 也是优化解.,背包问题满足的优化原理,例如n=5,c=10,w=2,2,6,5,4,p=6,3,5,4,6. 其优化解为(1,1,0,0,1),即优化的物品装入背包的方法为 1,2,5.物品1占背包容量2,剩下容量为8.优化解中包含的子问题:n=4,c=c-2(物品1的重量),物品为2,3,4,5(1,0,0,1),即放物品2和5,是上述子问题的优化解.背包问题满足的优化原理.,优化值间的递归式,虽然我们不知道优化解是否放物品1,但我们可以利用优化原理,从枚举“放”和“
5、不放”两种情形建立优化值之间的递归式:设f(i, y)为以背包容量y,放物品i,n,得到的优化效益值,以下递归关系成立:f(1,c)=maxf(2,c), f(2,c-w1)+p1先求子问题的优化值(递归),再从2种可能性中选出最优的.须求解:任意给定容量y, 任意i,n 种物品的子问题.,例15-2 0/1背包问题（解）,n=3, w=100,14,10, p=20,18,15, c=116 放进物品1(x1 = 1),背包容量还剩r=16. x2,x3= 1,0 为子问题的优化解,值为18. 不放物品1(x1= 0)则对于剩下的两种物品而言,容 量限制条件为116，1,1为子问题优化解,值
6、为33前者效益值为38, 后者为33; 所以优化解为1,1,0, 优化值为38.,例15-4 0/1背包,令f(i,y) 表示容量为y,物品i,i+1,n 的优化效益值,按优化原理可列递归关系如下：第2行表示背包容量y不足以放下物品i.,例15-4 0/1背包的DP算法,问题要求计算f(1,c), 所以计算过程中不必计算 f(i, y), yc计算从f(n, *)开始然后应用(15-1)式递归计算 f(i, y) i=n-1,n-2，,2，最按 f(1,c)=maxf(2,c), f(2,c-w1)+p1计算f(1,c).例题15.2：n=3, w=100,14,10, p=20,18,15,
7、 c= 116. 求解如下：,例15-2 0/1背包,利用递归式（15-1）,可得因此最优解f(1,116 )=maxf(2,116),f(2,116-w1)+p1=maxf(2,116),f(2,16)+20 =max33,38=38,例15-2 0/1背包,使用traceback方法从优化值得到优化解: 现在计算x1,xn值, traceback如下:f(1,c) =f(2,c)=x1=0；否则x1=1.设y为确定了x1,xi-1后背包的剩余容量,确定xi如下: 如果wiy, 则xi=0; 如果wiy, f(i,y)=f(i+1,y)=xi=0,否则xi=1.依次类推.该例中,f(2,11
8、6)=33f(1,116),所以x1=1. 剩余容量=116-100=16, f(2,16)=18f(3,16)=14 因此x2=1,此时r=16-14=2,不足以放物品3,所以x3= 0。,例题15.21旅行商问题,求图G=(V, E)的最小成本周游路线(见208页)动态规划解:令S为V的不含节点1的子集, 设g(i,S)表示从节点i 出发,经过S中的所有节点各一次,到达节点1 的最短路长度(子问题的优化值),根据优化原理有以下递归式原问题为g(1,V-1),初始: g(i, )=ci,1;从S=开始，依次对|S|=1,2,n-1,计算,考虑有如下邻接矩阵的图:计算过程如下:g(2,)=c2
9、1=5, g(2,3)=15, g(2,4)=18, g(3,2)=18, g(2,3,4)=minc23+g(3,4),c24+g(4,3) =25 g(1,2,3,4)=minc12+g(2,3,4),c13+g(3,2,4), c14+g(4,2,3),例题15.21货郎担问题,算法的时间复杂度为：|S|=k 的子问题个数为在|S|=k时，求最小值需做k-1次比较算法的时间复杂度(比较次数)为,动态规划法步骤:,在应用动态规划法时,须先验证欲求解的问题是否满足优化原理.应用优化原理建立子问题优化解的值(优化值)之间的递归式.解优化值满足的递归式.回溯(traceback)从优化值构造优化
10、解.在例题1中求优化值的过程中需记录下达到最小值的邻接节点编号, 以便进行traceback.,算法复杂性,直接用递归实现动态规划递归方程往往会引发大量重复计算,算法的计算量变得非常可观.最好使用迭代法实现动态规划算法;迭代实现需要存贮所有子问题的优化解的值f(i,y), 以便避免重复计算,所以算法往往需要较大的存储空间.算法的复杂性来自子问题的数目,通常子问题的数目很大.,15.2.1 0/1背包问题DP算法的实现,1. 递归实现2. 权为整数的迭代实现3. 元组法实现,1. 递归实现,前面已建立了背包问题的动态规划递归方程，程序15-1是该递归方程的直接实现.,程序15-1 背包问题的递归
11、实现,执行调用F(1,c) 返回f(1,c)值.程序15-1的最坏时间复杂性t(n):t(1)=a；t(n)=2t(n-1)+b (n1)， 其中a,b为常数,求解可得t(n)=(2n),例15-5,设n=5,p=6,3,5,4,6,w=2,2,6,5,4 且c=10 ,求f (1,10).为了确定f(1,10),调用函数F(1,10).递归调用关系如图15-1的树型结构所示: 其中每个节点用y值来标记;第j层的节点对应F(j,*);因此根节点表示F(1,10),而它有左、右子节点,分别对应F(2,10)和F(2,8).,图15-1 递归调用树,f(1,10)f(2,*)f(3,*) 节点内标
12、出的数是背包剩余容量y; 未标出的分枝是剩余容量不足以放任何物品.,例15-5（续）,从递归调用树可以看到程序15-1总共执行了28次递归调用.我们注意到,其中重复计算的节点,如f(3,8)计算过两次，相同情况的还有 f(4,8), f(4,6), f(4,2), f(5,8), f(5,6), f(5,3), f(5,2) 和f(5,1).如果保留以前的计算结果,则可将节点数减至19(省略图中的阴影节点的计算).,2. W取整数时的迭代实现,当物品重量为整数时,可设计一相当简单的算法(见程序15-2)来求解f(1,c).该实现用二维数组f iy来保存每个f(i,y) 的值,并且只计算一次.二
13、维数组需(nc)空间.函数Traceback从fiy产生优化的xi值.Knapsack的复杂性(nc),似乎是多项式算法.但因c的二进制输入长度为log2c, 所以nc仍是输入长度的指数函数.Traceback的复杂性为(n).,程序15-2 f 和x 的迭代计算,程序15-2 f 和x 的迭代计算(续1),注: yMax=wi,程序15-2 f 和x 的迭代计算(续2),例题5.6,n=5,p=6,3,5,4,6,w=2,2,6,5,4 且c=10 ,求f (1,10).,3. 元组法实现,程序15-2有两个缺点:1)要求物品重量为整数;2)当背包容量c 很大时,例如c2n,程序15-2的要
14、求的存储空间为(n2n).下述元组法克服了上述缺点.元组法将函数f(i, y)的跳跃点以元组 (y, f(i, y)形式存储于一个线性表P(i)中.表P(i)中的元组(y,f(i, y) 按y的增序排列.P(i)中的元组(a,b)表示:存在一种装物品i,n的方案,能以容量y, aya, a为下一元组的横坐标,得到效益值b.下面给出从f(i+1,y)的线性表P(i+1)得出f(i,y)的线性表P(i)的算法.,元组法,按f(i,y)的定义: f(i, y)=maxf(i+1,y),f(i+1,y-wi)+pi,首先需要从P(i+1)得到函数f*(i+1,y)=f(i+1,y-wi)+pi的元组集
15、合Q.设(a,b)Q, 则(a-wi, b-pi)必为P(i+1)的元组,反之亦然. 所以,P(i+1)的每个元组(w,p)对应Q的一个元组(w+wi, p+pi).Q的元组(u,v)代表装物品i,n的一种方案:以背包容量u,能得到效益值v.需设计一算法从P(i+1)和Q得到f(i,y)的元组(即P(i)的元组),元组法,从P(i+1)和Q得到P(i)的元组: 因P(i+1)和Q内元组均按w和p的增序排列,所以可用以前学过的merge算法进行合并.合并时使用以下支配(选优)规则:设(a,b)和(u,v)是来自P(i+1)和Q的元组,若au且bv,则称(a,b)受(u,v) 支配. 因为(a,b)代表以容量a得到效益值b的方案,而(u,v)代表以较少的容量u得到较大效益值v的装包方案.按(15.1),合并时舍弃被支配的元组(选优).,
