《算法设计与分析》第07章.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 一般方法和基本要素 l动态规划法的实质也是将较大问题分解为较小的 同类子问题，这一点上它与分治法和贪心法类似 。但动态规划法有自己的特点。分治法的子问题 相互独立，相同的子问题被重复计算，动态规划 法解决这种子问题重叠现象。贪心法要求针对问 题设计最优量度标准，但这在很多情况下并不容 易。动态规划法利用最优子结构，自底向上从子 问题的最优解逐步构造出整个问题的最优解，动 态规划则可以处理不具备贪心准则的问题。 7.1.1 一般方法 最优性原理最优性原理指出，一个最优策略具有这样的性 质，不论过去状态和决策如何，对前面的决策所 形成的状态而言，其余决策必定构成最优策略。 这便是最优决策序列的最优子结构特性。 设计一个动态规划算法，通常可以按以下几个步 骤进行： （1）刻画最优解的结构特性； （2）递归定义最优解值； （3）以自底向上方式计算最优解值； （4）根据计算得到的信息构造一个最优解。 其中，第（1）至（3）步是动态规动态规 划算法的基 本步骤骤。最优优解值值是最优优解的目标标函数的值值。 7.1.2 基本要素 一个最优化多步决策问题适合用动态规划法求 解有两个要素：最优子结构特性和重叠子问题。最优子结构特性和重叠子问题。 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,*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 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 流水作业调度问题具有最优子结构的性 质。 如果在调度方案的作业排列中，作业i和j满足 minbi,ajminbj,ai，则称作业i和j满足JohnsonJohnson不不 等式。等式。 可以设计下列作业排列方法。这样做能得到最优 调度方案 (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);