算法设计与分析第09章.ppt

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

1、南京邮电大学计算机学院 2008年3月,算法设计与分析,DeSign and Analysis of AlgorithmsIn C+,“十一五”国家级规划教材,陈慧南 编著,电子工业出版社,南京邮电大学计算机学院 2008年3月,第2部分 算法设计策略,南京邮电大学计算机学院 2008年3月,第9章 分支限界法,南京邮电大学计算机学院 2008年3月,9.1 一般方法9.2 求最优解的分枝限界法 9.3 带时限的作业排序 9.4 0/1背包 9.5 旅行商问题 9.6 批处理作业调度,南京邮电大学计算机学院 2008年3月,9.1 一般方法,南京邮电大学计算机学院 2008年3月,9.1.1

2、分枝限界法概述,采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分枝限界法。按照广度优先的原则，一个活结点一旦成为扩展结点（E-结点）R后，算法将依次生成它的全部孩子结点，并将它们一一加入活结点表，此时R自身成为死结点。算法从活结点表中另选一个活结点作为E-结点。,南京邮电大学计算机学院 2008年3月,不同的活结点表形成不同的分枝限界法，分为：FIFO分枝限界法、LIFO分枝限界法和LC（least cost）分枝限界法。三种不同的活结点表，规定了从活结点表中选取下一个E-结点的不同次序。FIFO分枝限界法的活结点表是先进先出队列LIFO分枝限界法的活结点表是堆栈；LC分枝限界法的

