分支限界法PPT课件

1、1分支限界n1 分支搜索算法n2 分支搜索算法实例p例9.1 装载问题p例9.2 布线问题p例9.3 单源最短路径问题p例9.4 最大团问题p例9.5 0-1背包问题p例9.6 旅行售货员问题n3 图的搜索算法小结第1页/共74页21234567891011 121314151 分支搜索 分支搜索法是一种在问题解空间上进行搜索尝试的算法。 所谓“分支”是采用广度优先的策略，依次生成E-结点所有分支，也就是所有的儿子结点。 和回溯法一样，可以在生成的结点中，抛弃那些不满足约束条件的结点，其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点。 选择下一个E-结点方式的不同导致几种分支搜索

2、方式：q1FIFO搜索 q2LIFO搜索 q3优先队列式搜索 第2页/共74页31 分支搜索-FIFO搜索 一开始，根结点是唯一的活结点，根结点入队。 从活结点队中取出根结点后，作为当前扩展结点。 对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。 再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，直到找到一个解或活结点队列为空为止。1234567891011 12131415第3页/共74页41 分支搜索-LIFO搜索 一开始，根结点入栈。 从栈中弹出一个结点为当前扩展结点。 对当前扩展结点，先从左到右地产生它的所有儿子，用

3、约束条件检查，把所有满足约束函数的儿子入栈; 再从栈中弹出一个结点（栈中最后进来的结点）为当前扩展结点，直到找到一个解或栈为空为止。1234567891011 12131415第4页/共74页51 分支搜索-优先队列式搜索 为了加速搜索的进程，可以采用有效的方式选择E-结点进行扩展。1234567891011 12131415n优先队列式搜索，对每一活结点计算一个优先级（某些信息的函数值）；q根据这些优先级，从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。第5页/共74页62 实例-例9.1 装载问题 例9.

4、1 有两艘船，n个货箱。第一艘船的载重量是c1，第二艘船的载重量是c2，wi 是货箱i 的重量,且 w1+w2+wnc1+c2。确定是否有一种可将所有n 个货箱全部装船的方法。若有的话，找出该方法。n实例分析：有两艘船，3个货箱。第一艘船的载重量是50，第二艘船的载重量是50。当w = 10,40,40时，有解；当w = 20,40,40时，无解。第6页/共74页72 例9.1 装载问题n算法1 FIFO分支搜索n算法2 FIFO分支限界n算法3 优先队列式分支限界n分析：q当第一艘船的可行最大装载为bestw时，若w1+w2+wn-bestwc2，则问题有解。1234567891011 12

5、131415x1=1x1=0 x2=1x2=0 x2=1x2=0 x3=1x3=0 x3=1x3=0 x3=1 x3=0 x3=1x3=0子集树n个物品的取舍组合共2n个叶子结点q因此，此问题可以转化为第一艘船的装载问题。第7页/共74页82 例9.1-算法1 FIFO分支搜索 搜索顺序同广度优先搜索； 辅助数据结构：队列。1234567891011 12131415x1=1x1=0 x2=1x2=0 x2=1x2=0 x3=1x3=0 x3=1x3=0 x3=1 x3=0 x3=1x3=0第8页/共74页92 例9.1-算法1 FIFO分支搜索float bestw,w100; int n;

6、 Queue Q;main( ) float c1,c2;int i,n,s=0; input(c1,c2,n); for(i=1;i=n;i+) input(wi); s=s+wi; if (s=c1 or sc1+c2) print(“no solution”); return; MaxLoading(c1); if (s-bestw=c2); print(“The first ship loading”, bestw); print(“The second ship loading”, s-bestw); else print(“no solution”);第一艘船的最大装载第9页/共7

