计算机学院动态规划教学课件PPT.ppt

第3讲 动态规划,王 静河南理工大学计算机学院2013年3月,第3讲 动态规划,一、算法总体思想二、算法基本要素三、算法范例分析,第3讲 动态规划,动态规划算法与分治法类似，其基本思想也 是将待求解问题分解成若干个子问题。,一、算法总体思想,第3讲 动态规划,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。,第3讲 动态规划,如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,T(n),第3讲 动态规划,动态规划通常应用于最优化问题，即要做出一组选择以达到一个最优解。在做选择的同时，经常出现同样形式的问题。当某一特定的子问题可能出自于多于一种选择的集合时，动态规划是很有效的；关键技术是存储这些子问题每一个的解，以备它重复出现。,第3讲 动态规划,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。,第3讲 动态规划,矩阵连乘问题,给定n个矩阵，其中 与 是可乘的，。考察这n个矩阵的连乘积 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。,第3讲 动态规划,矩阵连乘问题 给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。,第3讲 动态规划,16000,10500,36000,87500,34500,完全加括号的矩阵连乘积可递归地定义为：设有四个矩阵，它们的维数分别是：总共有五中完全加括号的方式,（1）单个矩阵是完全加括号的；（2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即,第3讲 动态规划,穷举法列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：,第3讲 动态规划,动态规划方法,将矩阵连乘积 简记为Ai:j，这里ij,考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为,计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量,第3讲 动态规划,特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。,（1）分析最优解的结构,第3讲 动态规划,（2）建立递归关系,设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n 当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,n当ij时，可以递归地定义mi,j为：,的位置只有 种可能,这里 的维数为,第3讲 动态规划,（3）计算最优值,对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。,第3讲 动态规划,matrixChain(int n,int pn+1,int mn+1n+1,int sn+1n+1)for(int i=1;i=n;i+)mii=0;/填主对角线d1 for(int r=2;r=n;r+)/填次对角线dr(r=2n)for(int i=1;i=n-r+1;i+)/填次对角线的各个元素 int j=i+r-1;/计算次对角线d r 上第i行的元素的列标 mij=mi+1j+pi-1*pi*pj;/用计算Ai(Ai+1Aj)的次数作为mij的初始值 sij=i;/保存分界点 for(int k=i+1;k j;k+)/用mik和mk+1j计算mij的新值 int t=mik+mk+1j+pi-1*pk*pj;if(t mij)mij=t;sij=k;,算法复杂度分析：算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。,第3讲 动态规划,例：计算如下几个矩阵连乘积。,第3讲 动态规划,#include stdafx.h#include void MatrixChain(int*p,int n,int m6,int s6);void Traceback(int i,int j,int s6);int main(int argc,char*argv)int n=6;int m66;int s66;int p7;for(int i=0;ipi;for(int ii=0;ii=n;ii+)coutpii;coutendlendlendl;MatrixChain(p,n,m,s);/coutnendl;Traceback(1,6,s);return 0;,void MatrixChain(int*p,int n,int m6,int s6)for(int i=1;i=n;i+)mii=0;sii=0;for(int r=2;r=n;r+)for(int i=1;i=n-r+1;i+)int j=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(int k=i+1;k j;k+)int t=mik+mk+1j+pi-1*pk*pj;if(t mij)mij=t;sij=k;for(int ii=1;ii=n;ii+)for(int jj=ii;jj=n;jj+)cout.width(10);coutmiijj;coutendl;coutendlendl;for(int iii=1;iii=n;iii+)for(int jjj=iii;jjj=n;jjj+)cout.width(10);coutsiiijjj;coutendl;coutendlendl;void Traceback(int i,int j,int s6)if(i=j)return;Traceback(i,sij,s);Traceback(sij+1,j,s);coutMultiply Ai,sij;coutand Asij+1,jendl;,第3讲 动态规划,课堂练习1.找零钱问题：设有n种不同面值的硬币，各硬币的面值存于数组T1:n中。现要用这些面值的硬币来找钱，可以实用的各种面值的硬币个数不限，使找零钱时给出最少硬币的枚数。当只用硬币面值T1,T2,Ti时，可找出钱数j的最少硬币个数记为C(i,j)。若只用这些硬币面值，找不出钱数j时，记C(i,j)=。设计一个动态规划算法，对1jL，计算出所有的C(n,j)。算法中只允许实用一个长度为L的数组。用L和n作为变量来表示算法的计算时间复杂性。,第3讲 动态规划,算法设计思想：假设这一堆面值分别为 1、2、5、21、25 元，需要找出总值 T 为 63 元的零钱。很明显，只要拿出 3 个 21 元的硬币就凑够了 63 元了。基于上述动态规划的思想，我们可以从 1 元开始计算出最少需要几个硬币，然后再求 2 元、3元每一次求得的结果都保存在一个数组中，以后需要用到时则直接取出即可。那么我们什么时候需要这些子问题的解呢？如何体现出由子问题的解得到较大问题的解呢？其实，在我们从 1 元开始依次找零时，可以尝试一下当前要找零的面值（这里指 1元）是否能够被分解成另一个已求解的面值的找零需要的硬币个数再加上这一堆硬币中的某个面值之和，如果这样分解之后最终的硬币数是最少的，那么问题就得到答案了。,第3讲 动态规划,算法设计思想：递归计算：假设对于i=1.N-1，所需最少的硬币数Count(i)已知，那么对于N，所需的硬币数为Min(Count(i)+Count(N-i),i=1.N-1；但是，递归过程中，每次计算Count(i)，都会重复计算 Count(1).Count(i-1);这样时间复杂度就是O(N2);动态规划：可以从1开始记录下每个钱数所需的硬币枚数，避免重复计算，为了能够输出硬币序列，我们还需要记录下每次新加入的硬币。当只用面值为T1,T2,Tn来找出钱j时，所用的硬币的最小个数记为C(i,j),则C(i,j)的递推方程为：C(i,j)=min(C(i-1,j)+1)，0=i=n,第3讲 动态规划,publicclassCoinsChange/*硬币找零：动态规划算法*paramvalues:保存每一种硬币的币值的数组*paramvalueKinds:币值不同的硬币种类数量，即coinValue数组的大小*parammoney:需要找零的面值*paramcoinsUsed:保存面值为i的纸币找零所需的最小硬币数*/publicstaticvoidmakeChange(intvalues,intvalueKinds,intmoney,intcoinsUsed)coinsUsed0=0;/对每一分钱都找零，即保存子问题的解以备用，即填表 for(intcents=1;cents=money;cents+)/当用最小币值的硬币找零时，所需硬币数量最多 intminCoins=cents;/遍历每一种面值的硬币，看是否可作为找零的其中之一 for(intkind=0;kindvalueKinds;kind+)/若当前面值的硬币小于当前的cents则分解问题并查表 if(valueskind=cents)inttemp=coinsUsedcents-valueskind+1;if(tempminCoins)minCoins=temp;/保存最小硬币数 coinsUsedcents=minCoins;System.out.println(面值为+(cents)+的最小硬币数:+coinsUsedcents);publicstaticvoidmain(Stringargs)/硬币面值预先已经按降序排列 intcoinValue=newint25,21,10,5,1;/需要找零的面值 intmoney=63;/保存每一个面值找零所需的最小硬币数，0号单元舍弃不用，所以要多加1 intcoinsUsed=newintmoney+1;makeChange(coinValue,coinValue.length,money,coinsUsed);,测试结果：面值为 1 的最小硬币数:1 面值为 2 的最小硬币数:2 面值为 3 的最小硬币数:3 面值为 4 的最小硬币数:4 面值为 5 的最小硬币数:1 面值为 6 的最小硬币数:2.面值为 60 的最小硬币数:3 面值为 61 的最小硬币数:4 面值为 62 的最小硬币数:4 面值为 63 的最小硬币数:3,第3讲 动态规划,课堂练习2.砝码称重问题：设有1g，2g，3g，5g，10g，20g的砝码各若干枚(其总重1000g)，要求：输入：a1 a2 a3 a4 a5 a6(表示1g砝码有a1个，2g砝码有a2个，.20g砝码有a6个)输出：Total=N(N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况)输入样例：1 1 0 0 0 0 输出样例：Total=3，表示可以称出1g，2g，3g三种不同的重量,第3讲 动态规划,算法设计思路：1.从砝码1开始分析，假设前i个砝码能称出的不同重量为Qi,那么Qi一定是这样计算出来的：在Qi-1的基础上，对Qi-1个不同的重量，分别添加k个砝码i，再添加的过程中除去重复情况。2.假设：wN表示N个不同重量的砝码(例子中N=6)，w0N-1。cN表示N个不同砝码相应的数量，c1N。则：Qi=(Qi-1+k*wi)-添加过程中重复的个数。其中0=k=ci。3.定义一个辅助布尔型数组visitM+1,这里的M是例子中的1000，表示最大重量不超过M。4.visitj=1表示，重量为j的情况已经存在，否则表示重量为j的情况还未出现。其中visit0作为一个多余空间存在，可以作为一个临时变量。最后遍历visit1M，统计1的个数就得到不同重量的个数，通过这个辅助数组，就可以除去重复情况。,第3讲 动态规划,1#include 2 using namespace std;3#define N 6 4#define M 1000 5 int wN=1,2,3,5,10,20;6 int cN=0;7 int visitM+1=0;9 int weight_count()10 int i=0;12 int j=0;13 int total=0;14 int count=0;16 visit0=w0*c0;/visit0用于每添加一个砝码时遍历的结束位置 17 for(i=1;iM)27 break;28 if(visitj=1,第3讲 动态规划,二、算法基本要素,最 优 子 结 构,重 叠 子 问 题,第3讲 动态规划,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。,同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）,（1）最优子结构,第3讲 动态规划,二、重叠子问题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,第3讲 动态规划,recurMatrixChain(int i,int j)if(i=j)return 0;int u=recurMatrixChain(i+1,j)+pi-1*pi*pj;/用计算Ai(Ai+1Aj)的次数作为mij的初始值 sij=i;/保存分界点 for(int k=i+1;k j;k+)/用mik和mk+1j计算mij的新值 int t=recurMatrixChain(i,k)+recurMatrixChain(k+1,j)+pi-1*pk*pj;if(t u)u=t;sij=k;return u;,递归方式直接计算Ai,j的算法recurMatrixChain,第3讲 动态规划,第3讲 动态规划,动态规划的变形：备忘录方法,备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。,第3讲 动态规划,memorizedMatrixChain(int n)for(int i=1;i 0)return mij;if(i=j)return 0;int u=lookupChain(i+1,j)+pi-1*pi*pj;sij=i;for(int k=i+1;k j;k+)int t=lookupChain(i,k)+lookupChain(k+1,j)+pi-1*pk*pj;if(t u)u=t;sij=k;mij=u;return u;,第3讲 动态规划,例1：最长公共子序列,若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。,第3讲 动态规划,问题描述为：给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。例如：X=A,B,C,B,D,A,B,Y=B,D,C,A,B,A 则序列B,C,A是X和Y的一个公共子序列。但它不是X和Y的一个最长公共子序列。序列B,C,B,A是X和Y的一个公共子序列，它的长度是4，而且它是X和Y的一个最长公共子序列。因为，X和Y没有长度大于4的公共子序列。它的另一个解是B,C,A,B。该问题的答案不唯一。,第3讲 动态规划,(1)最长公共子序列的结构,设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk，则(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的最长公共子序列。,由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。,第3讲 动态规划,(2)子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列Xi和Yj的最长公共子序列的长度。其中，Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下：,第3讲 动态规划,(3)计算最优值,由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。,第3讲 动态规划,lcsLength(int m,int n,char x,char y)int cmn,bmn;for(int i=1;i=cij-1)cij=ci-1j;bij=2;/竖直向下填写 else cij=cij-1;bij=3;/水平向右填写 return cmn;,第3讲 动态规划,(4)构造最长公共子序列,void LCS(int i，int j，char*x，int*b)if(i=0|j=0)return;if(bij=1)LCS(i-1，j-1，x，b);coutxi;else if(bij=2)LCS(i-1，j，x，b);else LCS(i，j-1，x，b);,第3讲 动态规划,例如 设所给的2个序列为X=A,B,C,B,D,A,B和Y=B,D,C,A,B,A,LCS：另一个解B,C,A,B,第3讲 动态规划,#include stdafx.h#include void LCSLength(int m,int n,char*x,char*y,int c7,int b7);void LCS(int i,int j,char*x,int b7);int main(int argc,char*argv)int m=7;int n=6;char x8=,A,B,C,B,D,A,B;char y7=,B,D,C,A,B,A;/coutx0endly0endl;int c87;int b87;LCSLength(m,n,x,y,c,b);cout序列x为：endl;for(int i=1;i=m;i+)coutxi;coutendl;cout序列y为：endl;for(int j=1;j=n;j+)coutyj;coutendl;cout序列x和y的最长公共子序列为：endl;LCS(7,6,x,b);coutendl;cout矩阵c为：endl;for(int ii=0;ii=m;ii+)for(int jj=0;jj=n;jj+)cout.width(2);coutciijj;coutendl;cout矩阵b为：endl;for(int iii=0;iii=m;iii+)for(int jjj=0;jjj=n;jjj+)cout.width(2);coutbiiijjj;coutendl;return 0;,void LCSLength(int m,int n,char*x,char*y,int c7,int b7)int i,j;for(i=0;i=cij-1)cij=ci-1j;bij=2;else cij=cij-1;bij=3;void LCS(int i,int j,char*x,int b7)if(i=0|j=0)return;if(bij=1)LCS(i-1,j-1,x,b);coutxi;else if(bij=2)LCS(i-1,j,x,b);else LCS(i,j-1,x,b);,第3讲 动态规划,(4)算法的改进,在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素cij的值仅由ci-1j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素cij，可以不借助于数组b而仅借助于c本身确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算cij时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n)。,第3讲 动态规划,例2：凸多边形最优三角剖分,用多边形顶点的逆时针序列表示凸多边形，即P=v0,v1,vn-1表示具有n条边的凸多边形。若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形vi,vi+1,vj和vj,vj+1,vi。多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。,第3讲 动态规划,给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。,第3讲 动态规划,(1)三角剖分的结构及其相关问题,一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积(A1(A2A3)(A4(A5A6)所相应的语法树如图(a)所示。凸多边形v0,v1,vn-1的三角剖分也可以用语法树表示。例如，图(b)中凸多边形的三角剖分可用图(a)所示的语法树表示。,第3讲 动态规划,矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，ij，对应于矩阵连乘积Ai+1:j。,第3讲 动态规划,(2)最优子结构性质,凸多边形的最优三角剖分问题有最优子结构性质。事实上，若凸(n+1)边形P=v0,v1,vn-1的最优三角剖分T包含三角形v0vkvn，1kn-1，则T的权为3个部分权的和：三角形v0vkvn的权，子多边形v0,v1,vk和vk,vk+1,vn的权之和。可以断言，由T所确定的这2个子多边形的三角剖分也是最优的。因为若有v0,v1,vk或vk,vk+1,vn的更小权的三角剖分将导致T不是最优三角剖分的矛盾。,第3讲 动态规划,(3)最优三角剖分的递归结构,定义tij，1ijn为凸子多边形vi-1,vi,vj的最优三角剖分所对应的权函数值，即其最优值。为方便起见，设退化的多边形vi-1,vi具有权值0。据此定义，要计算的凸(n+1)边形P的最优权值为t1n。tij的值可以利用最优子结构性质递归地计算。当j-i1时，凸子多边形至少有3个顶点。由最优子结构性质，tij的值应为tik的值加上tk+1j的值，再加上三角形vi-1vkvj的权值，其中ikj-1。由于在计算时还不知道k的确切位置，而k的所有可能位置只有j-i个，因此可以在这j-i个位置中选出使tij值达到最小的位置。由此，tij可递归地定义为：,第3讲 动态规划,minWeighuTriangulation(int n,int tnn,int snn)for(int i=1;i=n;i+)tii=0;/填主对角线d1 for(int r=2;r=n;r+)/填次对角线d2dn for(int i=1;i=n-r+1;i+)/填次对角线的各个元素 int j=i+r-1;tij=ti+1j+w(i-1,i,j);/计算tij的初始值 sij=i;/保存与vi-1和vj构成三角形的第3个顶点的下标 for(int k=i+1;k j;k+)/计算tij的新值 int u=tik+tk+1j+w(i-1,k,j);if(u tij)tij=u;sij=k;/更新与vi-1和vj构成三角形的第3个顶点的下标,(4)计算最优值,第3讲 动态规划,例3：多边形游戏,多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。游戏第1步，将一条边删除。随后n-1步按以下方式操作：(1)选择一条边E以及由E连接着的2个顶点V1和V2；(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。问题:对于给定的多边形，计算最高得分。,第3讲 动态规划,例：某个四边形中，设-7为1号顶点，4为2号顶点，2为3号顶点，5为4号顶点。按游戏规则，该四边形的游戏结果为：得分最高是33。首次被删去的边为1号边和2号边。,第3讲 动态规划,第3讲 动态规划,第3讲 动态规划,第3讲 动态规划,(1)最优子结构性质,在所给多边形中，从顶点i(1in)开始，长度为j(链中有j个顶点)的顺时针链p(i，j)可表示为vi，opi+1，vi+j-1。如果这条链的最后一次合并运算在opi+s处发生(1sj-1)，则可在opi+s处将链分割为2个子链p(i，s)和p(i+s，j-s)。设m1是对子链p(i，s)的任意一种合并方式得到的值，而a和b分别是在所有可能的合并中得到的最小值和最大值。m2是p(i+s，j-s)的任意一种合并方式得到的值，而c和d分别是在所有可能的合并中得到的最小值和最大值。依此定义有am1b，cm2d(1)当opi+s=+时，显然有a+cmb+d(2)当opi+s=*时，有minac，ad，bc，bdmmaxac，ad，bc，bd 换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。,第3讲 动态规划,(2)构造递归函数,由前面的分析可知，为了求链合并的最大值，必须同时求子链合并的最大值和最小值。因此，在整个计算过程中，应同时计算最大值和最小值。设mij0 是链p(i,j)合并的最小值，而mij1是最大值。若最优合并在 opi+s 处将p(i,j)分为2个长度小于j的子链 p(i,s)和 p(i+s,j-s)，且从顶点i开始的长度小于j的子链的最大值和最小值均已计算出。为叙述方便，记 a=mis0,b=mis1,c=i+sj-s0,d=i+sj-s1,第3讲 动态规划,(1)当opi+s=+时，mij0=a+c mij1=b+d(2)当opi+s=*时，mij0=minac,ad,bc,bd mij1=maxac,ad,bc,bd综合（1）和（2），将 p(i,j)在opi+s出断开的最大值记为maxf(i,j,s)，最小值记为minf(i,j,s)，则minf(I,j,s)有两种可能：opi+s=+时，a+c opi+s=*时，minac,ad,bc,bdmaxf(I,j,s)有两种可能：opi+s=+时,b+d opi+s=*时，maxac,ad,bc,bd,第3讲 动态规划,由于最优断开位置s有1n时，顶点i+s实际编号为（i+s）mod n。按上述递推式计算出的min1即为游戏首次删去第i条边后得到的最大得分。,第3讲 动态规划,(3)算法描述,minWeighuTriangulation(int n,int tnn,int snn)for(int i=1;i=n;i+)tii=0;/填主对角线d1 for(int r=2;r=n;r+)/填次对角线d2dn for(int i=1;i=n-r+1;i+)/填次对角线的各个元素 int j=i+r-1;tij=ti+1j+w(i-1,i,j);/计算tij的初始值 sij=i;/保存与vi-1和vj构成三角形的第3个顶点的下标 for(int k=i+1;k j;k+)/计算tij的新值 int u=tik+tk+1j+w(i-1,k,j);if(u tij)tij=u;sij=k;/更新与vi-1和vj构成三角形的第3个顶点的下标,第3讲 动态规划,int polyMax()/计算minminf(i,j,s)和maxmaxf(i,j,s)for(int j=2;jminf)mij0=minf;if(mij1maxf)mij1=maxf;int temp=m1n1;/删除第1条边后得到的最高分 for(int i=2;i=n;i+)/计算maxmaxf(i,j,s)if(tempmin1)temp=min1;/min1是删除第i条边后得到的最高分 return temp;,第3讲 动态规划,例4：图像压缩,图象的变位压缩存储格式将所给的象素点序列：p1,p2,pn,0pi255 分割成m个连续段S1,S2,Sm。第i个象素段Si中(1im)，有li个象素,且该段中每个象素都只用bi位表示。设 则第i个象素段Si为：设，则hibi8。因此需要用3位表示bi,如果限制1li255，则需要用8位表示li。因此，第i个象素段所需的存储空间为li*bi+11位。按此格式存储象素序列p1,p2,pn，需要 位的存储空间。,第3讲 动态规划,图象压缩问题要求确定象素序列p1,p2,pn的最优分段，使得依此分段所需的存储空间最少。每个分段的长度不超过256位。,第3讲 动态规划,（1）最优子结构及建立递归方程设li，bi，是p1,p2,pn的最优分段。显而易见，l1，b1是p1,pl1的最优分段，且li，bi，是pl1+1,pn的最优分段。即图象压缩问题满足最优子结构性质。设si，1in，是象素序列p1,pn的最优分段所需的存储位数。由最优子结构性质易知：其中,算法复杂度分析：由于算法compress中对k的循环次数不超这256，故对每一个确定的i，可在时间O(1)内完成的计算。因此整个算法所需的计算时间为O(n)。,第3讲 动态规划,（2）构造最优解,#define lmax 256#define header 11compress(int n,int p,int s,int l,int b)s0=0;for(int i=1;isi-j+j*bmax)si=si-j+j*bmax;li=j;/计算si-11 si+=header;/计算si,第3讲 动态规划,output(int s,int l,int b)int n=length(s)-1;/s的最大下标 printf(“the optimal value is%dn”,sn);int m=0;/给m赋初值 traceback(n,s,l);/将各最优分段的位数移位 sm=n;/将最后一个最优分段的位数移位 printf(“decomposed into%d”,m,”segmentsn”);for(int j=1;j=m;j+)将各段段长和象素位数移位 lj=lsj;bj=bsj;for(int j=1;j=m;j+)printf(“%d”,lj,”+”,”%dn”,bj);,第3讲 动态规划,例5:电路布线,在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导线(i,(i)将上端接线柱与下端接线柱相连，如图所示。其中(i)是1,2,n的一个排列。导线(i,(i)称为该电路板上的第i条连线。对于任何1i(j)。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets=(i,(i),1in的最大不相交子集。,第3讲 动态规划,记。N(i,j)的最大不相交子集为MNS(i,j)。Size(i,j)=|MNS(i,j)|。(1)当i=1时，(2)当i1时，2.1 j(i)。此时，。故在这种情况下，N(i,j)=N(i-1,j)，从而Size(i,j)=Size(i-1,j)。2.2 j(i)，(i,(i)MNS(i,j)。则对任意(t,(t)MNS(i,j)有ti且(t)(i)。在这种情况下MNS(i,j)-(i,(i)是N(i-1,(i)-1)的最大不相交子集。2.3 若，则对任意(t,(t)MNS(i,j)有 ti。从而。因此，Size(i,j)Size(i-1,j)。另一方面，故又有Size(i,j)Size(i-1,j)，从而Size(i,j)=Size(i-1,j)。,(1)当i=1时(2)当i1时,（1）最优子结构及建立递归方程,第3讲 动态规划,（2）计算最优值的程序,mnset(int c,int size)/c存放(i)的值，size存放Size(i,j)的值 int n=length(c)-1;/c的大小为11,c0冗余 for(int j=0;jc1;j+)size1j=0;for(int j=c1;j=n;j+)size1j=1;for(int i=2;in;i+)for(int j=0;jci;j+)sizeij=sizei-1j;for(int j=ci;j=n;j+)sizeij=max(sizei-1j,sizei-1ci-1+1);return(sizenn=max(sizen-1n,sizen-1cn-1+1);,第3讲 动态规划,traceback(int c,int size,int net)/net存放MNS(n,n)中的各条连线的第1元素 int n=length(c)-1;int j=n;/MNS(n,n)中各条连线的第2元素的前驱 int m=0;/MNS(n,n)中连线的个数 for(int i=n;i1;i-)if(sizeij!=sizei-1j)netm+=i;j=ci-1;return m;,第3讲 动态规划,70,例.求解布线问题,解：,for(int j=0;jc1;j+)size1j=0;,0,0,0,0,0,0,0,0,for(int j=c1;j=n;j+)size1j=1;,1,1,for(int i=2;in;i+)for(int j=0;jci;j+)sizeij=sizei-1j;,0,0,0,0,0,0,0,for(int j=ci;j=n;j+)sizeij=max(sizei-1j,sizei-1ci-1+1);,1,1,1,0,0,0,0,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,0,0,1,1,1,2,2,2,2,2,0,1,1,1,1,2,2,2,2,2,0,1,1,1,1,2,2,2,2,3,0,1,1,2,2,2,2,2,2,3,0,1,2,2,2,2,2,2,2,3,1,1,1,1,2,2,3,3,4,第3讲 动态规划,例6：流水作业调度,n个作业1，2，n要在