动态规划算法课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,1,,动态规划,3.1,动态规划的设计思想,3.2,动态规划的设计要素,3.3,动态规划算法,的典型应用,,3.3.1,投资问题,,3.3.2,背包问题,,3.3.3,最长公共子序列,LCS,,3.3.4,图像压缩,,3.3.5,最大子段和,,3.3.6,最优二分检索树,,3.3.7,生,物信息学中的动态规划算法,,1 动态规划3.1 动态规划的设计思想,2,0-1,背包问题的建模,一、,问题描述,：,有,n,个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？,二、,总体思路,：,根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填写备忘录表、寻找解组成）找出,0-1,背包问题的最优解以及解组成；,20-1背包问题的建模一、问题描述：有n 个物品，它们有各自,3,0-1,背包问题的建模,实例,：,物品的个数为,4,个，总重量不超过,8,；,30-1背包问题的建模实例：物品的个数为4个，总重量不超过8,4,子问题的界定和计算顺序,子问题的界定：有参数,i,和,j,来界定,i:,表示物品的个数,j :,背包总的装重量,原始输入：,i=4,，,j=8,子问题的计算顺序：,对于给定的,i=1,，看,j=1,2,3,4,…,..,8,的情况,;,i=2,，看,j=1,2,3,4,…,..,8,的情况,;,,4子问题的界定和计算顺序子问题的界定：有参数i和j来界定原始,5,0-1,背包问题求解过程,（,1,）,,把背包问题抽象化（,X1,，,X2,，,…,，,Xn,，其中,Xi,取,0,或,1,，表示第,i,个物品选或不选），,Vi,表示第,i,个物品的价值，,Wi,表示第,i,个物品的重量；,,（,2,）建立模型，即求,max(V1X1+V2X2+…+VnXn),；,,（,3,）约束条件，,W1X1+W2X2+…+WnXn<,总重量；,,（,4,）定义,Fi(j),：当前背包容量,j,，前,i,个物品最佳组合对应的价值；,50-1背包问题求解过程（1） 把背包问题抽象化（X1，X2,6,寻找递推关系式，面对当前商品有两种可能性：,,第一：包的容量比该商品体积小，装不下，此时的价值与前,i-1,个的价值是一样的，即：,F,i,(j)=F,i-1,(j),；,,第二：还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即：,F,i,(j)=max{F,i-1,(j),，,F,i-1,(j-w(i))+v(i)},;,0-1,背包问题求解过程,表示不装第,i,个物品,装了第,i,个商品，背包容量减少了,w(i),,但价值增加了,v(i),；,6寻找递推关系式，面对当前商品有两种可能性：0-1背包问题求,7,由此可以得出递推关系式：,,（,1,）,,j=w(i),：,F,i,(j)=max{F,i-1,(j),，,F,i-1,(j-w(i))+v(i)} ;,,0-1,背包问题求解过程,7由此可以得出递推关系式：0-1背包问题求解过程,8,备忘录表填写：,,,0-1,背包问题求解过程,考虑初始状态是什么？,F,0,(j)=F,i,(0)=0,,,8备忘录表填写：0-1背包问题求解过程考虑初始状态是什么？F,9,备忘录表填写：,,,0-1,背包问题求解过程,考虑初始状态是什么？,F,0,(j)=F,i,(0)=0,,,9备忘录表填写：0-1背包问题求解过程考虑初始状态是什么？F,10,0-1,背包问题求解过程,具体分析：,当,i=1,时：,j=1, w(1)=2, j=w(1),,F,1,(2)=max{F,0,(2),F,0,(2-2)+v(1)} =max{0,0+3}=3;,,j=3, w(1)=2, j>=w(1),,F,1,(3)=max{F,0,(3),F,0,(3-2)+v(1)} =max{0,0+3}=3;,,j=4, w(1)=2, j>=w(1),,F,1,(4)=max{F,0,(4),F,0,(4-2)+v(1)} =max{0,0+3}=3;,,,,,,,,100-1背包问题求解过程具体分析：,11,备忘录表填写：,,,0-1,背包问题求解过程,考虑初始状态是什么？,F,0,(j)=F,i,(0)=0,,,11备忘录表填写：0-1背包问题求解过程考虑初始状态是什么？,12,0-1,背包问题求解过程,当,i=2,时：,j=1, w(2)=3, j=w(2),,F,2,(3)=max{F,1,(3),F,1,(3-3)+v(2)} =max{3,0+4}=4;,,j=4, w(2)=3, j>=w(2),,F,2,(4)=max{F,1,(4),F,1,(4-3)+v(2)} =max{3,0+4}=4;,,j=5, w(2)=3, j>=w(2),,F,2,(5)=max{F,1,(5),F,1,(5-3)+v(2)} =max{3,3+4}=7;,,,,,,,,,120-1背包问题求解过程当i=2时：,13,备忘录表填写：,,,0-1,背包问题求解过程,考虑初始状态是什么？,F,0,(j)=F,i,(0)=0,,,13备忘录表填写：0-1背包问题求解过程考虑初始状态是什么？,14,备忘录表填写：,,,0-1,背包问题求解过程,考虑初始状态是什么？,F,0,(j)=F,i,(0)=0,,,14备忘录表填写：0-1背包问题求解过程考虑初始状态是什么？,15,备忘录表填写：,,,0-1,背包问题求解过程,如何从备忘录得出问题的解？,15备忘录表填写：0-1背包问题求解过程如何从备忘录得出问题,16,备忘录表填写：,,,0-1,背包问题求解过程,如何从备忘录得出问题的解？,16备忘录表填写：0-1背包问题求解过程如何从备忘录得出问题,17,1),当,F,i,(j)=F,i-1,(j),时，说明没有选择第,i,个商品，则回到,F,i-1,(j),；,2),否则：,F,i,(j)=F,i-1,(j-w(i))+v(i),时，说明装了第,i,个商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到,F,i-1,(j-w(i)),；,3),一直遍历到,i,＝,0,结束为止，所有解的组成都会找到。