7、4页10MaxLoading(float c) /返回最优装载值 Add(Q,-1) ; / 初始化活结点队列，标记分层 int i=1; /E-结点的层 ew=0; /当前船的载重量 bestw=0; /目前的最优值 while (not Empty(Q) / 搜索子集空间树 if(ew+wibestw) bestw=wt; else /不是叶子 Add(Q,wt);n算法分析：子集树搜索的时间与空间复杂性均为O(2n)；第11页/共74页122 例9.1-算法1 改进？n算法1缺点？p在可解情况下，没有给出每艘船装载物品的方案。p对子集树的搜索是进行盲目搜索。未考虑“限界”。n改进方案p回

8、溯法用数组记录解方案，数组大小与解向量相同。p分支搜索采用广度优先思想，同时存在的活结点多，用固定大小的一维数组不易保存，活结点的扩展关系不能准确存储。p考虑用结构体数组队列。p如何限界？第12页/共74页132 例9.1-限界 W=50,10,10,C1=60。 在此例中，结点3所在分支的所有子树中，装载货物的最大可能是多少？1234567891011 12131415x1=1x1=0 x2=1x2=0 x2=1x2=0 x3=1x3=0 x3=1x3=0 x3=1 x3=0 x3=1x3=0n如果增加判断，则搜索子集树时，就无需搜索结点3的分支。q因为扩展结点1后，就知道最大装载量不会小于

9、50；而扩展结点3时，发现此分支的“装载上界”为w2+w3=2050，无需搜索此分支，结点3不必入队。q20。q可以定义一个名词“装载上限”，用来描述一个分支中所有叶子结点的装载量的最大值。第13页/共74页142 例9.1-算法2 FIFO分支限界 搜索顺序仍采用FIFO的分支搜索，但当遇到： 若当前分支的“装载上界”，比现有的最大装载小，则该分支就无需继续搜索。1234567891011 12131415x1=1x1=0 x2=1x2=0 x2=1x2=0 x3=1x3=0 x3=1x3=0 x3=1 x3=0 x3=1x3=0n“装载上界”，容易求解，就是假设装载当前物品以后的所有物品。

10、第14页/共74页152 例9.1-算法2 FIFO分支限界-数据结构float bestw,w100,bestx100;int n；Queue Q;struct QNode float weight; QNode *parent; QNode LChild; 是否左儿子？值为1为左儿子，表示取物品；值为0为右儿子，表示不取。第15页/共74页16main( ) int c1,c2,n, s=0,i; input(c1,c2,n); for(i=1;i=n;i+) input(wi); s=s+wi; if (s=c1 or sc1+c2) print(“no solution”); retu

11、rn; MaxLoading(c1); if (s-bestw =c2); print(“The first ship loading”, bestw,“chose:”); for(i=1;i=n;i+) if (bestxi=1) print(i,“,”); print(“换行符 The second ship loading”, s-bestw,“chose”); for(i=1;iweight=0; E-parent =null; E-Lchild=0; add (Q,E) ; bestw=0; r=0; / E-结点中余下的重量 Ew=E-weight; /E-结点的重量 for (i

12、nt j=2;j=n;j+) r=r+ wj; while (true) / 搜索子集空间树 wt=Ew+wi; / 检查E-结点的左孩子 if (wtbestw) bestw=wt; AddLiveNode(wt,i, E ,1); if (Ew+rbestw) / 检查右孩子 AddLiveNode(Ew,i,E,0); Delete (Q,E ) ; / 下一个E-节点第17页/共74页18 if (E=0) / 层的尾部 if (Empty(Q ) break; add (Q, 0) ; / 层尾指针 Delete(Q,E) ; / 下一个E-结点 i+ ; / E-结点的层次 r=r

13、-wi; / E-结点中余下的重量 Ew=E-weight ; / 新的E-结点的重量 / 沿着从bestE到根的路径构造bestx for (j=n-1;j0;j-) bestxj=bestE-LChild; /从bool转换为int bestE=bestE-parent; return bestw; 第18页/共74页192 例9.1-算法2 FIFO分支限界AddLiveNode(folat wt,int i, QNode *E, int ch) Qnode *b; if (i=n) /叶子 if (wtbestw) /目前的最优解 bestE=E; bestxn=ch; /bestxn

14、取值为ch return; b = new QNode; / 不是叶子, 添加到队列中 b-weight=wt; b-parent=E; b-LChild=ch; add (Q,b) ; 第19页/共74页202 例9.1-算法3 优先队列式分支限界 优先队列式搜索通过结点的优先级，可以使搜索尽快朝着解空间树上有最优解的分支推进，这样当前最优解一定较接近真正的最优解。 初始的优先级可以通过“装载上限”确定。q其后将当前最优解作为一个“界”，对上界（或下界）不可能达到（大于）这个界的分支则不去进行搜索，这样就缩小搜索范围，提高了搜索效率。这种搜索策略称为优先队列式分支限界法LC-检索。第20页/

15、共74页212 例9.1-算法3 优先队列式分支限界 1）结点扩展方式：无论那种分支限界法，都需要有一张活结点表。该方法将活结点组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。 2）结点优先级确定：优先队列中结点优先级常规定为一个与该结点相关的数值p，它一般表示其接近最优解的程度，本例就以当前结点所在分支的装载上界为优先值。 3）优先队列组织：结点优先级确定后，简单地按结点优先级进行排序，就生成了优先队列。排序算法的时间复杂度较高，考虑到搜索算法每次只扩展一个结点，数据结构中堆排序，适合这一特点且比较交换的次数最少。此例采用最大堆来实现优先队列。

16、第21页/共74页221 1）要输出解的方案，在搜索过程中仍需要生成解结构树，其结点信息包括指向父结点的指针和标识物品取舍（或是父结点的左、右孩子）。 2）堆结点包括结点优先级信息：结点所在分支的装载上界uweight；堆中无法体现结点的层次信息（level），只能存储在结点中；AddLiveNode用于把活结点加到子树中，并把HeapNode类型的活结点插入最大堆。3）不同于算法2，由于扩展结点不是按层进行的，计算结点所在分支的装载上界时，要用数组变量r记录当前层以下的最大重量，这样可随时方便使用各层结点的装载上界。 2 例9.1-算法3-数据结构设计第22页/共74页232 例9.1-算法

17、3 优先队列式分支限界HeapNode H1000;struct bbnode bbnode *parent; / 父结点指针 int LChild; ; /当且仅当是父结点的左孩子时，取值为1struct HeapNode bbnode *ptr; / 活结点指针 float uweight; / 活结点的重量上限 int level; ; / 活结点所在层 第23页/共74页24算 发 设 计 3 （ 5 ）MaxLoading(float c, int n, int bestx) float r100,Ew,bestw=0; rn=0; for (int j=n-1; j 0; j-)

18、rj=rj+1 + wj+1; int i = 1; bbnode *E = 0; Ew = 0; / 搜索子集空间树 while (i != n+1) / 不在叶子上 if (Ew+wi=c) / 可行的左孩子 AddLiveNode(E,Ew+wi+ri,1,i+1); if (bestwEw+wi) bestw=Ew+wi; if(bestw0;j-) bestxj = E-LChild; E = E-parent; return Ew; 第24页/共74页25AddLiveNode(float wt, int lev,bbnode *E, int ch) bbnode *b=new b

19、bnode; b-parent=E; b-LChild=ch; HeapNode N; N.uweight=wt; N.level=lev; N.ptr=b; Insert(H,N) ; 2 例9.1-算法3 优先队列式分支限界第25页/共74页262 例9.1-算法3-算法说明 算法的复杂度仍为O(2n)，但通过限界策略，并没有搜索子集树中的所有结点，且由于每次都是选取最接近最优解的结点扩展，所以一旦搜索到叶结点作E结点时算法就可结束。算法结束时堆并不一定为空。 第26页/共74页272 例9.1-算法3-算法讨论问题：FIFO搜索或LIFO搜索也可以通过加入“限界”策略加速搜索，与优先队列

20、式分支限界法LC-检索的区别在哪儿呢？ 答案：由于FIFO搜索或LIFO搜索是盲目地扩展结点，当前最优解距真正的最优解距离较大，作为“界”所起到的剪枝作用很有限，不能有效提高搜索速度。第27页/共74页28 例如：W=10,30,50,C1=60, 所构成的子集树如下图所表示：2 例9.1-算法3-算法讨论第28页/共74页291）初始队列中只有结点A；2）结点A变为E-结点扩充B入队，bestw=10； 结点C的装载上界为30+50=80 bestw，也入队；3）结点B变为E-结点扩充D入队，bestw=40； 结点E的装载上界为60 bestw，也入队；4）结点C变为E-结点扩充F入队，b

21、estw仍为40； 结点G的装载上界为50 bestw，也入队；5）结点D变为E-结点，叶结点H超过容量， 叶结点I的装载为40，bestw仍为40；6）结点E变为E-结点，叶结点J装载量为60，bestw为60； 叶结点K被剪掉；7）结点F变为E-结点，叶结点L超过容量，bestw为60； 叶结点M被剪掉；8）结点G变为E-结点，叶结点N、O都被剪掉； 此时队列空算法结束。 FIFO限界搜索过程为： 第29页/共74页30LC-搜索的过程如下： 1) 初始队列中只有结点A；2) 结点A变为E-结点扩充B入堆，bestw=10；结点C的装载上界30+50=80bestw，入堆；堆中B上界为90

22、在优先队列首。3) 结点B变为E-结点扩充D入堆，bestw=40；结点E的装载上界60bestw，入堆；堆中D上界为90为优先队列首。4) 结点D变为E-结点，叶结点H超过重量，叶结点I的装载为40，入堆，bestw仍为40；此时堆中C上界为80为优先队列首。5) 结点C变为E-结点扩充F入堆，bestw仍为40；结点G的装载上界50 bestw，入堆；此时堆中E上界为60为优先队首6) 结点E变为E-结点，叶结点J装载量为60入堆，bestw变为60；叶结点K上界10bestw被剪掉；此时堆中J上界为60为优先队列首。7) 结点J变为E-结点，扩展的层次为4算法结束。虽然此时堆并不空，但可

