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

1、,7.1 一般方法和基本要素 7.2 每对结点间的最短路径 7.3 矩阵连乘 7.4 最长公共子序列 7.5 最优二叉搜索树 7.6 0/1背包 7.7 流水作业调度,第7章 动态规划法,动态规划法的实质也是将较大问题分解为较小的同类子问题，这一点上它与分治法和贪心法类似。但动态规划法有自己的特点。分治法的子问题相互独立，相同的子问题被重复计算，动态规划法解决这种子问题重叠现象。贪心法要求针对问题设计最优量度标准，但这在很多情况下并不容易。动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，动态规划则可以处理不具备贪心准则的问题。,7.1 一般方法和基本要素,7.1.

2、1 一般方法,最优性原理指出，一个最优策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，其余决策必定构成最优策略。这便是最优决策序列的最优子结构特性。,设计一个动态规划算法，通常可以按以下几个步骤进行： （1）刻画最优解的结构特性； （2）递归定义最优解值； （3）以自底向上方式计算最优解值； （4）根据计算得到的信息构造一个最优解。 其中，第（1）至（3）步是动态规划算法的基本步骤。最优解值是最优解的目标函数的值。,7.1.2 基本要素,一个最优化多步决策问题适合用动态规划法求解有两个要素：最优子结构特性和重叠子问题。,7.1.3 多段图问题,例71 多段图G=(V,

3、E)是一个带权有向图，它具有如下特性：图中的结点被划分成k2个互不相交的子集Vi，1ik。其中V1和Vk分别只有一个结点，V1包含源点（source）s，Vk包含汇点（sink）t。对所有边E，多段图要求若uVi，则vVi1，1ik，每条边的权值为c(u,v)。从s到t的路径长度是这条路径上边的权值之和，多段图问题（multistage graph problem）是求从s到t的一条长度最短的路径。,【程序71】多段图的向前递推算法 template void Graph:FMultiGraph(int k,int *p) /采用程序68的邻接表存储图G。 float *cost=new fl