寻解方式：,171) 当Fi(j)=Fi-1(j)时，说明没有选择第i,18,备忘录表填写：,,,0-1,背包问题求解过程,,,,,第,4,个选择,第,3,个不选,第,2,个选择,第,1,个不选,解：,,,,,,,18备忘录表填写：0-1背包问题求解过程第4个选择第3个不选,19,动态规划算法,:0-1,背包问题,19动态规划算法:0-1背包问题,20,动态规划算法,:0-1,背包问题,20动态规划算法:0-1背包问题,21,X,的子序列,Z,,：设序列,X,,,Z,,,,,,若存在,X,的元素构成的下标严格递增序列,使得 ， 则称,Z,是,X,的,子序列,X,与,Y,的,公共子序列,Z,,：,Z,是,X,和,Y,的子序列,子序列的长度,：子序列的元素个数,,,,相关概念,3.3.3,,最长公共子序列,LCS,21X 的子序列 Z ：设序列 X, Z,相关概念3.3.,22,给定序列,X,=<,x,1,,,x,2,, … ,,x,m,>,,Y,=<,y,1,,,y,2,, … ,,y,n,>,求,X,和,Y,,的最长公共子序列,实例,问题描述,X,: A B C B D A B,Y,:,,,,B D C A B A,22给定序列 X=, Y,23,给定序列,X,=<,x,1,,,x,2,, … ,,x,m,>,,Y,=<,y,1,,,y,2,, … ,,y,n,>,求,X,和,Y,,的最长公共子序列,实例,问题描述,X,:,,A,B C B,,,D,A,B,Y,:,,,,B,D,C,A,B A,一个最长公共子序列,:,,B,,C,,B,,A,23给定序列 X=, Y,24,蛮力算法,24蛮力算法,25,子问题边界：,,X,和,Y,起始位置为,1,，,X,的终止位置是,m,，,Y,的终止位置是,n,，记作,,X,i,=<,x,1,,,x,2,,…,,x,m,>,，,Y,j,=<,y,1,,,y,2,,…,,y,n,>,依赖关系：,,X,=<,x,1,,,x,2,,…,,x,m,>,,Y,=<,y,1,,,y,2,,…,,y,n,>,,Z,=<,z,1,,,z,2,,…,,z,k,>,，,,子问题的界定,25子问题边界： X和Y 起始位置为1，X的终止位置是 m,26,子问题的依赖关系,26子问题的依赖关系,27,令,X,与,Y,的子序列,,X,i,= <,x,1,,,x,2,, … ,,x,i,>,，,Y,j,= <,y,1,,,y,2,, … ,,y,j,>,,C,[,i,,,j,],：,X,i,与,Y,j,的,LCS,的长度,递推方程,,,,,优化函数的递推方程,27令 X 与 Y 的子序列优化函数的递推方程,28,标记函数：,B,[,i, j,],,其值为字符,↖、,,、,,，,,标记函数,28标记函数：B[i, j], 其值为字符↖、、，标记,算法,3.4,,LCS(,X,,,Y,,,m,,,n,),1. for,i,,1 to,m,do,//,行,1-4,边界情况,2.,C,[,i,,0],0,3. for,i,,1 to,n,do,4.,C,[0,,i,],0,5. for,i,,1 to,m,do,,6,．,for,j,,1 to,n,do,7. if,X,[,i,]=,Y,[,j,],8. then,C,[,i,j,],C,[,i,,1,,j,,1]+1,9.,B,[,i,j,],’,,’,10. else if,C,[,i,,1,,j,],,,C,[,i,,,j,,1],11. then,C,[,i,j,],C,[,i,,1,,j,],12.,B,[,i,j,],’,,’,13. else,C,[,i,j,],C[,i,,,j,,1],14.,B,[,i,j,],’,,’,29,动态规划算法伪代码表示,初值,子问题,X,i,,Y,j,算法3.4 LCS(X,Y,m,n) 29动态规划算法,30,利用标记函数构造解,算法,3.5,,Structure Sequence(,B, i, j,),输入：,B,[,i,,,j,],输出：,X,与,Y,的最长公共子序列,,,1. if,i,=0 or,j,=0 then return //,一个序列为空,,2. if,B,[,i,,,j,] =,“↖”,,,3. then,输出,X,[,i,],,4. Structure Sequence(,B, i,－,1,, j,－,1),,5. else if,B,[,i,,,j,]=,“,,”,then Structure Sequence (,B,,,i,－,1,,j,),,6. else Structure Sequence (,B,,,i,,,j,－,1),30利用标记函数构造解算法3.5 Structure Se,输入：,X,=,,Y,=,，,优化函数函数：,,,,,,,,,实例的优化函数表,输入：X=, Y=,根元素，递归进入右子树；,4.,,x,=,根元素，算法停止，输出,x,；,5.,,x,到达叶结点，算法停止，输,出,x,不在数组中,.,,,,,3.3.6,,最优二叉检索树,4,2,,6,,5,3,1,,L,0,L,1,,L,2,,L,4,,L,5,,L,6,,L,3,52S={ 1, 2, 3, 4, 5, 6}，x=3.5检,53,S,={ 1, 2, 3, 4, 5, 6},，,x=3.5,检索方法：,1.,初始，,x,与根元素比较；,2.,,x,<,根元素，递归进入左子树；,3.,,x,>,根元素，递归进入右子树；,4.,,x,=,根元素，算法停止，输出,x,；,5.,,x,到达叶结点，算法停止，输,出,x,不在数组中,.,,,,,3.3.6,,最优二叉检索树,4,2,,6,,5,3,1,,L,0,L,1,,L,2,,L,4,,L,5,,L,6,,L,3,53S={ 1, 2, 3, 4, 5, 6}，x=3.5检,54,S,={ 1, 2, 3, 4, 5, 6},，,x=3.5,检索方法：,1.,初始，,x,与根元素比较；,2.,,x,<,根元素，递归进入左子树；,3.,,x,>,根元素，递归进入右子树；,4.,,x,=,根元素，算法停止，输出,x,；,5.,,x,到达叶结点，算法停止，输,出,x,不在数组中,.,,,,,3.3.6,,最优二叉检索树,4,2,,6,,5,3,1,,L,0,L,1,,L,2,,L,4,,L,5,,L,6,,L,3,54S={ 1, 2, 3, 4, 5, 6}，x=3.5检,55,S,={ 1, 2, 3, 4, 5, 6},，,x=3.5,检索方法：,1.,初始，,x,与根元素比较；,2.,,x,<,根元素，递归进入左子树；,3.,,x,>,根元素，递归进入右子树；,4.,,x,=,根元素，算法停止，输出,x,；,5.,,x,到达叶结点，算法停止，输,出,x,不在数组中,.,,,,,3.3.6,,最优二叉检索树,4,2,,6,,5,3,1,,L,0,L,1,,L,2,,L,4,,L,5,,L,6,,L,3,55S={ 1, 2, 3, 4, 5, 6}，x=3.5检,56,S,={ 1, 2, 3, 4, 5, 6},，,x=3.5,检索方法：,1.,初始，,x,与根元素比较；,2.,,x,<,根元素，递归进入左子树；,3.,,x,>,根元素，递归进入右子树；,4.,,x,=,根元素，算法停止，输出,x,；,5.,,x,到达叶结点，算法停止，输,出,x,不在数组中,.,,,,,3.3.6,,最优二叉检索树,4,2,,6,,5,3,1,,L,0,L,1,,L,2,,L,4,,L,5,,L,6,,L,3,,3.5,56S={ 1, 2, 3, 4, 5, 6}，x=3.5检,57,空隙：,(-,,,,x,1,), (,x,1,,,x,2,), … , (,x,n,1,,,x,n,), (,x,n,,+,) ,,,x,0,= -,,,,x,n,+1,=,,给定序列,S,= <,x,1,,,x,2,, …,,x,n,>,,,x,在,x,i,的概率为,b,i,,,x,在,(,x,i,,,x,i,+1,),的概率为,a,i,,,,S,的存取概率分布如下：,,P,= <,a,0,,,b,1,,,a,1,,,b,2,,,a,2,, … ,,b,n,,,a,n,>,数据元素存取概率分布,,57空隙： (-, x1), (x1, x2), … ,,实例：,S,={1,2,3,4,5,6},P,=<0.04,,0.1,,0.01,,0.2,,0.05,,0.2,,0.02,,0.1,,0.02,,0.1,,0.07,,0.05,,0.04>,,实例：S={1,2,3,4,5,6}P=<0.04,0.1,检索数据的平均时间,4,2,,6,,5,3,1,,L,0,L,1,,L,2,,L,4,,L,5,,L,6,,L,3,T,1,m,(,T,1,)=[1*0.1+2*(0.2+0.05)+3*(0.1+0.2+0.1)],+[3*(0.04+0.01+0.05+0.02+0.02+0.07)+2*0.04],= 1.8+0.71,=,2.51,,在数据结点上的情况,在间隙的情况,,,检索数据的平均时间42 6 531 L0 L1 L2,检索数据的平均时间,2,1,6,3,5,4,,L,0,,L,1,L,2,,L,4,,L,5,,L,6,L,3,m(T2)=,,[1*0.1+2*0.2+3*0.1+4*(0.2+0.05)+5*0.1],+[1*0.04+2*0.01+4*(0.05+0.02+0.04)+5*(0.02+0.07)],= 2.3+0.95=,3.25,T,2,检索数据的平均时间216354 L0 L1 L2,。