23、以确定已找到了最优解。优先队列限界搜索解空间的过程是：A-B-D-C-E-J第30页/共74页312 FIFO分支搜索算法框架 上例是求最大值的最优化问题，下面以求找最小成本的最优化问题，给出FIFO分支搜索算法框架。 假定问题解空间树为T，T至少包含一个解结点（即答案结点）。u为当前的最优解，初值为一个较大的数;E表示当前扩展的活结点，x为E的儿子，s(x)为结点x下界函数，当其值比u大时，不可能为最优解，不继续搜索此分支，该结点不入队；当其值比u小时，可能达到最优解，继续搜索此分支，该结点入队；cost(X)为当前叶结点所在分支的解。算法框架如下：第31页/共74页32search(T)

24、/为找出最小成本答案结点检索T leaf=0; 初始化队; ADDQ(T); /根结点入队 parent(E)=0; /记录扩展路径，当前结点的父结点 while (队不空) DELETEQ(E); /队首结点出队为新的E-结点 for (E的每个儿子 X) if (s(X)u) /当是可能的最优解时入队 ADDQ(X); parent(X)=E; if (X是解结点) /x为叶结点 U=min(cost(X),u); leaf=x; /方案的叶结点存储在leaf中 print(”least cost=,u); while (leaf0) /输出最优解方案 print(leaf); leaf=

