《算法设计与分析》第07章v.ppt

《《算法设计与分析》第07章v.ppt》由会员分享，可在线阅读，更多相关《《算法设计与分析》第07章v.ppt（96页珍藏版）》请在三一办公上搜索。

1、,算法设计与分析,DeSign and Analysis of AlgorithmsIn C+,“十一五”国家级规划教材,陈慧南 编著,电子工业出版社,第2部分 算法设计策略,第7章 动态规划法,7.1 一般方法和基本要素7.2 每对结点间的最短路径 7.3 矩阵连乘 7.4 最长公共子序列7.5 最优二叉搜索树 7.6 0/1背包 7.7 流水作业调度,7.1 一般方法和基本要素,多段图问题,例71 多段图G=(V,E)是一个带权有向图，它具有如下特性：图中的结点被划分成k2个互不相交的子集Vi，1ik。其中V1和Vk分别只有一个结点，V1包含源点（source）s，Vk包含汇点（sink）

2、t。对所有边E，多段图要求若uVi，则vVi1，1ik，每条边的权值为c(u,v)。从s到t的路径长度是这条路径上边的权值之和，多段图问题（multistage graph problem）是求从s到t的一条长度最短的路径。,子集Vi,多段图问题的特性,最优子结构特性（s,v2,v3,vk-1,t)与(v2,v3,vk-1,t)定义cost(i,j)，1ikcost(k,t)=0cost(i,j)=min c(j,p)+cost(i+1,p)重叠子问题特性,第i阶段j状态的最短路径,1 k段图的自后向前递推求解,递推关系式cost(5,t)=0cost(4,8)=?，cost(4,9)，cos

3、t(4,10)cost(3,5)=?，cost(3,6)，cost(3,7),课堂练习,用分治法思想求解K段图问题与上述动态规划法进行比较,【程序71】k段图的（从后）向前递推算法templatevoid Graph:FMultiGraph(int k,int*p)/采用程序68的邻接表存储图G。对图按阶段顺序标号float*cost=new floatn;/各节点的最短路径值 int q;int*d=new intn;/各结点开始的最短路径上的下一结点costn-1=0,dn-1=-1;/设置初值,for(int j=n-2;j=0;j-)float min=INFTY;for(ENode*

4、r=aj;r;r=r-nextArc)int v=r-adjVex;if(r-w+costvw+costv;q=v;costj=min;dj=q;p0=0;pk-1=n-1;/p记录最短路径 for(j=1;j=k-2;j+)pj=dpj-1;delete cost;delete d;,2 k段图的自前向后递推求解,递推关系式cost(1,s)=0cost(i,j)=?,动态规划法的实质也是将较大问题分解为较小的同类子问题，这一点上它与分治法和贪心法类似。但动态规划法有自己的特点。分治法的子问题相互独立，相同的子问题被重复计算，动态规划法解决这种子问题重叠现象。贪心法要求针对问题设计最优量度标

5、准，但这在很多情况下并不容易。动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，动态规划则可以处理不具备贪心准则的问题。,7.1.1 一般方法,最优性原理指出，一个最优策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，其余决策对相应的子问题来说，必定构成最优策略。这便是最优决策序列的最优子结构特性。,设计一个动态规划算法，通常可以按以下几个步骤进行：（1）刻画最优解的子结构特性；（2）递归定义最优解值；（3）以自底向上方式计算最优解值；（4）根据计算得到的信息构造一个最优解。其中，第（1）至（3）步是动态规划算法的基本步骤。最优解值是最优解的

6、目标函数的值。,7.1.2 基本要素,一个最优化多步决策问题适合用动态规划法求解有两个要素：最优子结构特性和重叠子问题。,7.1.4 资源分配问题,【例72】将n个资源分配给r个项目，已知如果把j个资源分配给第i个项目，可以收益N(i,j)，0jn，1ir。求总收益最大的资源分配方案。（这里假设，对同一个项目，获得的资源越多，收益越多；不同的项目对资源的单位收益不一样）,V(i,j)表示j个资源已经分配给前i-1个项目N(m,n)表示n个资源分配给第m个项目了,4个资源、3个项目,7.1.4 资源分配问题,向后递推的动态规划算法？,7.1.5 关键路径问题（略）,工程安排最短工期关键路径关键活

7、动在关键路径上的活动注意结点的编号,结点=事件（代表前一个活动结束，后一个活动可开始的状态）,7.1.5 关键路径问题,最优子结构特性？子问题重叠？,7.2 每对结点间的最短路径,单源最短路径问题,单源最短路径问题是：给定带权的有向图G=(V,E)和图中结点sV，求从s到其余各结点的最短路径，其中，s称为源点。,贪心法求解,迪杰斯特拉（Dijkstra）算法解视为向量（L1,L2,L3,Ln-1)，分量Li表示s到结点i的最短路径首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推，直到从源点到其它所有结点之间的最短路径都已求得为止。每步度量准则：当前最短路径（增量最少的分量

