算法设计与分析第8-10章课件

1、第8章 分枝一限界法本章的内容是回溯法讨论的问题的继续和扩展。使用限界函数的深度优先生成结点方法是回溯法，E结点一直保持到死为止的状态生成方法叫分枝限界法。在这一章里，首先介绍状态空间树上的三种检索方式：FIFO，LIFO，LC检索，再重点介绍用LC-分枝限界法解最优化问题的一般实现，最后得出一个实例0/1背包的解法以及用C语言实现的程序。8.1 状态空间树上的检索FIFO，LIFO，LC检索8.1.1 FIFO(first in first out)，LIFO(last in first out)检索图8.1 由FIFO分枝限界法生成的一部分4-后状态空间树8.1.2 LC-检索在生成一个答

2、案结点之前，子树X需要生成的结点数。在子树X中，X到最近一个答案结点的路径长。例8.1 15谜问题(15-puzzle)。在44的方格棋盘上,将数字1,2,3,15以任意顺序放置在棋盘的各个方格中，空出一格,如图8.2(a)为15谜问题的一种初始棋盘格局。定理8.1 对于一个给定的状态图8.2 15谜问题的一个实例如果这个和数是偶数,则这个状态可达目标状态,否则,其他任何初态都不可达目标状态。图8.3 15-谜问题的一部分状态空间树设想1：g(X)是结点X表示的状态中没有到达目标位置的非空白牌的数目。显然，状态X到达目标状态所需要的移动空白牌的次数大于g(X)。比如状态X设想2： f (x)同

3、设想1， 这里j表示空格的位置。它也是一个可行的方法,似乎不及设想1中的g (X)好，因为对图 8.3给定的初态，它需要产生更多的结点，但是如果检索如8.1.3 LC-检索的抽象化描述算法8.1的状态空间树，按设想1,g(1)=1,按设想2, g (1) = 14。这里f ( X ) +14=14显然更接近C(X),C(X)是初态到目标状态的路径长度,即需要移动空白牌的次数。procedure LC(T，C)；begin ET；置活结点表为空；loop if E是答案结点 then begin 输出从E到T的路径； return； end； for E的每个儿子结点X do begin cal

4、l add(x)； parent(x)E； end；if 不再有活结点 then begin print(No answer node)； stop； end； call least(E)； repeat；endp；8.2 分枝限界法解最优化问题例8.2 带限期的作业排序问题。假定有n个作业Wi，i=1，n和一台处理机，每个作业Wi与一个三元组(pi，di，ti)对应，其中ti是完成作业Wi需要的时间，di是完成作业Wi需要的期限，如果不在这个期限di之内完成Wi则将受到pi的罚款。问题的目标是从n个作业中选取一个子集J，要求J中的作业都能在相应的限期内完成，且使不在J中的作业受到的罚款总额最

5、小,这样的J就是最优解。图8.4 大小可变的元组表示对应的状态空间树X中最小成本答案结点的上界函数u(X)定义为：图8.5 大小固定的元组表示对应的状态空间树以图8.4元组大小不固定的状态空间树为例说明作业排序的LC-分枝限界算法。开始时置最小成本答案结点的成本上界U=,或由于图8.4中每个圆形结点都是答案结点，按U的定义：算法8.2procedure LCBB(T，c，u，cost)/为了找出最小成本结点,检索状态空间树T,假定T至少包含一个解结点,且C(X)C(X) u(X)/begin ET；parent(E)0； if T是解结点 then begin Umin(cost(T)，u(T

6、)+)； ansT； endelse begin Uu(T)+； ans0； end；将活结点表初始化为空；loop for E的每个儿子 do if C(X)U then begin call ADD(X)； parent(X) E； case X是解结点and cost(X)U： begin Umin(cost(X)，u(X)+)； ansX； end； u(X)+UUu(X)+： endcase； end；if 不再有活结点 or 下一个E-结点有CU then begin print(least cost=，U)； while ans0 do begin print(ans)； ans

