算法设计与解读实用教案

1、 南京(nn jn)邮电大学计算机学院 2008年3月第2部分 算法(sun f)设计策略第1页/共66页第一页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月第9章 分支(fnzh)限界法 第2页/共66页第二页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月第3页/共66页第三页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月9.1 一般(ybn)方法 第4页/共66页第四页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月9.1.1 分枝分枝(fn zh)限界法概述限界法概述采用广度优先产生状态空间树的结点，并使用剪枝

2、函数的方法(fngf)称为分枝限界法。按照广度优先的原则，一个活结点一旦成为扩展结点（E-结点）R后，算法将依次生成它的全部孩子结点，并将它们一一加入活结点表，此时R自身成为死结点。算法从活结点表中另选一个活结点作为E-结点。第5页/共66页第五页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月不同的活结点表形成不同的分枝限界法，分为：FIFO分枝限界法、LIFO分枝限界法和LC（least cost）分枝限界法。三种不同的活结点表，规定了从活结点表中选取下一个E-结点的不同次序。FIFO分枝限界法的活结点表是先进先出队列LIFO分枝限界法的活结点表是堆栈(duzhn)； L

3、C分枝限界法的活结点表是优先权队列，LC分枝限界法将选取具有最高优先级的活结点出队列，成为新的E-结点。第6页/共66页第六页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月 例91 (4-皇后问题(wnt) FIFO分枝限界法求解第7页/共66页第七页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月【程序(chngx)91】分枝限界算法template struct Node T cost; Node* parent;第8页/共66页第八页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月templatevoid BranchBound(N

4、ode* t) LiveListNode* lst(mSize); Node *x,*E=t; do for( 对结点E的每个不受限的孩子) x=new Node;x-parent=E; if ( x是一个(y )答案结点 ) 输出从x到 t的一条路径；return; lst.Append(x); 第9页/共66页第九页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月 if(lst.IsEmpty()cout“没有答案(d n)结点”；return； lst.Serve(E); while（1）；第10页/共66页第十页，共66页。 南京(nn jn)邮电大学计算机学院 20

5、08年3月9.1.2 LC分枝(fn zh)限界法 代价函数(hnsh)c()若X是答案结点，则c(X)是从根结点到X的搜索代价；若X不是答案结点且子树X上不含任何答案结点，则c(X) = ；若X不是答案结点但子树X上包含答案结点，则c(X)等于子树X上具有最小搜索代价的答案结点的代价。 第11页/共66页第十一页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月相对代价函数g()衡量一个结点X的相对代价一般有两种标准： 在生成一个答案结点之前(zhqin)，子树X上需要生成的结点数目； 在子树X上，离X最近的答案结点到X的路径长度。容易看出，如果采用标准，总是生成最小数目的结

6、点；如果采用标准，则要成为E-结点的结点只是由根到最近的那个答案结点路径上的那些结点。 第12页/共66页第十二页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月第13页/共66页第十三页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月相对代价估计函数(.)(X)作为(zuwi)g(X)的估计值，用于估计结点X的相对代价，它是由X到达一个答案结点所需代价的估计函数。一般地，假定(X)满足如下特性：如果Y是X的孩子，则有(Y) (X)。代价估计函数(.)(X)是代价估计函数，它由两部分组成：从根到X的代价f(X)和从X到答案结点的估计代价(X)，即(X)=f(

7、X)+ (X)。一般而言，可令f(X)等于X在树中的层次。第14页/共66页第十四页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月9.1.3 15谜问题(wnt) 在一个44的方形棋盘(qpn)上放置了15块编了号的牌，还剩下一个空格。问题要求对于任意给定的一种初始排列，通过一系列的合法移动，将给定的初始排列转换成目标排列。 第15页/共66页第十五页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月初始状态和目标状态，从任意初始状态，经一系列的空格移动，到达目标状态。空格可以最多有前、后、左和右四种移动方式。共有16！种不同的排列。这个状态空间(kngji

8、n)树是相当大的。有必要判定当前到达的状态是否属于该状态空间(kngjin)树。第16页/共66页第十六页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月定理9-1 对给定的初始状态，当且仅当为偶数时，可以由此初始状态到达目标状态，其中(qzhng)，i和j分别是空格在棋盘上的行和列下标。 161kjiless(k)第17页/共66页第十七页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月第18页/共66页第十八页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月第19页/共66页第十九页，共66页。 南京(nn jn)邮电大学计算机学院 2

9、008年3月9.2 求最优解的分枝(fn zh)限界法 第20页/共66页第二十页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月9.2.1 上下界(xi ji)函数定义9-1 状态空间树上一个结点X的代价函数c()定义为：若X是答案结点，则c(X)为X所代表的可行解的目标函数值；若X为非可行解结点，则c(X)=；若X代表部分向量，则c(X)是以X为根的子树上具有最小代价的结点代价。显然，这样(zhyng)定义的c(X)也是难以计算的，它的计算难度与求得问题最优解的难度相当定义9-2 函数u()和()分别是代价函数c()的上界和下界函数。对所有结点X，总有(X)c(X)u(X

10、)。第21页/共66页第二十一页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月基于上下界函数的分枝限界法的限界方法 U的值可以按下列原则修正(xizhng)：如果X是答案结点，cost(X)是X所代表的可行解的目标函数值，u(X)是该子树上最小代价答案结点代价的上界值，则U=mincost(X), u(X)+, U；如果X代表部分向量，则U=minu(X)+, U。 使用(X)U 剪除多余分枝。第22页/共66页第二十二页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月9.2.2 FIFO分枝(fn zh)限界法 templateNode* FIFOBB(

11、Node* t,T& U) LiveListNode* lst(mSize); Node *ans=NULL, *x, *E=t; do for(对结点( ji din)E的每个孩子x) if (x)parent=E;第23页/共66页第二十三页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月第24页/共66页第二十四页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月9.2.3 LC分枝分枝(fn zh)限界法限界法 【程序9-3】 基于(jy)上下界的LC分枝限界法templateNode* LCBB(Node* t,T& U) LiveL

12、istNode* lst(mSize); Node *ans=NULL,*x,E=*t; do for( 对结点E的每个孩子x) if (x)parent=E; lst.Append(x); 第25页/共66页第二十五页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月 if ( x是一个(y )答案结点 & cost(x)U) if (u(x)+ cost(x) U=u(x)+; else U=coxt(x);ans=x; else if(u(x)+U) U=u(x)+; if(!lst.IsEmpty() lst.Serve(E); if (E)U) return

13、ans; else return ans; while（1）；第26页/共66页第二十六页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月9.3 带时限(shxin)的作业排序第27页/共66页第二十七页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月9.3.1 问题(wnt)描述 对于单处理机的带时限作业排序问题，如果每个作业具有( jyu)相同的处理时间，则可以用贪心法求解。如果每个作业的处理时间允许不同，带时限的作业排序问题可描述为：设有n个作业和一台处理机，每个作业所需的处理时间、要求的时限和收益可用三元组（ti, di, pi）， 0in表示，其中

14、，作业i的所需时间为ti，如果作业i能够在时限di内完成，将可收益pi，求使得总收益最大的作业子集J。第28页/共66页第二十八页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月第29页/共66页第二十九页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月9.3.2 分枝(fn zh)限界法求解 可变大小元组（x0, x1, xk）表示(biosh)解，xi为作业编号。问题的显式约束为：xi0, 1, n1且xixi+1(0in1)，隐式约束为：对于选入子集J的作业（x0, x1, xk），存在一种作业排列使J中作业均能如期完成。问题的目标函数是作业子集J中所

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

16、改变(gibin)目标函数，将其改为未入选子集J的作业所导致的损失，即为：pmin1.nJ,iii第31页/共66页第三十一页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月 (X) u(X) (X) c(X) u(X)Ji|imax, mpmJ, iii 1,.,nmiimJ,iii1.nJ,iiippp第32页/共66页第三十二页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月第33页/共66页第三十三页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月9.3.3 带时限(shxin)作业排序算法 【程序94】 带时限(shxin)的作业

17、排序 struct NodeNode(Node* par,int k)parent=par;j=k;Node* parent;int j; ;第34页/共66页第三十四页，共66页。 南京(nn jn)邮电大学计算机学院 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;第35页/共66页第三十五页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月templateclass J

18、Spublic:JS(T *prof,int *de,int *time,int size);T JSFIFOBB();void GenerateAns(int *x,int &k);private:T *p,total;int *t,*d,n;Node *ans,*root; 第36页/共66页第三十六页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月templateT JS:JSFIFOBB () Node *E,*child;QueueqNode q(mSize); E=root=new Node(NULL,-1); qNode ep(0,0,0,-1,root

19、),ec; T U=total+epsilon while(1) T loss=ep.loss,prof=f; E=ep.ptr; for (int j=ep.j+1;jn;j+) 第37页/共66页第三十七页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月 if(ep.d+tj=dj & lossU) child=new Node(E,j); f=prof+pj;ec.d=ep.d+tj; ec.ptr=child;ec.loss=loss;ec.j=j; q.Append(ec); T cost=f; if(cost

20、=U); /while /JSFIFOBB第39页/共66页第三十九页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月9.4 0/1背包(bibo) 第40页/共66页第四十页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月9.4.1 问题(wnt)描述已知一个载重为M的背包和n件物品(wpn)，第i件物品(wpn)的重量为wi(wi0)，如果将第i件物品(wpn)装入背包，将有收益pi ( pi0，0in)。现求一种最佳装载方案，使得总收益最大。例92 设有载重能力为M=15的背包，4件物品(wpn)的重量为：(w0, w1, w2, w3)=(2, 4,

21、 6, 9)，物品(wpn)装入背包的收益为：(p0, p1, p2, p3)=(10, 10, 12, 18)。这一0/1背包实例的解为（1, 1, 0, 1），总收益为38。 第41页/共66页第四十一页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月9.4.2 分枝限界(xinji)法求解 目标函数(hnsh)：代价函数(hnsh)： 若X是答案结点（叶结点），则c(X)=cost(X)； 若X是叶结点但非答案结点，则c(X)=； 若X是非叶结点， 则c(X)=maxc(lChild(X), c(rChild(X)。上下界函数(hnsh)：LBB(X)、UBB(X) n

22、1iixp(X)cost第42页/共66页第四十二页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月贪心法的解：Z=（z1,zk,zk+1,zn) 0/1背包的最优解：X= (x1,xk,xk+1,xn) 一个(y )可行解：Y(y1,yk,yk+1,yn) )X(u)X(c(X)c ypxpu(X) xpxpc(X)zpxp(X)c n1kiiik1iiin1kiiik1iiin1kiiik1iii 第43页/共66页第四十三页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月9.4.3 0/1背包(bibo)算法【程序95】 类声明 struct Node

23、/状态空间(kngjin)树结点Node(Node* par,bool lft)parent=par;left=lft;Node* parent; bool left; ; 第44页/共66页第四十四页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月templatestruct pqNode/活结点(ji din)结构 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; fl

24、oat cu; T profit,UBB; int level; Node *ptr; ;第45页/共66页第四十五页，共66页。 南京(nn jn)邮电大学计算机学院 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& LBB,T& UBB); T* p; float* w,m; int n; Node*

25、 ans,* root; ; 第46页/共66页第四十六页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月 【程序96】上下界(xi ji)函数template void Knapsack:LUBound(T cp,float cw, int k,T& LBB,T& UBB) LBB=cp; float c=cw; 第47页/共66页第四十七页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月for (int i=k;in;i+) if(cwi) UBB=LBB+c*pi/wi; for(int j=i+1;j=wj)c=c-wj;LBB=LB

26、B+pj; return ; c=c-wi;LBB=LBB+pi; UBB=LBB; 第48页/共66页第四十八页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月【程序97】0/1背包(bibo)的LC分枝限界法template T Knapsack: LCBB () Node * child,* E;T LBB,UBB,L;ans=NULL; PrioQueuepqNode pq(mSize); root=new Node(NULL,false); E=root; LUBound(0,m,0,LBB,UBB); pqNode e(m,0,UBB,0,root); L=LBB

27、-epsilon; 第49页/共66页第四十九页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月do int k=e.level; float cap=e.cu;T prof=fit;E=e.ptr;if (k=n) & (profL) L=prof;ans=E; else if (cap=wk) child=new Node(E,true); e.ptr=child;e.level=k+1; e.cu=cap-wk;fit=prof+pk; pq.Append(e); 第50页/共66页第五十页，共66页。 南京(nn jn)邮电大学计算机学院

28、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;fit=prof;e.UBB=UBB; pq.Append(e); if (LL); return L;第51页/共66页第五十一页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月第52页/共66页第五十二页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月9. 5 旅行(lxng)商问题 第53页/共66页第五十三页，共66页。 南京(

29、nn jn)邮电大学计算机学院 2008年3月9.5.1 问题问题(wnt)描述描述旅行商问题（travelling salesperson）是一个看似简单其实十分难解的著名(zhmng)难题之一，至今仍有许多人在研究它。此问题描述为：一个旅行商准备到n个村庄售货。他从A村出发经过其它n-1个村庄，又回到出发地A村。现要求一条最短路径，使得每个村庄都经过且仅经过一次。第54页/共66页第五十四页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月9.5.2 分枝限界(xinji)法求解 设带权有向图G=(V,E)，|V|=n，表示连接n个村庄的道路交通图，边上的权值为两个村庄间的

30、路程，cnn是该图的邻接矩阵，下面也称代价矩阵。旅行商问题的解是一条回路：（x0,x1,xn1,xn），x0=xn，0 xin；xixj，当ij和i,j0,n ；E，0in-1。其状态空间树结构见图911的例子(l zi)。图中采用的解结构形式为（x1,xn-1），这里假定x0 xn0。本问题的目标函数是路径长度。 第55页/共66页第五十五页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月第56页/共66页第五十六页，共66页。 南京(nn jn)邮电大学计算机学院 2008年3月 归约代价矩阵定义93 如果矩阵的一行（或列）中至少包含一个零且其余元素(yun s)均非负，则称此行（或列）已归约。定义94 如果一个矩阵的所有行和列均已归约，则称此矩阵为归约矩阵（reduced matrix）。对矩阵的一行（列）进行归约，可以通过将该行(列)中的每个元素(yun s)减去该行（列）的最小数进行，此最小数称为该行（列）的约数。通过逐行逐列的归约，可得到一个代价矩阵的归约矩阵。假定第i行的约数为ti，第j列的约数为rj，0i,jn，则所有行和列约数之和称为矩阵约数，设为L，。第57页/共66页第五十七页，共66页。 南京(nn j