8、）以求得最短路径的结点集合记为S,从其他结点找出当前最短的,6.6.3 迪杰斯特拉算法,【程序610】迪杰斯特拉算法templateclass MGraph public:MGraph(int mSize);void Dijkstra(int s,T*,private:int Choose(int*d,bool*s);T*a;/邻接矩阵 int n;,template int MGraph:Choose(int*d,bool*s)/找出在下一条当前最短路径上的尾结点 int i,minpos;T min;min=INFTY;minpos=-1;for(i=1;in;i+)if(dimin,te

9、mplate void MGraph:Dijkstra(int s,T*,inSs=true;ds=0;for(i=1;in-1;i+)/需要n-1步完成 k=Choose(d,inS);inSk=true;for(j=0;jn;j+)/更新各结点的d和path if(!inSj,时间复杂度？,7.2.1 结点对间最短路径问题描述,设G=(V,E)是一个有n个结点的带权有向图，w(i,j)是权函数，每对结点间的最短路径问题是指求图中任意一对结点i和j之间的最短路径。,7.2.2 动态规划法求解,最优子结构设图G=(V,E)是带权有向图，(i,j)是从结点i到结点j的最短路径长度，k是这条路径上

10、的一个结点，(i,k)和(k,j)分别是从i到k和从k到j的最短路径长度，则必有(i,j)=(i,k)+(k,j)。因为若不然，则(i,j)代表的路径就不是最短路径。这表明每对结点之间的最短路径问题的最优解具有最优子结构特性。,定义dkij=i到j的路径上，包含的结点编号不超过k是的最短路径长度,最优解的递推关系,重叠子问题：为了计算dkij时，必须先计算dk1ij、dk1ik和dk1ik，dk1的元素被多个dk的元素的计算共享。,dkij指在i和j之间由编号不大于k的结点组成的最短路径长度。k=-1时表示不包含其他结点,7.2.3弗洛伊德算法,弗洛伊德算法的基本思想是：令k=0,1,n-1，

11、每次考察一个结点k。二维数组d用于保存各条最短路径的长度，其中，dij存放从结点i到结点j的最短路径的长度。在算法的第k步上应作出决策：从i到j的最短路径上是否包含结点k。,【程序72】弗洛伊德算法templatevoid MGraph:Floyd(T*,for(k=0;kn;k+)总共n步完成 for(i=0;in;i+)for(j=0;jn;j+)if(dik+dkj dij)dij=dik+dkj;pathij=pathkj;弗洛伊德算法的时间复杂度也为O(n3),7.2.4 算法正确性,定理71 弗洛伊德算法得到的dij，0i,jn-1是从i到j的最短路径。,结点对间最短路径问题,弗洛

12、伊德算法N次迪杰斯特拉算法,7.3 矩阵连乘,问题描述,给定n个矩阵A0,A1,An1，其中Ai，i=0,n-1的维数为pipi+1，并且Ai与Ai+1是可乘的。考察这n个矩阵的连乘积A0A1An1，由于矩阵乘法满足结合律，所以计算矩阵的连乘可有许多不同的计算次序。矩阵连乘问题是确定计算矩阵连乘积的计算次序，使得按照这一次序计算矩阵连乘积，需要的“数乘”次数最少。,(A0A1)A3)A4),(A0(A1 A3)A4),完全加括号的矩阵连乘积可递归地定义为：单个矩阵是完全加括号的；矩阵连乘积A是完全加括号的，则A可表示为两个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。,A=(M0

13、M1M3Mk),(Mk+1Mk+2Mn-1),A=M0M1M3M4Mn-1,B,C,例74 4个矩阵连乘积ABCD，设它们的维数分别为A:5010，B:1040,C:4030,D:305。,7.3.2 动态规划法求解,最优子结构矩阵连乘AiAi+1Aj简记为Ai:j，ij。于是矩阵连乘A0A1An-1可记作A0:n-1。将这一计算次序在矩阵Ak和Ak+1，0kn-1之间断开，则其相应的完全加括号形式为（A0A1Ak）（Ak+1Ak+2An1）。可先分别计算A0:k和Ak+1:n-1，然后将两个连乘积再相乘得到A0:n-1。,矩阵连乘A0:n-1的最优计算次序的计算量等于A0:k和Ak+1:n-

14、1两者的最优计算次序的计算量之和，再加上A0:k和Ak+1:n-1相乘的计算量。如果两个矩阵子序列的计算次序不是最优的，则原矩阵的计算次序也不可能是最优的。这就是说，矩阵连乘问题的最优解具有最优子结构特性。,最优解的递推关系先定义一个二维数组m，用来保存矩阵连乘时所需的最少计算量。,注意：N个矩阵的维数依序放在一维数组p中，其中Ai的维数记为PiPi+1,求解过程,为避免重复计算，自底向上求解mijmik,k=i,i+1,j-1mk+1j,k=i+1,j-1,矩阵连乘算法,【程序73】矩阵连乘算法class MatrixChainpublic:MatrixChain(int mSize,int

15、*p);int MChain();/基于动态规划法 int LookupChain();/基于备忘录的分治法 void Traceback();/输出最优解,private:void Traceback(int i,int j);int LookupChain(int i,int j);int*p,*m,*s,n;,int MatrixChain:MChain()/求A0:n-1的最优解值 for(int i=0;in;i+)mii=0;/主对角线,for(int r=2;r=n;r+)/和主对角线平行的其他次对角线 for(int i=0;i=n-r;i+)int j=i+r-1;mij=m

16、i+1j+pi*pi+1*pj+1;sij=i;for(int k=i+1;kj;k+)int t=mik+mk+1j+pi*pk+1*pj+1;if(tmij)mij=t;sij=k;return m0n-1;,void MatrixChain:Traceback(int i,int j)if(i=j)coutAi;return;if(isij)cout(;/ai,ai+1,ak加括号Traceback(i,sij);if(isij)cout);if(sij+1j)cout(;/ak+1,ak+2,aj加括号Traceback(sij+1,j);if(sij+1j)cout);void Ma

17、trixChain:Traceback()cout(;Traceback(0,n-1);cout);coutendl;,例75 6个矩阵连乘积A0A1A2A3A4A5，设它们的维数分别为A:3035，B:3515 C:155 D:510，E:1020，F:2025。,备忘录方法,矩阵连乘的备忘录方法 备忘录方法为每个已经计算的子问题建立备忘录，即保存子问题的计算结果以备需要时引用，从而避免了相同子问题的重复求解。,【程序74】矩阵连乘的备忘录方法 int MatrixChain:LookupChain(int i,int j)if(mij0)return mij;/子问题已解。if(i=j)r

18、eturn 0;int u=LookupChain(i+1,j)+pi*pi+1*pj+1;sij=i;for(int k=i+1;kj;k+)int t=LookupChain(i,k)+LookupChain(k+1,j)+pi*pk+1*pj+1;if(tu)u=t;sij=k;mij=u;return u;,int MatrixChain:LookupChain()return LookupChain(0,n-1);,7.5 最优二叉搜索树,问题描述,设有元素集合 a1,a2,an，其中，a1a2an，p(i)是在集合中成功查找ai 的概率，1i n，q(i)是待查元素x值满足 aix

19、ai+1的概率,0i n（假定a0=,an+1=+）。最优二叉搜索树问题是指设法构造一棵具有最小平均搜索时间的二叉搜索树。,二叉搜索树的代价,二叉搜索树平均搜索时间a1,an,E0,Encost(T)=,递推关系,cost(T)=cost(L)+cost(R)+p1+pn+q0+q1+qn,L,R,T,=cost(L)+cost(R)+w(0,n),动态规划法求解,设 c(0,n)是由元素值集合a1,an所构造的最优二叉搜索树的代价，则,一般地，c(i,j),ij 是元素值集合ai+1,aj所构造的最优二叉搜索树的代价，设r(i,j)=k为该树的根，要求结点k满足,例77 设n4且（a1,a2

20、,a3,a4）=(Mon,Thu,Tue,Wed)。又设p(1:4)=(3,3,1,1)和q(0:4)(2,3,1,1,1)。这里p和q都已乘了16。,7.5.3 最优二叉搜索树算法,【程序77】构造最优二叉搜索树int Find(int i,int j,int*r,float*c)/找出I,j之间使代价最小的根 float min=INFTY;int k;for(int m=i+1;m=j;m+)if(cim-1+cmj)min)min=cim-1+cmj;k=m;return k;,void CreateOBST(float*p,float*q,float*c,int*r,float*w,

21、int n)/初始化，主对角线，次主对角线for(int i=0;i=n-1;i+)wii=qi;cii=0.0;rii=0;wii+1=qi+qi+1+pi+1;cii+1=qi+qi+1+pi+1;rii+1=i+1;wnn=qn;cnn=0.0;rnn=0;,for(int m=2;m=n;m+)for(i=0;i=n-m;i+)int j=i+m;wij=wij-1+pj+qj;int k=Find(i,j,r,c);cij=wij+cik-1+ckj;rij=k;,算法复杂度,7.6 0/1背包,问题描述,问题已知一个载重为M的背包和n件物品，物品编号从0到n-1。第i件物品的重量为

22、 wi，如果将第i种物品装入背包将获益pi，这里，wi0，pi0，0in。所谓0/1背包问题是指在物品不能分割，只能整件装入背包或不装入的情况下，求一种最佳装载方案使得总收益最大。,7.6.2 动态规划法求解,最优子结构0/1背包的最优解具有最优子结构特性。设(x0,x1,xn1)，xi0,1是0/1背包的最优解，那么，(x1,x2,xn1)必然是0/1背包子问题的最优解：背包载重Mw0 x0，共有n-1件物品，第i件物品的重量为 wi，效益pi，wi0，pi0，1in。,例78 设有0/1背包问题n=3，（w0,w1,w2）=（2,3,4），（p0,p1,p2）=（1,2,4）和M=6。,递

23、归式,0/1背包算法框架,现用Sj表示函数曲线f(j,X)的全部阶跃点的集合，Sj=(Xi,Pi)|函数曲线f(j,X)的全部阶跃点，-1jn-1，其中S-1=(0,0)。用S1j表示函数曲线f(j-1,X-wj)+pj的全部阶跃点的集合，S1j=(Xj,Pj)|函数曲线f(j-1,X-wj)+pj的全部阶跃点，0jn-1。,计算所有Sj和S1j的步骤如下：S-1=(0,0)，函数f(-1,X)只有一个阶跃点；S1j=(X,P)|(X-wj,P-pj)Sj1，也就是说，由集合Sj-1中的每个阶跃点（X,P），得到集合S1j中的一个阶跃点（X+wj,P+pj）；Sj是合并集合Sj-1S1j，舍弃

24、其中被支配的阶跃点和所有XM的阶跃点得到。,对于例78有S1=(0,0)，S10=(2,1)S0=(0,0),(2,1)，S11=(3,2),(5,3)S1=(0,0),(2,1),(3,2),(5,3)，S12=(4,4),(6,5)，(7,6),(9,7)S2=(0,0),(2,1),(3,2),(4,4),(6,5),【程序79】0/1背包算法的粗略描述void DKP(float*p,float*w,int n,float M,float,(X1,P1)=Sn2中最后一个阶跃点;(X2,P2)=(X+wn1,P+pn1)，其中(X,P)是Sn-1 中 使得 X+wn1M的最大的阶跃点;

25、PmaxP1,P2;If(P2P1)xn1=1;else xn1=0;回溯确定xn2,xn-3,x0;,性能分析,在最坏情况下，算法的空间复杂度是O(2n)。在最坏情况下，算法的时间复杂度是O(2n)。,7.7 流水作业调度,7.7.1 问题描述,假定处理一个作业需要执行若干项不同类型的任务，每一类任务只能在某一台设备上执行。设一条流水线上有n个作业J=J0,J1,Jn1和m台设备P=P1,P2,Pm。每个作业需依次执行m个任务，其中第j个任务只能在第j台设备上执行，1jm。设第i个作业的第j项任务Tji所需时间为tji，1jm，0in。如何将这nm个任务分配给这m台设备，使得这n个作业都能顺

26、利完成。这就是流水线作业调度(flow shop schedule)问题。,例710 设有三台设备两个作业，每个作业包含三项任务。完成这些任务的时间由矩阵M给定。,作业i的完成时间fi(S)是指在调度方案S下，该作业的所有任务都已完成的时间。完成时间F(S)是所有作业都完成的时间。平均流动时间(mean flow time)MFT(S)定义为：,一组给定的作业的最优完成时间是F(S)的最小值。OFT表示指非抢先调度最优完成时间POFT表示抢先调度最优完成时间。OMFT表示非抢先调度最优平均完成时间，POMFT表示抢先调度最优平均完成时间。本节只讨论当m=2时获得OFT的调度方案的算法，这就是双

27、机流水作业调度问题。,双机流水作业调度描述为：设有n个作业的集合0，1，n-1，每个作业都有两项任务要求在2台设备P1和P2组成的流水线上完成加工。每个作业加工的顺序总是先在P1上加工，然后在P2上加工。P1和P2加工作业i所需的时间分别为a i和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在设备P1上开始加工，到最后一个作业在设备P2上加工完成所需的时间最少。即求使F(S)有最小值的调度方案S。,动态规划法求解,重要结论（可证明）：在两台设备的情况下，存在一个最优非抢先调度方案，使得在P1和P2上的作业完全以相同次序处理（若m2则不然）。,定理73 流水作业调度问

28、题具有最优子结构的性质。=(0),(1),(k-1)g(S,t)递推关系：g(N,0)=minai+g(N-i,bi;N=0,1,N-1,i属于N.对任意的集合S和I(i属于S）：g(S,t)=ai+g(S-i,t),t=bi+maxt-ai,0,如果在调度方案的作业排列中，作业i和j满足minbi,ajminbj,ai，则称作业i和j满足Johnson不等式。最优调度方案中，只要有作业i先于j处理，必然有：minbi,aj=min bj,ai即满足Johnson不等式,最优调度求解方案,可以设计下列作业排列方法。这样做能得到最优调度方案(1)如果mina0,a1,an1,b0,b1,bn1是

29、ai，则ai应是最优排列的第一个作业；(2)如果mina0,a1,an-1,b0,b1,bn1是bj，则bj应是最优排列的最后一个作业；(3)继续（1）和（2）的做法，直到完成所有作业的排列。,例711设n4，（a0,a1,a2,a3）=(3,4,8,10)（b0,b1,b2,b3）=(6,2,9,15)。设=(0),(1),(2),(3)是最优作业排列。先将任务按处理时间的非减次序排列成：（b1,a0,a1,b0,a2,b2,a3,b3）=(2,3,4,6,8,9,10,15)先选 b1，将其加在最优作业排列的最后，故(3)=1再选a0，应加在最优作业排列的最前面，故(0)=0考察a1和b0

30、，因作业1和0已调度，接着考察a2，应有(1)=2，再考察b2和a3，令(2)=3。所以最优解为：(0),(1),(2),(3)（0,2,3,1）。,7.7.3 Johnson算法,Johnson算法具体描述如下：设ai和bi，0in分别为作业i在两台设备上的处理时间。建立由三元组（作业号,处理时间,设备号）组成的三元组表d。对三元组表按处理时间排序，得到排序后的三元组表d。对三元组表的每一项di，0in，从左和右两端生成最优作业排列cj,0jn，cj是作业号。如果di的设备号为1，则按从左向右顺序将作业i置于c的左端第一个空位，否则按从右向左的顺序置于c的右端第一个空位。,【程序712】Jo

31、hnson算法/三元组结构struct Triplet int operator(Triplet b)const return tb.t;int jobNo,t,ab;,void FlowShop(int n,int*a,int*b,int*c)Triplet dmSize=0,0,0;for(int i=0;in;i+)if(aibi)di.jobNo=i;di.ab=0;di.t=ai;else di.jobNo=i;di.ab=1;di.t=bi;Sort(d,n);/n个元素排序，O(nlogn)int left=0,right=n-1;/指示左右两端首个空位for(i=0;in;i+)if(di.ab=0)cleft+=di.jobNo;else cright-=di.jobNo;,Johnson算法的时间取决于对作业集合的排序，因此，在最坏情况下算法的时间复杂度为O(nlogn)，所需的空间复杂度为O(n)。,（a0,a1,a2,a3）=(3,4,8,10)（b0,b1,b2,b3）=(6,2,9,15)。,动态规划法 小结,求最优化问题最优子结构原理递推关系分析子问题的重叠性自底向上计算（最优解值）构造最优解与分治法、贪心法比较备忘录方法,