7、parent(ans)； end； return； end； call least(E)； repeat；endp；对算法LCBB还需强调以下几点：当下一个E-结点使CU时，算法终止；子算法ADD是加入一个结点到活结点表中，LEAST是从一个活结点表中删去一个结点，活结点表作成一个min堆；如果U是已找到的一个解X的成本值，U=c(X)u(X)，对于X的儿子Y，不仅c(Y)U，而且c(Y)=U的结点Y都要被杀死；如果U是一个单纯的上界，它是由一可行结点X的u值修改而得，U=u(X)+。对于X的儿子只杀死c(Y)U的Y，c(Y)=U的Y不被杀死，Y入堆；虽然找到了一个答案结点X,但它的成本值大于

8、它的上界值u(X),这说明,这个答案结点的子孙中还有成本更小的答案结点,U取u(X)+,对于X的儿子结点Y,只杀死c(Y)U的Y，c(Y)=U的Y不被杀死,Y入堆。8.3 0/1背包问题的LC-分枝限界求解的 实现例8.3 0/1背包问题。问题可描述如下：极小化：规范函数 xi=0 或 xi=1, 1in成本函数 为了使最小成本答案结点与最优解对应，成本函数定义如下：如果X是答案结点，如果X是不可行的叶子结点，C(X)=；如果X是非叶子结点,C(X)= minC(LCHI LD(X),C(RCHILD(X)。算法8.3procedure UBOUND(P，W，k，M)；/P：当前效益总量;W:

9、当前背包质量;k:上次处理的物品的下标号;M:背包容量;W(i)：第i种物品的质量;P(i):第i种物品的效益值,并且P(i)/W(i)P(i+1)/W(i+1),1in/begin bP；cW； for ik+1 to n do if c+ W(i)M then begin cc+W(i)； bb-P(i)； end； return(b)；endp；算法8.4算法中涉及的说明同算法8.3.procedure BOUND(P，W，k，M)；begin bP；cW； for ik+1 to n do begin cc+W(i)； if cM then bb-P(i) else return(b-

10、(1-(c-M)/W(i)*P(i)； end； return(b)；endp；图8.6 0/1背包问题的一个实例的分枝限界检索解决以下问题：被检查的状态空间树中结点的结构；如何生成一个儿子结点；如何识别答案结点；活结点表的表示以及其上的操作。算法8.51)计算上、下界Procedure LUBOUND(P,W,rw,cp,N,k,LBB,UBB),/rw：背包的剩余容量,cp：已获得的效益,还有k，N个物品作选择,LBB=-u(X),UBB=-C(X)/begin LBBcp；crw； for ik to N do begin if cW(i) then begin UBBLBB+c*P(i

11、)/W(i)； for ji+1 to N do if cW(j) then begin cc-W(j)； LBBLBB+P(j)； end； return； end； cc-W(i)； LBBLBB+P(i)； end； UBBLBB；endp；2)生成一个新结点Procedure NEWNODE(par，lev，t，cap，prof，ub)/生成一个新结点i，将它加入活结点表中/begin call GETNODE(i)； ARENT(i)par;LEVEL(i)lev;TAG(i)=t； CU(i)cap；PE(i)prof；UB(i)ub； call ADD(i)；endp；3)输出解

12、procedure FINISH(L，ANS，N)begin for jN to 1 step-1 do begin if TAG(ANS)=1 then printf(j)； ANSPARENT(ANS)； end；endp；算法8.6procedure LCKNAP(P，W，M，N，)1 begin2 call INIT ；/初始可用结点表以及活结点表/3 call GETNODE(E)；/生成根结点/4 PARENT(E)0;LEVEL(E)1;CU(E)M；PE(E)0；5 call LUBOUND(P， W， M， N，0，1， LBB， UBB)；6 LLBB-；UB(E)UBB；

13、7 repeat8 iLEVEL(E)；capCU(E)；prof PE(E)；9 case10 i=N+1/解结点/11 if profL then12 begin13 Lprof；14 ANSE；15 end；16 iN+1/E有的两个儿子/17 begin18 if capW(i) then /生成左儿子/19 ca ll NEWNODE(E，i+1，1，cap-W(i)，prof+p(i)，UB(E)； /看右儿子是否会成为活结点/20 call LUBOUND(P，W，cap，prof，N，i+1，LBB，UBB)；21 if UBBL then /右儿子会活/22 begin23

14、call NEWNODE(E，i+1，0，cap，prof，UBB)；24 Lmax(L，LBB-)；25 end；26 endcase；27 if 不再有活结点 then exit；28 call LARGEST(E)；29 until UB(E)L；30 call FINISH(L，ANS，N)；31 endp；下面是该算法用C语言实现的程序清单。/* this is the fixed number */#define n 8#define lit 0.000 1#define m 110.0#define nn 20#define len sizeof(struct point)/*

15、this is the data structure */struct point int parent； int level； int tag； float cu； float pe； float ub；struct list struct point *dot； struct list bagnn； struct point *e； float apn，awn； float l，lbb，ubb； int pc，lpc，ans； int llnn；/* the more number*/float max(a，b)float a，b； float more； if (ab) more=a；

16、else more=b； return(more)；main( ) float cap，prof，x，y； Int i，j，k，la，jobok； void lubound( )； void newnode( )； void add()； void finish()； int largest()； printf(* this is a programme about 0/1 bag problem * n)； printf(input p and w !n)； for (i=0；i=n-1；i+) scanf(%f，&x)； scanf(%f，&y)； j=0； while (j=i-1) &

17、 (x/y)(apj/ awj) j=j+1； for (k=i；k=j+1；k-) apk=apk-1 ； awk=apk-1 ； apj=x；awj=y； jobok=0； pc=0； lpc=0； e=(struct point *) malloc(len)； e-parent=-1；e-level=1;e-cu=m； e-pe=0.0；e-tag=-1； la=0； lubound(m，0.0，0)； l=lbb-lit； e-ub=ubb； bagpc.dot=e； ans=0； do i=e-level;cap=e-cu；prof=e-pe； if (i=n+1) printf(*

18、 the best result is： * *n)； if (profl) l=prof；ans=la； else if (cap=awi-1) newnode(la，i+1，1，cap-awi-1， rof+api-1，e-ub)； lubound(cap，prof，i)； if (ubbl) newnode(la,i+1,0,cap,prof,ubb)； l=max(l，lbb-lit)； if (lpc= =0) printf(the num of livelist is %dn，lpc)；jobok=1；break； if (!jobok) la=largest()； e=bagla

19、.dot； while(e-ub)l) ； finish(ans，l)； printf( * my programme have finished *n)；/* the bound of the point */void lubound(rw，cp，k)float rw，cp；Int k； int i，j； float c； lbb=cp；c=rw； for (i=k；i=n-1；i+) if (cawi) ubb=lbb+c*api/awi； for (j=i+1；j=n-1；j+) if (c=awj) c=c-awj； lbb=lbb+apj； goto exit； c=c-awi；lb

20、b=lbb+api； ubb=lbb；exit ； /* add to livelist */void add(y)Int y； int j，addok； lpc=lpc+1； addok=0； j=lpc； while (! addok) & (j1) if (bagy.dot-ub)=(bagll j/2. dot-ub) llj=llj/2； j=j/2； else addok=1； llj=y； /* delete the largest number from the livelist and form the max-stock again */int largest() int

21、lar，i，j，t，delok； lar=ll1； ll1=lllpc； lpc=lpc-1； i=1； j=2*i； t=ll1； delok=0； while (j=lpc) & (!delok) if (jlpc) & (bagllj.dot-ub)(bagllj+1.dot-ub) j=j+1; if(bagt.dot-ub)=(bagllj. dot-ub) delok=1； else lli=llj； i=j； j=2*i； lli=t； return(lar)；/* NEWNODE form a new point */void newnode(par，lev，t，cap，pro

22、f，vub)int par，lev，t；float cap，prof，vub； pc=pc+1； e =(struct point *) malloc(len)； e-parent=par； e-level=lev； e-tag=t； e-cu=cap； e-pe=prof； e-ub=vub; bagpc.dot=e； add(pc)； /* print the result */void finish(ans，l)Int ans；float l； printf(VALUE OF OPTIMAL FILLING IS ：%fn, l)； printf(OBJECTS IN KNAPSACK

23、ARE:)； while (ans0) if (bagans.dot-tag= =1) rintf(% d-，bagans.dot-level-1)； ans=bagans.dot-parent； printf(endn)；第9章 内存分类法分类也叫排序。根据待分类的记录的数量的多少，可将分类分为两类：一类是内存分类，这种分类是指待分类的记录的关键字的数量不是很多，可一次调入计算机的内存进行分类；另一类是外存分类，这种分类指的是待分类的数据的数量很大，内存一次不能容纳全部数据，在分类过程中，需要进行内外存的交换进行分类的过程。本章介绍的是第一种,但只介绍内存分类法中两个问题:求第K个元素(也叫

24、顺序统计);另一个是堆排序。9.1 求第K个元素图9.1 锦标赛过程示意图算法9.1 找出序列S=x1，x2，xn的第K小元素。输入：有n个元素的序列S以及整数K，1 Kn；输出： S的第K小元素。pocedure Kthmin(S，K)；begin if S64 then begin sort S; /任一种分类法,对S直接分类/ return S的第K小元素； endelse begin 将S分成 个子序列，每个子序列有15个元素。如果有剩余元素放入子序列L，对它们分别进行分类；设C是15个元素子序列的中值组成的序列； mKthmin(C， c/2 )； /求m的序数/ if m的序数 =

25、K then return m else if m的序数K then Kthmin(S-A，k1=K-A) else Kthmin(S-B，k)； end；endp；对算法9.1的了解可参考图9.2，不妨设n刚好是15的倍数。设T(n)是从S(S=n)中选出第K小元素所需时间，则图9.2 算法9.1的示意图解这个递归式 T(n)=O(n)。算法9.2 寻找序列S的第K小元素。Procedure quickmin(S，K)；begin if S=1 then return S中的单个元素 else else begin 从S中随机地选出一个元素a； 用快速分类法求出S1，S2，S3； /S1：小

26、于a的元素序列；S2：等于a的元素序列；S3：大于a的元素序列；/ if S1K then return quickmin(S1，K) else if S1+S2K then return a else return quickmin(S3,K-S1-S2);end；endp；假设T(n)是对长度为n的序列S求第K小元的平均时间耗费。S中的n个元素xi是互不相同的。在利用快速分类时，作为“枢轴”的元素a是S的第i个最小元，其中i=1，2，n是等概率的。如果iK，则在S1上调用quickmin的时间耗费为：O(n)+T(i-1)；如果iK，则在S3上调用quickmin的时间耗费为：O(n)+T

27、(n-i)；如果i=K，时间耗费为：O(n).当i遍取1，2，n时，可选T(1)c，用归纳法证明：对于所有n2，有T(n)4cn。对于n=2，有 T(1)=3c4c2；假定有T(n)4cn，对所有的n，2nm成立；对于n=m由于T(n)是n的非降函数,因此当 时, 取极大值，所以所以T(n)4cn成立，即T(n)=O(n)。9.2 堆 分 类在数据结构中已作介绍,当待分类的元素没有明显的结构特征时,只能施行“比较”操作,以此确定两个元素的顺序。这种“比较”分类,理论上已证明至少需要作log2n!次比较,而log2n!nlog2n-1.44n+log2 +1.325，此作为比较分类的时间复杂性的

28、理论下界。设A=a1，a2，an是待分类的序列，T是一棵二叉树，T中每个结点都对应着A中的一个元素。T是一个极大/极小堆，当且仅当满足以下条件：T是一棵完全二叉树；aia2i且aia2i+1 或 aia2i且aia2i+1 (i=1，2，n/2).利用堆可以将待分类的序列A分类，其基本步骤是：将A建成堆；A1An；置nn-1，即在T中把极大结点输出，得到一棵非堆的二叉树；恢复堆。在当前T中，将根结点(或子树的根结点)与它的两个儿子结点中较大的结点交换,直到每个结点都大于它的子孙为止；重复、，直到n=1，将输出分类后的结果。这种分类方法叫堆分类。1)建立初始堆算法9.3procedure HEA