3、活结点表是优先权队列，LC分枝限界法将选取具有最高优先级的活结点出队列，成为新的E-结点。,南京邮电大学计算机学院 2008年3月,例91(4-皇后问题)FIFO分枝限界法求解,南京邮电大学计算机学院 2008年3月,【程序91】分枝限界算法template struct Node T cost;Node*parent;,南京邮电大学计算机学院 2008年3月,templatevoid BranchBound(Node*t)LiveList*lst(mSize);Node*x,*E=t;do for(对结点E的每个不受限的孩子)x=new Node;x-parent=E;if(x是一个答案结点

4、)输出从x到 t的一条路径；return;lst.Append(x);,南京邮电大学计算机学院 2008年3月,if(lst.IsEmpty()cout“没有答案结点”；return；lst.Serve(E);while（1）；,南京邮电大学计算机学院 2008年3月,9.1.2 LC分枝限界法,代价函数c()若X是答案结点，则c(X)是从根结点到X的搜索代价；若X不是答案结点且子树X上不含任何答案结点，则c(X)=；若X不是答案结点但子树X上包含答案结点，则c(X)等于子树X上具有最小搜索代价的答案结点的代价。,南京邮电大学计算机学院 2008年3月,相对代价函数g()衡量一个结点X的相对代

5、价一般有两种标准：在生成一个答案结点之前，子树X上需要生成的结点数目；在子树X上，离X最近的答案结点到X的路径长度。容易看出，如果采用标准，总是生成最小数目的结点；如果采用标准，则要成为E-结点的结点只是由根到最近的那个答案结点路径上的那些结点。,南京邮电大学计算机学院 2008年3月,南京邮电大学计算机学院 2008年3月,相对代价估计函数(.)(X)作为g(X)的估计值，用于估计结点X的相对代价，它是由X到达一个答案结点所需代价的估计函数。一般地，假定(X)满足如下特性：如果Y是X的孩子，则有(Y)(X)。代价估计函数(.)(X)是代价估计函数，它由两部分组成：从根到X的代价f(X)和从X

6、到答案结点的估计代价(X)，即(X)=f(X)+(X)。一般而言，可令f(X)等于X在树中的层次。,南京邮电大学计算机学院 2008年3月,9.1.3 15谜问题,在一个44的方形棋盘上放置了15块编了号的牌，还剩下一个空格。问题要求对于任意给定的一种初始排列，通过一系列的合法移动，将给定的初始排列转换成目标排列。,南京邮电大学计算机学院 2008年3月,初始状态和目标状态，从任意初始状态，经一系列的空格移动，到达目标状态。空格可以最多有前、后、左和右四种移动方式。共有16！种不同的排列。这个状态空间树是相当大的。有必要判定当前到达的状态是否属于该状态空间树。,南京邮电大学计算机学院 2008

7、年3月,定理9-1 对给定的初始状态，当且仅当为偶数时，可以由此初始状态到达目标状态，其中，i和j分别是空格在棋盘上的行和列下标。,南京邮电大学计算机学院 2008年3月,15谜问题的部分状态空间树(FIFOBB),南京邮电大学计算机学院 2008年3月,15谜问题的部分状态空间树(LCBB),南京邮电大学计算机学院 2008年3月,9.2 求最优解的分枝限界法,南京邮电大学计算机学院 2008年3月,9.2.1 上下界函数,定义9-1 状态空间树上一个结点X的代价函数c()定义为：若X是答案结点，则c(X)为X所代表的可行解的目标函数值；若X为非可行解结点，则c(X)=；若X代表部分向量，则

8、c(X)是以X为根的子树上具有最小代价的结点代价。显然，这样定义的c(X)也是难以计算的，它的计算难度与求得问题最优解的难度相当定义9-2 函数u()和()分别是代价函数c()的上界和下界函数。对所有结点X，总有(X)c(X)u(X)。,南京邮电大学计算机学院 2008年3月,基于上下界函数的分枝限界法的限界方法 U的值可以按下列原则修正：如果X是答案结点，cost(X)是X所代表的可行解的目标函数值，u(X)是该子树上最小代价答案结点代价的上界值，则U=mincost(X),u(X)+,U；如果X代表部分向量，则U=minu(X)+,U。使用(X)U 剪除多余分枝。,南京邮电大学计算机学院

9、2008年3月,9.2.2 FIFO分枝限界法,templateNode*FIFOBB(Node*t,T,南京邮电大学计算机学院 2008年3月,lst.Append(x);if(x是一个答案结点 while（1）；,南京邮电大学计算机学院 2008年3月,9.2.3 LC分枝限界法,【程序9-3】基于上下界的LC分枝限界法templateNode*LCBB(Node*t,T,南京邮电大学计算机学院 2008年3月,if(x是一个答案结点 while（1）；,南京邮电大学计算机学院 2008年3月,9.3 带时限的作业排序,南京邮电大学计算机学院 2008年3月,9.3.1 问题描述,对于单处

10、理机的带时限作业排序问题，如果每个作业具有相同的处理时间，则可以用贪心法求解。如果每个作业的处理时间允许不同，带时限的作业排序问题可描述为：设有n个作业和一台处理机，每个作业所需的处理时间、要求的时限和收益可用三元组（ti,di,pi），0in表示，其中，作业i的所需时间为ti，如果作业i能够在时限di内完成，将可收益pi，求使得总收益最大的作业子集J。,南京邮电大学计算机学院 2008年3月,例91 设有带时限的作业排序实例：n=4，(p0,d0,t0)=(5,1,1)，(p1,d1,t1)=(10,3,2)，(p2,d2,t2)=(6,2,1)和(p3,d3,t3)=(3,1,1)，求使得

11、总收益最大的作业子集J。,南京邮电大学计算机学院 2008年3月,9.3.2 分枝限界法求解,可变大小元组（x0,x1,xk）表示解，xi为作业编号。问题的显式约束为：xi0,1,n1且xixi+1(0in1)，隐式约束为：对于选入子集J的作业（x0,x1,xk），存在一种作业排列使J中作业均能如期完成。问题的目标函数是作业子集J中所有作业所获取的收益之和，使得总收益最大的作业子集是问题的最优解。如果希望以最小值为最优解，则可以适当改变目标函数，将其改为未入选子集J的作业所导致的损失，即为：,南京邮电大学计算机学院 2008年3月,可变大小元组（x0,x1,xk）表示解，xi为作业编号。显式约

12、束为：xi0,1,n1且xixi+1(0in1)，隐式约束为：对于选入子集J的作业（x0,x1,xk），存在一种作业排列使J中作业均能如期完成。问题的目标函数是作业子集J中所有作业所获取的收益之和，使得总收益最大的作业子集是问题的最优解。如果希望以最小值为最优解，则可以适当改变目标函数，将其改为未入选子集J的作业所导致的损失，即为：,南京邮电大学计算机学院 2008年3月,(X)u(X)(X)c(X)u(X),南京邮电大学计算机学院 2008年3月,可变大小元组状态空间树,南京邮电大学计算机学院 2008年3月,9.3.3 带时限作业排序算法,【程序94】带时限的作业排序struct Node

13、Node(Node*par,int k)parent=par;j=k;Node*parent;int j;,南京邮电大学计算机学院 2008年3月,templatestruct qNodeqNode()qNode(T p,T los,int sd,int k,Node*pt)prof=p;loss=los;d=sd;ptr=pt;j=k;T prof,loss;Node*ptr;,南京邮电大学计算机学院 2008年3月,templateclass JSpublic:JS(T*prof,int*de,int*time,int size);T JSFIFOBB();void GenerateAns

14、(int*x,int,南京邮电大学计算机学院 2008年3月,templateT JS:JSFIFOBB()Node*E,*child;Queue q(mSize);E=root=new Node(NULL,-1);qNode ep(0,0,0,-1,root),ec;T U=total+epsilon while(1)T loss=ep.loss,prof=ep.prof;E=ep.ptr;for(int j=ep.j+1;jn;j+),南京邮电大学计算机学院 2008年3月,if(ep.d+tj=dj/for,南京邮电大学计算机学院 2008年3月,do if(q.IsEmpty()ret

15、urn total=U;ep=q.Front();q.Serve();while(ep.loss=U);/while/JSFIFOBB,南京邮电大学计算机学院 2008年3月,9.4 0/1背包,南京邮电大学计算机学院 2008年3月,9.4.1 问题描述,已知一个载重为M的背包和n件物品，第i件物品的重量为wi(wi0)，如果将第i件物品装入背包，将有收益pi(pi0，0in)。现求一种最佳装载方案，使得总收益最大。例92 设有载重能力为M=15的背包，4件物品的重量为：(w0,w1,w2,w3)=(2,4,6,9)，物品装入背包的收益为：(p0,p1,p2,p3)=(10,10,12,18

16、)。这一0/1背包实例的解为（1,1,0,1），总收益为38。,南京邮电大学计算机学院 2008年3月,9.4.2 分枝限界法求解,目标函数：代价函数：若X是答案结点（叶结点），则c(X)=cost(X)；若X是叶结点但非答案结点，则c(X)=；若X是非叶结点，则c(X)=maxc(lChild(X),c(rChild(X)。上下界函数：LBB(X)、UBB(X),南京邮电大学计算机学院 2008年3月,贪心法的解：Z=（z1,zk,zk+1,zn)0/1背包的最优解：X=(x1,xk,xk+1,xn)一个可行解：Y(y1,yk,yk+1,yn),南京邮电大学计算机学院 2008年3月,9.4

17、.3 0/1背包算法,【程序95】类声明 struct Node/状态空间树结点Node(Node*par,bool lft)parent=par;left=lft;Node*parent;bool left;,南京邮电大学计算机学院 2008年3月,templatestruct pqNode/活结点结构 operator T()const return UBB;pqNode()pqNode(float cap,T prof,T ub,int lev,Node*p)cu=cap;profit=prof;level=lev;UBB=ub;ptr=p;float cu;T profit,UBB;i

18、nt level;Node*ptr;,南京邮电大学计算机学院 2008年3月,templateclass Knapsackpublic:Knapsack(T*prof,float*wei,float mm,int len);T LCBB();void GenerateAns(int*x);private:void LUBound(T cp,float cw,int k,T,南京邮电大学计算机学院 2008年3月,【程序96】上下界函数template void Knapsack:LUBound(T cp,float cw,int k,T,南京邮电大学计算机学院 2008年3月,for(int

19、i=k;i=wj)c=c-wj;LBB=LBB+pj;return;c=c-wi;LBB=LBB+pi;UBB=LBB;,南京邮电大学计算机学院 2008年3月,【程序97】0/1背包的LC分枝限界法template T Knapsack:LCBB()Node*child,*E;T LBB,UBB,L;ans=NULL;PrioQueue pq(mSize);root=new Node(NULL,false);E=root;LUBound(0,m,0,LBB,UBB);pqNode e(m,0,UBB,0,root);L=LBB-epsilon;,南京邮电大学计算机学院 2008年3月,do

20、int k=e.level;float cap=e.cu;T prof=e.profit;E=e.ptr;if(k=n),南京邮电大学计算机学院 2008年3月,LUBound(prof,cap,k+1,LBB,UBB);if(UBBL)child=new Node(E,false);e.ptr=child;e.level=k+1;e.cu=cap;e.profit=prof;e.UBB=UBB;pq.Append(e);if(LL);return L;,南京邮电大学计算机学院 2008年3月,南京邮电大学计算机学院 2008年3月,9.5 旅行商问题,南京邮电大学计算机学院 2008年3月,

21、问题描述,旅行商问题（travelling salesperson）是一个看似简单其实十分难解的著名难题之一，至今仍有许多人在研究它。此问题描述为：一个旅行商准备到n个村庄售货。他从A村出发经过其它n-1个村庄，又回到出发地A村。现要求一条最短路径，使得每个村庄都经过且仅经过一次。,南京邮电大学计算机学院 2008年3月,9.5.2 分枝限界法求解,设带权有向图G=(V,E)，|V|=n，表示连接n个村庄的道路交通图，边上的权值为两个村庄间的路程，cnn是该图的邻接矩阵，下面也称代价矩阵。旅行商问题的解是一条回路：（x0,x1,xn1,xn），x0=xn，0 xiE，0in-1。其状态空间树结

22、构见图911的例子。图中采用的解结构形式为（x1,xn-1），这里假定x0 xn0。本问题的目标函数是路径长度。,南京邮电大学计算机学院 2008年3月,南京邮电大学计算机学院 2008年3月,归约代价矩阵定义93 如果矩阵的一行（或列）中至少包含一个零且其余元素均非负，则称此行（或列）已归约。定义94 如果一个矩阵的所有行和列均已归约，则称此矩阵为归约矩阵（reduced matrix）。对矩阵的一行（列）进行归约，可以通过将该行(列)中的每个元素减去该行（列）的最小数进行，此最小数称为该行（列）的约数。通过逐行逐列的归约，可得到一个代价矩阵的归约矩阵。假定第i行的约数为ti，第j列的约数为

23、rj，0i,jn，则所有行和列约数之和称为矩阵约数，设为L，。,南京邮电大学计算机学院 2008年3月,对矩阵的一行（列）进行归约，可以通过将该行(列)中的每个元素减去该行（列）的最小数进行，此最小数称为该行（列）的约数。通过逐行逐列的归约，可得到一个代价矩阵的归约矩阵。假定第i行的约数为ti，第j列的约数为rj，0i,jn，则所有行和列约数之和称为矩阵约数，设为L，,南京邮电大学计算机学院 2008年3月,南京邮电大学计算机学院 2008年3月,代价矩阵归约矩阵,南京邮电大学计算机学院 2008年3月,归约行,南京邮电大学计算机学院 2008年3月,归约列,矩阵约数L=25,南京邮电大学计算机学院 2008年3月,下界函数计算方法根结点R的归约矩阵是对邻接矩阵直接归约得到，其下界函数(R)=L，L是矩阵约数。树中任意非叶状态X的归约矩阵B，可由其双亲状态P的归约矩阵A，先变换成A后再归约得到B；X的下界函数(X)=(P)+Aij+r，r是从A归约到B的矩阵约数。叶状态S的下界函数(S)=c(S)，c(S)为从根到S的路径长度。,南京邮电大学计算机学院 2008年3月,上界函数 对于树中任何状态结点X，令上界函数值u(X)=。,南京邮电大学计算机学院 2008年3月,