4、oatn; int q,*d=new intn; costn-1=0,dn-1=-1;,for (int j=n-2;j=0;j-) float min=INFTY; for (ENode *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; for(j=1;j=k-2;j+) pj=dpj-1; delete cost;delete d; ,7.1.4 资源分配问题,【例72】 将n个资源分配给r个项目，已知如果把j个资源分配给第i个项目，可以收益N(i,j)

5、，0jn，1ir。求总收益最大的资源分配方案。,7.2.1 问题描述,设G=(V,E)是一个有n个结点的带权有向图，w(i,j)是权函数， 每对结点间的最短路径问题是指求图中任意一对结点i和j之间的最短路径。,7.2 每对结点间的最短路径,7.2.2 动态规划法求解,最优子结构 设图G=(V,E)是带权有向图，(i,j)是从结点i到结点j的最短路径长度，k是这条路径上的一个结点，(i,k) 和(k,j)分别是从i到k和从k到j的最短路径长度，则必有(i,j)= (i,k)+(k,j)。因为若不然，则(i,j)代表的路径就不是最短路径。这表明每对结点之间的最短路径问题的最优解具有最优子结构特性。

6、,最优解的递推关系,重叠子问题：为了计算dkij时，必须先计算 dk1ij、dk1ik和dk1ik，dk1的元素被多个dk的元素的计算共享。,7.2.3弗洛伊德算法,弗洛伊德算法的基本思想是：令k=0,1,n-1，每次考察一个结点k。二维数组d用于保存各条最短路径的长度，其中，dij存放从结点i到结点j的最短路径的长度。在算法的第k步上应作出决策：从i到j的最短路径上是否包含结点k。,【程序72】弗洛伊德算法 template void MGraph:Floyd(T* ,for (k=0;kn;k+) for (i=0;in;i+) for (j=0;jn;j+) if (dik+dkj di

7、j ) dij=dik+dkj; pathij=pathkj; 弗洛伊德算法的时间复杂度为O(n3),7.2.4 算法正确性,定理71 弗洛伊德算法得到的dij，0i,jn-1是从i到j的最短路径。,7.3.1 问题描述,给定n个矩阵A0,A1,An1， 其中Ai，i=0,n-1的维数为pipi+1，并且Ai与Ai+1是可乘的。考察这n个矩阵的连乘积A0A1An1，由于矩阵乘法满足结合律，所以计算矩阵的连乘可有许多不同的计算次序。矩阵连乘问题是确定计算矩阵连乘积的计算次序，使得按照这一次序计算矩阵连乘积，需要的“数乘”次数最少。,7.3 矩阵连乘,完全加括号的矩阵连乘积可递归地定义为： 单个矩

8、阵是完全加括号的； 矩阵连乘积A是完全加括号的，则A可表示为两个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。,例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的

9、最优计算次序的计算量等于A0:k和Ak+1:n-1两者的最优计算次序的计算量之和，再加上A0:k和Ak+1:n-1相乘的计算量。如果两个矩阵子序列的计算次序不是最优的，则原矩阵的计算次序也不可能是最优的。这就是说，矩阵连乘问题的最优解具有最优子结构特性。,最优解的递推关系 先定义一个二维数组m，用来保存矩阵连乘时所需的最少计算量。,7.3.3矩阵连乘算法,【程序73】矩阵连乘算法 class MatrixChain public: MatrixChain(int mSize,int *q); int MChain(); int LookupChain(); void Traceback();

10、,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=mi+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 (

11、tmij) mij=t;sij=k; return m0n-1; ,void MatrixChain:Traceback(int i,int j) if(i=j) coutAi;return; if (isij) cout(; Traceback(i,sij);if (isij)cout); if(sij+1j)cout(; Traceback(sij+1,j);if(sij+1j) cout); void MatrixChain:Traceback() cout(; Traceback(0,n-1);cout); coutendl; ,例75 6个矩阵连乘积A0A1A2A3A4A5，设它们的

12、维数分别为A:3035，B:3515 C:155 D:510，E:1020，F:2025。,7.3.4 备忘录方法,矩阵连乘的备忘录方法 备忘录方法为每个已经计算的子问题建立备忘录，即保存子问题的计算结果以备需要时引用，从而避免了相同子问题的重复求解。,【程序74】矩阵连乘的备忘录方法 int MatrixChain:LookupChain(int i, int j) if (mij0) return mij; if(i=j) return 0; int u=LookupChain(i+1,j)+pi*pi+1*pj+1; sij=i; for (int k=i+1;kj; k+) int t

13、=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 最优二叉搜索树,7.5.1 问题描述,设有元素集合 a1,a2,an，其中，a1a2an，p(i) 是在集合中成功查找ai 的概率，1i n，q(i)是待查元素x值满足 aixai+1的概率,0i n（假定a0= , an+1=+）。 最优二叉搜索树问题是指设法构造一棵具有最小平均搜索时间的二叉

14、搜索树。,7.5 最优二叉搜索树,7.5.2动态规划法求解,设 c(0,n) 是由元素值集合a1,an所构造的最优二叉搜索树的代价，则,一般地，c(i,j) ,ij 是元素值集合ai+1,aj所构造的最优二叉搜索树的代价，设r(i,j)=k为该树的根，要求结点k满足,例77 设n4且（a1,a2,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) float m

15、in=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,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

16、=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.1 问题描述,问题 已知一个载重为M的背包和n件物品，物品编号从0到n-1。第i件物品的重量为 wi，如果将第i种物品装入背包将获益pi，这里，wi0，pi0，0in。所谓0/1背包问题是指在物品不能分割，只能整件装入背包或不装入的情况下，求一种最佳装载方案使得总收益最大。,7.6 0/1背包,7.6.2 动态规划法求解,最优子结构 0/1背包的最优解具有最优子结构特性。设 (x0, x1,

17、 , 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。,递归式,7.6.3 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的全部阶跃点的集合，S1

18、j=(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，舍弃其中被支配的阶跃点和所有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),(

19、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的最大的阶跃点; PmaxP1,P2; If (P2P1) xn1=1; else xn1=0; 回溯确定xn2,xn-3,x0; ,7.6.5 性能分析,在最坏情况下，算法的空间复杂度是O(2n)。 在最坏情况下，算法的时间复

20、杂度是O(2n)。,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个作业都能顺利完成。这就是流水线作业调度(flow shop schedule)问题。,7.7 流水作业调度,例710 设有三台设备两个作业，每个作业包含三项任务。完成这些任务的时间由矩阵M给定。,作业i的完成时间fi

21、(S)是指在调度方案S下，该作业的所有任务都已完成的时间。 完成时间F(S)是所有作业都完成的时间。 平均流动时间(mean flow time)MFT(S)定义为：,一组给定的作业的最优完成时间是F(S)的最小值。 OFT表示指非抢先调度最优完成时间 POFT表示抢先调度最优完成时间。 OMFT表示非抢先调度最优平均完成时间， POMFT表示抢先调度最优平均完成时间。 本节只讨论当m=2时获得OFT的调度方案的算法，这就是双机流水作业调度问题。,双机流水作业调度描述为：设有n个作业的集合0，1，n-1，每个作业都有两项任务要求在2台设备P1和P2组成的流水线上完成加工。每个作业加工的顺序总是

22、先在P1上加工，然后在P2上加工。P1和P2加工作业i所需的时间分别为a i和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在设备P1上开始加工，到最后一个作业在设备P2上加工完成所需的时间最少。即求使F(S)有最小值的调度方案S。,7.7.2 动态规划法求解,在两台设备的情况下，存在一个最优非抢先调度方案，使得在P1和P2上的作业完全以相同次序处理（若m2则不然）。,定理73 流水作业调度问题具有最优子结构的性质。,如果在调度方案的作业排列中，作业i和j满足minbi,ajminbj,ai，则称作业i和j满足Johnson不等式。 可以设计下列作业排列方法。这样做能得到最优调度方案 (1)如果mina0,a1,an1, b0,b1,bn1是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,