29、PFIFY(i，j)；/将数组元素AiAj建成堆/begin while (2i+1j)(AiA2i )(AiA2i+1) do /i不是一片叶子且若i的儿子含有比i大的元素/ begin if(A2iA2i+1)then begin Ai A2i； HEAPFIFY(2i，j)； end else begin AiA2i+1； HEAPFIFY(2i+1，j)； end； if(2i=j)(AiA2i) then Ai A2i； end； endp；算法9.4Procedure BUILDHEAP；begin for i n/2step-1 until 1 do call HEAPFIFY(

30、i，n)；endp；2)分类算法9.5 Heapsort：输入：待分类的数组Ai，1in；输出：已分类的数组A。procedure Heapsort；begin call BUILDHEAP； mn； while m1 do begin AiAm；mm-1；call HEAPFIFY(1，m)； end；endp；对于深度为K的堆,HEAPFIFY进行关键字比较的次数至多为2(k-1)次,则在建含有n个元素，深度为h的堆时,由于第i层上的结点数至多为2i-1,以它为根的完全二叉树的深度为h-i+1。则调用n/2次HEAPFIFY总共进行的关键字比较次数不超过下式之值：对于堆分类,每次调用HEA

31、PFIFY算法的比较次数最多是深度的2倍,即2 log2m,2 mn-1，所以总的比较次数是：图9.3 初始堆示例算法9.6procedure UPANDUP(i，j)；begin if i不是叶子 then begin 令k是i的带有较大元素的儿子； AiAk； call UPDANDUP(k，j)； endelse begin Ai Aj+1； /将最后一片叶子放在完全二叉树中当前所缺的叶子结点上。如果所缺的叶子刚好是完全二叉树上的最后一片叶子，则将最后一片叶子自己赋给自己/ while AiA i/2 do begin Ai A i/2； i i/2； end； end；endp；算法9