25、parent(leaf); 第32页/共74页33 找最小成本的LC分支-限界算法框架与FIFO分支-限界算法框架结构大致相同，只是扩展结点的顺序不同，因而存储活结点的数据结构不同。 FIFO分支-限界算法用队存储活结点，LC分支-限界算法用堆存储活结点，以保证比较优良的结点先被扩展。且对于LC分支-限界算法，一旦扩展到叶结点就已经找到最优解，可以停止搜索。2 LC分支-限界算法框架第33页/共74页342 例9.2 布线问题 布线问题：如图所示，印刷电路板将布线区域划分成n*m个方格。精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线。

26、为了避免线路相交，已经布线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。abab第34页/共74页352 例9.2 布线问题-问题分析2 1 2 3 4 514 5 62 15 6 73 26 7 87ab 根据布线方法要求，除边界处或已布线处，每个E-结点分支扩充的方向有4个：上、下、左、右。即：一个E-结点扩充后最多产生4个活结点。从图不难发现：最短的布线方案是不唯一的。 第35页/共74页362 例9.2 布线问题-算法设计 (1)初始化部分 开辟m*n的二维数组模拟布线区域，初始值均置为-1，表示没有被使用。已使用的位置，通过键盘输入其下标，将对应值置为0。输入方格a、b的下标，

