《动态规划法》PPT课件.ppt

#includeusingnamespacestd;intbinarysearch(inta,constintx,intleft,intright,int,课后第一题,voidmain()inta6=1,3,5,6,9,11;intx=4;inty=10;inti1,j1,i2,j2;binarysearch(a,x,0,5,i1,j1);binarysearch(a,y,0,5,i2,j2);for(intk=j1;k=i2;k+)coutakV(n-1,C)，表明第n个物品被装入背包，前n-1个物品被装入容量为C-wn的背包中；否则，第n个物品没有被装入背包，前n-1个物品被装入容量为C的背包中。依此类推，直到确定第1个物品是否被装入背包中为止。由此，得到如下函数：,（式6.13）,设n个物品的重量存储在数组wn中，价值存储在数组vn中，背包容量为C，数组Vn+1C+1存放迭代结果，其中Vij表示前i个物品装入容量为j的背包中获得的最大价值，数组xn存储装入背包的物品，动态规划法求解0/1背包问题的算法如下：,在算法6.3中，第一个for循环的时间性能是O(n)，第二个for循环的时间性能是O(C)，第三个循环是两层嵌套的for循环，其时间性能是O(nC)，第四个for循环的时间性能是O(n)，所以，算法6.3的时间复杂性为O(nC)。,x5=1,x4=0,x3=0,x2=1,x1=1,6.3.2最长公共子序列问题,对给定序列X=(x1,x2,xm)和序列Z=(z1,z2,zk)，Z是X的子序列当且仅当存在一个严格递增下标序列(i1,i2,ik)，使得对于所有j=1,2,k，有zj=xij（1ijm）。给定两个序列X和Y，当另一个序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列问题就是在序列X和Y的公共子序列中查找长度最长的公共子序列。,证明最长公共子序列问题满足最优性原理。设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk，记Xk为序列X中前k个连续字符组成的子序列，Yk为序列Y中前k个连续字符组成的子序列，Zk为序列Z中前k个连续字符组成的子序列，显然有下式成立：（1）若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列；（2）若xmyn且zkxm，则Z是Xm-1和Y的最长公共子序列；（3）若xmyn且zkyn，则Z是X和Yn-1的最长公共子序列。可见，两个序列的最长公共子序列包含了这两个序列的前缀序列的最长公共子序列。,要找出序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列，可按下述递推方式计算：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm即可得到X和Y的最长公共子序列；当xmyn时，必须求解两个子问题：找出Xm-1和Y的最长公共子序列以及Xm和Yn-1的最长公共子序列，这两个公共子序列中的较长者即为X和Y的最长公共子序列。用Lij表示子序列Xi和Yj的最长公共子序列的长度，可得如下动态规划函数：L00=Li0=L0j=0(1im,1jn)（式6.14）（式6.15）,由此，把序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列的搜索分为m个阶段，第1阶段，按照式6.15计算X1和Yj的最长公共子序列长度L1j（1jn），第2阶段，按照式6.15计算X2和Yj的最长公共子序列长度L2j（1jn），依此类推，最后在第m阶段，计算Xm和Yj的最长公共子序列长度Lmj（1jn），则Lmn就是序列Xm和Yn的最长公共子序列的长度。,为了得到序列Xm和Yn具体的最长公共子序列，设二维表Sm+1n+1，其中Sij表示在计算Lij的过程中的搜索状态，并且有：,（式6.16）,若Sij=1，表明ai=bj，则下一个搜索方向是Si-1j-1；若Sij=2，表明aibj且Lij-1Li-1j，则下一个搜索方向是Sij-1；若Sij=3，表明aibj且Lij-1Li-1j，则下一个搜索方向是Si-1j。,(a)长度矩阵L(b)状态矩阵S,例：序列X=(a,b,c,b,d,b)，Y=(a,c,b,b,a,b,d,b,b)，建立两个(m+1)(n+1)的二维表L和表S，分别存放搜索过程中得到的子序列的长度和状态。,在算法6.4中，第一个for循环的时间性能是O(n)；第二个for循环的时间性能是O(m)；第三个循环是两层嵌套的for循环，其时间性能是O(mn)；第四个for循环的时间性能是O(k)，而kminm,n，所以，算法6.4的时间复杂性是O(mn)。,6.4查找问题中的动态规划法,6.4.1最优二叉查找树,6.4.2近似串匹配问题,设r1,r2,rn是n个记录的集合，其查找概率分别是p1,p2,pn，最优二叉查找树（OptimalBinarySearchTrees）是以这n个记录构成的二叉查找树中具有最少平均比较次数的二叉查找树，即最小，其中pi是记录ri的查找概率，ci是在二叉查找树中查找ri的比较次数。,6.4.1最优二叉查找树,例如，集合A,B,C,D的查找概率是0.1,0.2,0.4,0.3，(a)的平均比较次数是0.110.22+0.43+0.34=2.9，(b)的平均比较次数是0.120.21+0.42+0.33=2.1，(c)的平均比较次数是0.130.22+0.41+0.32=1.7。,将由r1,r2,rn构成的二叉查找树记为T(1,n)，其中rk（1kn）是T(1,n)的根结点，则其左子树T(1,k-1)由r1,rk-1构成，其右子树T(k+1,n)由rk+1,rn构成。,证明最优二叉查找树满足最优性原理,若T(1,n)是最优二叉查找树，则其左子树T(1,k-1)和右子树T(k+1,n)也是最优二叉查找树，如若不然，假设T(1,k-1)是比T(1,k-1)更优的二叉查找树，则T(1,k-1)的平均比较次数小于T(1,k-1)的平均比较次数，从而由T(1,k-1)、rk和T(k+1,n)构成的二叉查找树T(1,n)的平均比较次数小于T(1,n)的平均比较次数，这与T(1,n)是最优二叉查找树的假设相矛盾。,设T(i,j)是由记录ri,rj(1ijn)构成的二叉查找树，C(i,j)是这棵二叉查找树的平均比较次数。虽然最后的结果是C(1,n)，但遵循动态规划法的求解方法,需要求出所有较小子问题C(i,j)的值，考虑从ri,rj中选择一个记录rk作为二叉查找树的根结点，可以得到如下关系：,因此，得到如下动态规划函数：C(i,i-1)=0(1in+1)（式6.17）C(i,i)=pi(1in)（式6.18）C(i,j)=minC(i,k-1)+C(k+1,j)+(1ijn,ikj)（式6.19）设一个二维表Cn+1n+1，其中Cij表示二叉查找树T(i,j)的平均比较次数。注意到在式6.19中，当k=1时，求Cij需要用到Ci0，当k=n时，求Cij需要用到Cn+1j，所以，二维表Cn+1n+1行下标的范围为1n+1，列下标的范围为0n。为了在求出由r1,r2,rn构成的二叉查找树的平均比较次数的同时得到最优二叉查找树，设一个二维表Rn+1n+1，其下标范围与二维表C相同，Rij表示二叉查找树T(i,j)的根结点的序号。,例如，集合A,B,C,D的查找概率是0.1,0.2,0.4,0.3，二维表C和R的初始情况如图6.13所示。,在二维表C和R中只需计算主对角线以上的元素。首先计算C(1,2)：,在前两个记录构成的最优二叉查找树的根结点的序号是2。,按对角线逐条计算每一个C(i,j)和R(i,j)，得到最终表。,设n个字符的查找概率存储在数组pn中，动态规划法求解最优二叉查找树的算法如下：,for(d=1;dn;d+)/按对角线逐条计算for(i=1;i=n-d;i+)j=i+d;min=;mink=i;sum=0;for(k=i;k=j;k+)sum=sum+pk;if(Cik-1+Ck+1jmin)min=Cik-1+Ck+1j;mink=k;Cij=min+sum;Rij=mink;returnC1n;,6.4.2近似串匹配问题,设样本P=p1p2pm，文本T=t1t2tn，对于一个非负整数K，样本P在文本T中的K-近似匹配（K-approximateMatch）是指P在T中包含至多K个差别的匹配（一般情况下，假设样本是正确的）。这里的差别是指下列三种情况之一：（1）修改：P与T中对应字符不同；（2）删去：T中含有一个未出现在P中的字符；（3）插入：T中不含有出现在P中的一个字符。,样本P和文本T为K-近似匹配包含两层含义：（1）二者的差别数至多为K；（2）差别数是指二者在所有匹配对应方式下的最小编辑错误总数。,证明近似串匹配问题满足最优性原理。如果样本p1p2pm在文本T的某一位置上有最优（差别数最小）的对应关系，则样本P的任意一个子串pipj（1ijm）与文本T的对应关系也必然是最优的。动态规划函数：定义一个代价函数D(i,j)(0im,0jn)表示样本前缀子串p1pi与文本前缀子串t1tj之间的最小差别数，则D(m,n)表示样本P与文本T的最小差别数。根据近似匹配的定义，容易确定代价函数的初始值：（1）D(0,j)=0，因为空样本与文本t1tj有0处差别；（2）D(i,0)=i，因为样本p1pi与空文本t1tj有i处差别。,当样本p1pi与文本t1tj对应时，D(i,j)有四种可能的情况：（1）字符pi与tj相对应且pi=tj，则总差别数为D(i-1,j-1)；（2）字符pi与tj相对应且pitj，则总差别数为D(i-1,j-1)1；（3）字符pi为多余，即字符pi对应于tj后的空格，则总差别数为D(i-1,j)1；（4）字符tj为多余，即字符tj对应于pi后的空格，则总差别数为D(i,j-1)1。,例：已知样本P=happy，K=1，T=Haveahsppyday是一个可能有编辑错误的文本，在T中求1-近似匹配的过程如下：,由于D(5,12)=1且m=5，所以，在t12处找到了差别数为1的近似匹配，此时的对应关系如下：,算法6.6的时间复杂性为O(mn)。,6.5实验项目最大子段和问题,1.实验题目给定由n个整数组成的序列(a1,a2,an)，求该序列形如的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。,2.实验目的（1）深刻掌握动态规划法的设计思想并能熟练运用；（2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。,3.实验要求（1）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法；（2）比较不同算法的时间性能；（3）给出测试数据，写出程序文档。,