32、.7procedure Heapsort1；begin call BUILDHEAP； for jn step-1 until 2 do begin BA1；call UPANDUP(1，j-1)；AjB； end；endp；下面对Heapsort1进行时间复杂性分析：初始堆之后，为了输出分类序列，用了15次比较图9.4 Heapsort的实现过程初始堆之后，为了输出分类序列，用了9次比较图9.5 Heapsort1的实现过程算法9.8procedure UPORDOWN(i，j)；begin if id then begin 令k是i的较大儿子； AiAk； call UPORDOWN(k，

33、j)； end else begin AiAj+1； if AiA i/2 then call HEAPFIFY(i，j) else while AiA i/2 do begin AiA i/2； i i/2； end； end；endp；算法9.9procedure Heapsort2；begin call BUILDHEAP； for jn step-1 until 2 do begin d2 ；BA1; UPOR DOWN(1，j-1)； AjB； end；endp；同上对Heapsort1的分析，算法9.9的时间耗费包括两部分：调用BUILDHEAP，初始化堆，其耗费是O(n)。for

34、循环的耗费。第10章 图的算法图是应用极为广泛的数学工具。许多工程和科学技术中的问题可以抽象为图，将图作为其数学模型。图的研究分为两类：一是图论，研究图的一些代数性质；二是图的应用，主要研究图的最优化问题。本章介绍这两方面的一些基本算法。10.1 图的两种遍历DFS，BFS图本身是一种无序结构。在解决图的问题时,几乎所有算法都需要处理图的顶点或边, 为了尽可能少地对顶点和边作重复检查,需要人为地规定图的检索顺序。在数据结构中已介绍过图的遍历的两种方式DFS（Depth First Search）遍历和BFS（Breadth First Search)遍历两种方式,这两种方式实际上都是对图这种无