27、存储在变量中。第36页/共74页372 例9.2 布线问题-算法设计 (2)可布线位置的识别 不可布线的位置有两种情况： a. 已占用结点，标识为0； b. 布线区域外的结点，结点下标(i,j)满足： not (i0 and i0 and j=n)2 1 2 3 4 5 14 5 62 15 6 73 26 7 87ab把布线区域扩充为(m+2)*(n+2)数组，边界置占用状态，就无需做越界的检查了。用空间换取时间 第37页/共74页38struct node int x, y; start, end;int a100100;teamtype q; /队列的类型main( ) int i, j

28、, k; struct node temp; print(“How many row?”); input(m); print(“How many col?”); input(n); print(“input start and end?”); input(start.x, start.y);input(end.x, end.y); if (start.x=end.x or start.y=end.y) error( ); if (start.xm or start.yn) error( ); if (end.xm or end.yn) error( ); for (i=1;i=m;i+) fo

29、r (j=1;j=n;j+) aij=-1; for (i=1;i=m;i+) ai0=ain+1=0; /设置边界 for (j=0;j=n+1;j+) a0j=am+1j=0; print(“input the node of tie-up”); input(temp.x,temp.y); /设置占用区域 while (x0) axy=0; input(temp.x,temp.y); k=search( ); if (k=-1) print(“No result”); else output(k); 2 例9.2 布线问题-算法实现第38页/共74页39int search( ) stru

