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

算法设计与分析 DeSignDeSign and Analysis of Algorithms and Analysis of Algorithms In C+In C+ “ “十一五十一五” ”国家级规划教材国家级规划教材 陈慧南陈慧南 编著编著 电子工业出版社电子工业出版社 第2部分 算法设计策略 第7章 动态规划法 7.1 7.1 一般方法和基本要素一般方法和基本要素 7.2 7.2 每对结点间的最短路径每对结点间的最短路径 7.3 7.3 矩阵连乘矩阵连乘 7.4 7.4 最长公共子序列最长公共子序列 7.5 7.5 最优二叉搜索树最优二叉搜索树 7.6 0/17.6 0/1背包背包 7.7 7.7 流水作业调度流水作业调度 7.1 一般方法和基本要素 7.1.3 多段图问题 例例7 71 1 多段图G=(V,E)是一个带权有向图，它具有如下特 性：图中的结点被划分成k2个互不相交的子集Vi， 1ik。其中V1和Vk分别只有一个结点，V1包含源点 （source）s，Vk包含汇点（sink）t。对所有边 E，多段图要求若uVi，则vVi1，1i void 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 *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 class 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;i void MGraph:Dijkstra(int s, T* if (sn-1) throw OutOfBounds; bool *inS=new booln; d=new Tn; path=new intn; for (i=0;i void MGraph:Floyd(T* d= new T*n; path=new int *n; for(i=0;i0) 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;k0，pi0， 0i0，pi0，1iM的阶跃点得到。 对于例例7 78 8有 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) 【程序程序7 79 9】0/10/1背包算法的粗略描述背包算法的粗略描述 void DKP(float *p,float *w,int n, float M, float for (i=0;iP1) xn1=1; else xn1=0; 回溯确定xn2,xn-3,x0; 7.6.5 性能分析 在最坏情况下，算法的空间复杂度是O(2n)。 在最坏情况下，算法的时间复杂度是O(2n)。 7.7 流水作业调度 7.7.1 问题描述 l假定处理一个作业需要执行若干项不同类型的任 务，每一类任务只能在某一台设备上执行。设一条 流水线上有n个作业J=J0,J1,Jn1和m台设备 P=P1,P2,Pm。每个作业需依次执行m个任务， 其中第j个任务只能在第j台设备上执行，1jm。 设第i个作业的第j项任务Tji所需时间为tji，1jm， 0i2则不然）。 定理定理7 73 3 流水作业调度问题具有最优子结构的性 质。 l =(0),(1),(k-1) lg (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满足JohnsonJohnson 不等式。不等式。 最优调度方案中，只要有作业i先于j处理，必然有 ： minbi, aj = min bj,ai 即满足Johnson不等式 最优调度求解方案 l可以设计下列作业排列方法。这样做能得到 最优调度方案 (1)如果mina0,a1,an1, b0,b1,bn1是ai，则ai应 是最优排列的第一个作业； (2)如果mina0, a1, , an-1, b0, b1, bn1是bj，则bj 应是最优排列的最后一个作业； (3) 继续（1）和（2）的做法，直到完成所有作业 的排列。 例例7 71111设n4，（a0,a1,a2,a3）=(3,4,8,10) （b0,b1,b2,b3）=(6,2,9,15)。 l设 =(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，因作业1和0已调度， 接着考察a2，应有(1)=2，再考察b2和a3，令(2)=3 。 所以最优解为：(0),(1),(2),(3) （0,2,3,1）。 7.7.3 Johnson算法 l Johnson算法具体描述如下： 设ai和bi，0in分别为作业i在两台设备上的处 理时间。建立由三元组（作业号,处理时间,设备号 ）组成的三元组表d。 对三元组表按处理时间排序，得到排序后的三元 组表d。 对三元组表的每一项di，0in，从左和右两端 生成最优作业排列cj, 0jn，cj是作业号。如果 di的设备号为1，则按从左向右顺序将作业i置于c 的左端第一个空位，否则按从右向左的顺序置于c 的右端第一个空位。 【程序程序7 71212】JohnsonJohnson算法算法 /三元组结构 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算法的时间取决于对作业集合的