35、序结构作线性化处理。算法10.1 dfs的递归算法。Procedure dfsrecursive（G，v）。begin 访问v；标记v； while有一个邻接于v的未标记的顶点w do dfsrecursive（G，w）；endp；算法10.2 dfs的非递归算法。Procedure dfs（G，v）；/S是一个栈，初始为空，在任何时候，栈顶元用top表示/begin 访问v；标记v；push（S，v）； while S非空 do begin while top有邻接点w且w未标记 do begin 访问w；标记w；push（S，w）; end； pop（S）； end；endp；算法10.3

36、Procedure bfs（G，v）；/Q是一个队列，初始为空/begin 访问v；标记v；enqueque（Q，v）； while Q非空do begin xdelqueque（Q）； for 每个邻接于x而未标记的顶点w do begin 访问w；标记w； enqueque（Q，w）； end； end；endp；上述算法仅访问了以v为始点，以及v的可达顶点，如果要访问G中每个顶点，则算法10.4 图的遍历。Procedure travel（G）；begin for v1 to n do v标记0； for v1 to n do if v未标记 then dfs/bfs（G，v）；endp

37、；10.2 DFS 树在一个图（有向图或无向图）上作DFS时，引向未标记顶点的边构成一棵有限树称为DFS树，这种边称为树边。如果从始点出发，图中所有顶点不是始点的可达顶点，则对图的遍历生成DFS森林。对于无向图，这种搜索给图的每条边一个定向，按通过边的方向对边定向。如果是有向图，则只能按预先给定边的方向对边进行访问。算法10.5 求图G的DFN数组Procedure dfsDFN（G，v）；/G的存储用邻接表l/var t：link；begin visit（v）；markv1；DFNvx; xx+1； t1v；（a）有向图G （b）有向图G的DFS森林图10.1 while tnil do b