30、ct node temp,temp1; inq(start); k=0; while (not empty(q) temp=outq(q); if (atemp.x-1temp.y=-1) /上 temp1.x=temp.x-1; temp1.y=temp.y; k=k+1; atemp1.xtemp1.y=k; if (temp1.x=end.x and temp1.y=end.y) return(k); inq(temq1); if (atemp.x+1temp.y=-1) /下 temp1.x=temp.x+1; temp1.y=temp.y; k=k+1; atemp1.xtemp1.

31、y=k; if (temp1.x=end.x and temp1.y=end.y) return(k); inq(temq1); if (atemp.xtemp.y-1=-1) /左 temp1.x=temp.x; temp1.y=temp.y-1; k=k+1; atemp1.xtemp1.y=k; if (temp1.x=end.x and temp1.y=end.y) return(k); inq(temq1); if (atemp.xtemp.y+1=-1) /右 temp1.x=temp.x; temp1.y=temp.y+1; k=k+1; atemp1.xtemp1.y=k; i

32、f (temp1.x=end.x and temp1.y=end.y) return(k); inq(temq1); return(-1);2 例9.2 布线问题-算法实现第39页/共74页40output(int k) int x,y; print(“(”,end.x,“,”,end.y,“)”); x=end.x; y=end.y; while (k2) k=k-1; if (ax-1y=k) x=x-1;print(“(”,x,“,”,y,“)”);continue; if (ax+1y=k) x=x+1;print(“(”,x,“,”,y,“)”);continue; if (axy-

33、1=k) y=y-1;print(“(”,x,“,”,y,“)”);continue; if (axy+1=k) y=y+1;print(“(”,x,“,”,y,“)”);continue; print(“(”,start.x,“,”,start.y,“)”);2 例9.2 布线问题-算法实现第40页/共74页412 例9.3 单源最短路径问题-问题描述 下面以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。 第41页/共74页422 例9.3 单源最短路径问题-问题分析 下图是用优先队列式分支限界法解有向图G的单

34、源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。第42页/共74页432 例9.3 单源最短路径问题-问题分析 单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。 优先级是结点所对应的当前路长。第43页/共74页442 例9.3 单源最短路径问题-算法思想 算法从图G的源顶点s和空优先队列开始。结点s被扩展后，其儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。若从当前扩展结点i到顶点j有边可达且从源出发，途经顶点i再到顶点j的路径长度小于当前最优路径长度，则将该顶点作为

35、活结点插入到活结点优先队列中。扩展过程一直继续到活结点优先队列为空时为止。第44页/共74页452 例9.3 单源最短路径问题-数据结构设计int c100100; /图G的邻接矩阵int n; /图G的顶点数int prev ; /前驱顶点数组int dist ; /最短距离数组struct MinHeapNode int i; / 顶点编号 int length; ; / 当前路长：从源到该顶点的距离 用最小堆表示活结点优先队列第45页/共74页46void ShortestPaths(int v) MinHeapNode H1000; /定义最小堆的容量为1000 MinHeapNode

36、 E; /定义源为初始扩展结点 E.i=v; E.length=0; distv=0; while (not Empty(H) /搜索问题的解空间 for (int j=1; j=n; j+) if (cE.ijinf)&(E.length+cE.ijbestn时，右子树中可能含有最优解，此时将右儿子结点加入子集树中并插入活结点优先队列中。第52页/共74页532 例9.4 最大团问题-算法思想l算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。l对于子集树中的叶结点，有uncn。此时活结点优先队列中剩余结点的un值均不超过当前扩展结点的un值

37、，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。 第53页/共74页542 例9.4 最大团问题-数据结构设计struct bbnode bbnode *parent; /指向父结点的指针 int LChild; ; /左儿子结点标志struct CliqueNode bbnode *ptr; /指向活结点在子集树中相应结点的指针 int cn; /当前团的顶点数 int un; /当前团最大顶点数的上界 int level; ; /结点在子集树中所处的层次 int a ; /图G的邻接矩阵int n; /图G的顶点数 CliqueNode MaxHeap1000; /定义最大堆

38、的容量为1000第54页/共74页55int MaxClique(int bestx ) bbnode *E=null; int i=1,cn=0,bestn=0; /初始化,i表示扩展结点的层次 /搜索子集空间树 while (i!=n+1) /非叶结点 /检查顶点i与当前团中其他顶点之间是否有边相连 int OK=1; bbnode *B=E; for(int j=i-1;j0;B=B.parent,j-) if (B.LChild&aij=0) OK=0;break; if (OK) /左儿子结点为可行结点 if (cn+1bestn) bestn=cn+1; AddLiveNo

39、de(H,cn+1,cn+n-i+1,i+1,E,1); if (cn+n-i=bestn) /右子树可能含最优解 AddLiveNode(H,cn,cn+n-i,i+1,E,0); CliqueNode N; /取下一扩展结点 H.DeleteMax(N); /堆非空 EN.ptr; cn=N.cn; i=N.level; for(int j=n;j0;j-) bestxj=E.LChild; E=E.parent; /构造当前最优解 return bestn;2 例9.4 最大团问题-算法第55页/共74页56void AddLiveNode(MaxHeap &H, int cn,

40、 int un, int level, bbnode E,int ch) /将活结点加入到子集空间树中并插入最大堆中 bbnode *b=new bbnode; b.parent=E; b.LChild=ch; CliqueNode N; N.cn=cn; N.ptr=b; N.un=un; N.level=level; H.Insert(N); 2 例9.4 最大团问题-算法第56页/共74页572 例9.5 0-1背包问题-问题分析n如何实现？ 对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。n 优先级如何确定？ 在优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩

41、下的最大单位重量价值的物品装满剩余容量的价值和。第57页/共74页582 例9.5 0-1背包问题-算法思想 算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。第58页/共74页592 例9.5 0-1背包问题-上界函数Typep Bound(int i) Typew cleft=c-cw; /剩余容量 Typep b=cp; /价值上界 while(i=n&wi=cleft) /n表示物品总

42、数 cleft-=wi; /wi表示i所占空间 b+=pi; /pi表示i的价值 i+; if (i=n) b+=pi/wi*cleft; /装填剩余容量装满背包 return b; /b为上界函数第59页/共74页602 例9.5 0-1背包问题-数据结构设计struct bbnode bbnode *parent; /指向父结点的指针 int LChild; ; /左儿子结点标志struct HeapNode bbnode *ptr; /指向活结点在子集树中相应结点的指针 Typep uprofit; /结点的价值上界 Typep profit; /结点所相应的价值 Typew weigh

43、t; /结点所相应的重量 int level; ; /结点在子集树中所处的层次 HeapNode MaxHeap1000; /定义最大堆的容量为1000int ID; float d; /单位重量价值第60页/共74页612 例9.5 0-1背包问题-算法实现Typep MaxKnapsack( ) bestx=new intn+1; int i=1;E=0;cw=cp=0; /初始化 Typep bestp=0; /当前最优值 Typep up=Bound(1); /价值上界 while (i != n+1) / 非叶结点 Typew wt = cw + wi; if (wt bestp)

44、bestp=cp+pi; AddLiveNode(up, cp+pi, cw+wi, 1, i+1); up = Bound(i+1); if (up=bestp) / 右子树可能含最优解 AddLiveNode(up, cp, cw, 0, i+1); HeapNode N; DeleteMax(N); /取下一个扩展节点 E=N.ptr; cw=N.weight; cp=N.profit; up=N.uprofit; i=N.level; for(int j=n;j0;j-) bestxj=E.LChild; E=E.parent; /构造最优解 return cp;第61页/共74页62

45、2 例9.5 0-1背包问题-算法实现void AddLiveNode(Typep up,Typep cp,Typew cw,int ch,int lev) bbnode *b=new bbnode; b.parent=E; b.LChild=ch; HeapNode N; N.upprofit=up; N.profit=cp; N.weight=cw; N.level=lev; N.ptr=b; H.Insert(N);第62页/共74页632 例9.6 旅行售货员问题 某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路

46、线，使总的路程(或总旅费)最小。 路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中每个顶点在内的一条回路。周游路线的费用是该路线上所有边的费用之和。第63页/共74页64 旅行售货员问题的解空间可以组织成一棵排列树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。2 例9.6 旅行售货员问题-问题分析问题一：解空间？第64页/共74页652 例9.6 旅行售货员问题-问题分析 要找的是最小费用旅行售货员回路，所以选用最小堆表示活结点优先队列。每个结点子树费用的下界作为优先级。问题二：优先队列如何确定？优先级？第65页

47、/共74页662 例9.6 旅行售货员问题-算法思想算法开始时创建一个最小堆，用于表示活结点优先队列。堆中每个结点的子树费用的下界lcost值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用出边并用minout记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。如果每个顶点都有出边，则根据计算出的minout作算法初始化。 第66页/共74页672 例9.6 旅行售货员问题-算法思想 算法利用while循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分2种情况进行处理： 1、考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。 2、当sn-2时，算法依次产生当前扩展结点的所有儿子结点。当前扩展结点所相应的路径是x0:s，其