38、egin if markt，v=0 then dfs-DFN（G，t，v）； tt.next； end；endp；Procedure travel（G）；begin for v1 to n do markv0； x1； for v1 to n do if markv=0 then gfs2（v）；endp；顶点的深度优先数与顶点的先辈后代关系的关系如下，以此去识别G的四种类型的边：如果w是v的后代，则：DFN(v)DFN（y）；如果有向边（x，y）是子孙边，则：DFN（x）DFN（y）。如果x,y不满足,则x,y是兄弟关系,或属于不同的连通分支,所以和用来判定横跨边, 、则作为判定回边与子孙边

39、。10.3 无向图的双连通分支定义10.1 设G=(V，E)是一个连通的无向图，顶点aV,如果存在顶点v,wV和a互不相同，并且v和w之间的每一条路径都包含a, 则称a是图的一个关节点,也叫图的割点。定义10.3 E上的一个等价关系R定义为：e1Re2 e1=e2或者G中有一个回路既包含e1又包含e2。定义10.4 等价关系R将E分成等价类，E1，E2，Ek，使得两条不同边在同一个类当且仅当它们位于同一个回路上。设Vi是Ei中边的关联顶点集，每个图Gi=（Vi，Ei）是G的一个双连通分支。例10.1 图10.2（a）是一无向图。B，E，F是关节点，G有4个双连通分支，位于公共回路的边的等价类是

40、：（a）图G （b）G的4个双连通分支图10.2E1=(G,B),(B，I),(I，G)E2=(B,E),(E，C),(C，B)E3=(E,F)E4=(H,E),(E,I),(H,A),(A，F),(F,D),(A,D),(I,D)有几点注意：一条边（例如E3）没有回路，也产生一个双连通分支。R是E上的等价关系,R对E产生一个分划,并不对V产生分划,因此一个顶点可能在几个分支中,比如,B现在G1=（E1,V1）又出现在G2=（E2,V2）中。算法10.6 计算无向图G计算low数组。Procedure dfs-low(G,k)；/假定G用邻接表l存储,mark,low,DFN,father数组

41、分别是标记数组,low数组和DFS数数组,以及顶点的父亲。/图10.3 DFS树T中的一个关节点Vvar t：link；begin markk1；DFNkx；xx+1; lowkDFNk；t1k； while tnil do begin if markt.k=0 then begin fathert.kk； dfs-low（t.k）； lowkminlowk，lowt.k； /如果顶点k在dfs树中有一个儿子w=t.k,且low（w） DFN（top） do begin tag（x）1；output x； pop（SC）； end； /输出一个强连通分支/end else begin push

42、（SC，top）； ZS上的第二个顶点（从top起） low(Z)minlow(Z)，low(top) end； pop（S）； /从top返回到Z，即新的top/ if S不空 then goto forward； endp；10.5 流 的 算 法许多系统涉及流量问题，比如车辆运行系统中的车流，控制系统的信息流，金融系统的金融流等，这些研究对象抽象为数学问题时，数学模型是网络中的流。它本身属于运筹学和组合数学讨论的内容，本节内容作为有向图的应用。10.5.1 基本概念（1）网络与流定义10.5 G=(V,E)是一带权的有向图,在V中指定了一点称为发点(source),vs以表示;指定 了另一点称为收点(sink),以vt表示;其余的点叫中间点。G中边上的权大于或等于0,称为弧的容量,记为C(vi，vj),简记为Cij。所谓网络上的流,是指定义在E上的一个函数f=f(vi，vj),称f (vi,vj)(简记为fij)为弧(vi,vj)上的流量,f称为网络G上的一个流,如图10.8。(a) 网络G，边上的数表弧的容量Cij(b) G上的一个流，边上的数表弧的流量fij图10.8 网络上的流(2)可行流与最大流在网络的实际问题中，对于流有两个明显的要求：一