计算机算法分析与设计(研究生)全册配套课件(二).ppt

1、计算机算法分析与设计(研究生)全册配套课件(二) 0-1背包问题(0-1Knapsack Problem )设有n个物体和一个背包,物体i的重量为wi价值为pi背包的载荷为M,若将物体i(1 i n,)装入背包,则有价值为pi .目标是找到一个方案,使得能放入背包的物体总价值最高算法设计与分析算法设计与分析 回溯法回溯法若取W= (20,15, 15), P= (40,25, 25), C=30例例 题题有限离散问题总可以用穷举法求得问题的全部有限离散问题总可以用穷举法求得问题的全部. .例如 取N=3 , 问题所有可能的解为(解空间): (0, 0, 0), (0, 0, 1), (0, 1

2、, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1) 可表示为一棵3层的完全正则二叉树时间复杂性: O(2n)求解过程相当于在树中搜索满足条件的叶结点.第五章. 回溯法回溯法 (Back tracking)设问题的解可表示为n元组(x1, x2, xn), xisi , si为有限集, n元组的子组(x1, x2, xi) i 回溯法回溯法E= E= (x1, x2, xn), xi si , si为有限集 称为问题的解空间解空间. .约束条件隐约束:元组的分量间满足函数关系f(x1,.xn)显约束:每个xi 的范围都给定的约束

3、.满足显约束的全体向量构成解空间.例例 题题算法设计与分析算法设计与分析 回溯法回溯法1.子集树子集树:当解向量为不定长n元组时, 树中从根至每一结点的路径集合构成解空间.树的每个结点称为一个解状态,有儿子的结点称为可扩展结点,叶结点称为终止结点, 若结点v对应解状态(x1, x2, xi),则其儿子对应扩展的解状态(x1, x2, xi, xi+1 ).满足所有约束条件的解状态结点称为回答结点.2.排序树排序树:当解向量为定长n元组时, 树中从根至叶结点的路径的集合构成解空间.树的每个叶结点称为一个解状态.解空间树构造:搜索按深度优先策略从根开始, 当搜索到任一结点时,判断该点是否满足约束条

4、件D(剪枝函数),满足则继续向下深度优先搜索,否则跳过该结点以下的子树(剪枝),向上逐级回溯.搜索过程搜索过程:求解过程可表示为在一棵解空间树 作 深度优先搜索深度优先搜索. 0-1背包问题设有n个物体和一个背包,物体i的重量为wi价值为pi背包的载荷为M,若将物体i(1 i n,)装入背包,则有价值为pi .目标是找到一个方案,使得能放入背包的物体总价值最高算法设计与分析算法设计与分析 回溯法回溯法 设N=3, W=(20,15,15), P=(40, 25, 25), C=30例例 题题x1=123x2=233x3=3ABCDEFGH子集树子集树排序树排序树中间结点可以是解,例如,只装物体

5、1,B是解只有叶结点可以是解xi表示第i次选择物体号Procedure BACKTRACK(n)； k:=l； repeat if TK (x1,x2,.xK-1 )中的值未取遍 then xK:TK (x1，x2，., x K-1 )中未取过的一个值； if BK (x1, x2, ., x K) then /状态结点(x1,.xk)被激活 if kn then output(x1, x2, ., xk) /输出一个回答结点 e1se k:k + l； /深度优先 e1se k:k-l； /回溯 until k0；/回溯到根结点end；BACKTRACK算法模式算法模式回溯法解题步骤:1).

6、针对所给问题,定义问题的解空间2).确定解空间结构.3).以深度优先方式搜索解空间.算法设计与分析算法设计与分析 回溯法回溯法递归回溯算法设计与分析算法设计与分析 回溯法回溯法void Backtrack(int t) if (t n) Output(x); else / f(n,t): leftChild; g(n,t): rightChild for (int i = f(n,t); i 0) if (f(n,t) = g(n,t) /对剩下子树处理 for (int i = f(n,t);i 回溯法回溯法 子集和子集和 例如例如 设n=4, W=(11,13, 24, 7), M=31

7、满足约束条件的子集为(11,13,7), 和 (24, 7), 5.2 子集和问题 S=(1, 2, 4), 和 S=(3, 4), jiix1约束条件x1=w1w2 w3w4x2=w2 w3 w4w4w4w4w3w3 w4w4w4jiix1 + xj+1 M+ Mnjiiw1) )( (选xj+1代表的分枝不超界选xj+1代表的分枝最终能够达到M元素不能重复选取算法设计与分析算法设计与分析 回溯法回溯法算法思路算法思路2 2:问题的解可表示为n元向量x1, x2, . xn , xi=1或0 则问题的解空间树为排序树Mkwxiwkii) 1()(1约束条件: 子集和子集和+ Mnjiiw1)

8、 )( (jiixiw1) )( ( n=4, W=(11,13, 24, 7), M=31/即使选了下一个,和不超界,所以,选与不选的/子树都可以展开/未来值有可能使累和达到M procedure sumofsub(s，k，r)； 正实数组Wl.n，布尔数组Xl.n).M，n：均为全局量。 Wl.n按非降次序排列，s= WjXj，r= Wj 假定WlM及 WiM Xk:=1； lf s+Wk=M then Print the result X1.k else if s+Wk+Wk+1M and s+Wk+1M then Xk:=0; sumofsub(s, k+1，r-Wk )； nkj11

9、kjnk 1算法复杂性算法复杂性:约为穷举法的1/3子集合问题回溯算法(排列树)算法设计与分析算法设计与分析 回溯法回溯法 子集合子集合/进右子树及条件(不选后不超界,且有达到M的可能)/进左子树及条件(选后不超界,而达到M的可能性在进入第k层时已保证)算法设计与分析算法设计与分析 回溯法回溯法 子集合子集合n=6,m=30,w=5,10,12,13,15,18时由算法生成的部分解空间树子集和s剩余元素之和r当前层次k算法设计与分析算法设计与分析 回溯法回溯法 n后问题5.3 装载问题问题描述问题描述:n个集装箱装到2艘载重量分别为c1,c2的货轮,其中集装箱i的重量为wi且 问题要求找到一个

10、合理的装载方案可将这n个货箱装上这2艘轮船。211ccwnii例如 当n=3, c1=c2=50, w=10, 40, 40, 可将货箱1和2装到第一艘船上;货箱3装到第二艘船上; 若w=20, 40, 40, 则无法将全部货箱装船.当当 时问题等价于子集和问题时问题等价于子集和问题; ; 当当c1=c2c1=c2且且 时时问题等价于划分问题问题等价于划分问题. .211ccwnii112cwnii若装载问题有解, 采用如下策略可得一个最优装载方案:(1)将第一艘轮船尽可能装满; (2)将剩余的货箱装到第二艘轮船上。将第一艘船尽可能装满等价于如下0-l背包问题:niiixw1m ma ax x

11、12cxwniiixi0,1, 1in可采用动态规划求解, 其时间复杂性为:O(2n)算法设计与分析算法设计与分析 回溯法回溯法 装载问题装载问题算法思路算法思路:用排序树表示解空间,则解为n元向量x1, . ,xn , xi0, 1 jiiixw1 + wj+1 c1约束条件:由于是最优化问题, 可利用最优解性质进一步剪去不含最优解的子树:设 bestw: 当前最优载重量, cw = : 当前扩展结点的载重量 ; r = : 剩余集装箱的重量;jiiixw1njijw1cw+r bestwjiiixw1 + wj+1 c1选wj+1就超界,所以,左分枝不能选剪左子树条件:剪右子树条件:不选w

12、j+1,结果无法达到最优,所以右分枝不能选算法设计与分析算法设计与分析 回溯法回溯法 装载问题装载问题例如 n=4, c1=12, w=8, 6, 2, 3.cw=0cw=8cw=14cw=8cw=10cw=13bestw=10cw=8bestw=11cw=0cw=6cw=8bestw=11算法设计与分析算法设计与分析 回溯法回溯法 装载问题装载问题templatevoid Loading:Backtrack(int i) / /搜索第i层结点 if (in) /到达叶结点 bestw=cw； return； /搜索子树 r - = wi; if (cw+wi bestw) /xi=0 Bac

13、ktrack(i+1)； r+=wi; /复原 template Type Maxloading(type w, type c, int n,) loading X； /初始化X X. w=w; /集装箱重量数组 X. c=c; /第一艘船载重量 X. n=n；/集装箱数 X. bestw=0; /当前最优载重 X. cw=0;/当前载重量 X. r=0; /剩余集装箱重量 for (int i=1; i 回溯法回溯法 n后问题53 批处理作业调度批处理作业调度问题描述问题描述:给定n个作业的集合J=(J1, J2, . , Jn)。每一作业Ji都有两项任务要分别在2台机器上完成. 每一作业须

14、先由机器l处理, 再由机器2处理. 设tji是作业Ji在机器j上的处理时间, i=1,.,n, j=1, 2.Fji是作业Ji在机器j上完成处理的时间. 所有作业在机器2上完成时间和: f=F2i 称为该作业调度的完成时间和完成时间和.对于给定的J, 要求制定一个最佳作业调度方案, 使完成时间和最小.算法思路算法思路:设解为n元向量x1,. ,xn , xi1,.n, 用排序树表示解空间 约束条件: 当i j , xi xj (元素不能重复选取) 例例 题题例例 题题算法设计与分析算法设计与分析 回溯法回溯法 作业调度void Flowshop: :Backtrack(int i) if (i

15、n) for(int j = 1;j = n; j+) bestxj = xj; bestf = f; else for (int j = i; j fl)?f2i-1:fl) +Mxj2; f+= f2i; if (f bestf) Swap(xi, xj); Backtrack(i + 1 ); Swap(xi, xj ); fl - = Mxj1; f- = f2i ;int Flow(int * M, int n, int bestx ) int ub = 32767; Flowshop X; X.x = new int n+ 1; /当前调度 X.f2 = new intn+ l;

16、X.M = M; /各作业所需处理时间 X.n= n; /作业数 X.bestx = bestx; /当前最优调度 X. bestf = ub; /当前最优调度时间 X.fl = 0; /机器2完成处理时间 X.f = 0; /机器1完成处理时间 for(int i = 0;i 回溯法回溯法 作业调度 机器1 机器2 作业1 2 1 作业2 3 1 作业3 2 3 tji 这三个作业的6种可能调度方案是: 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, l, 2; 3, 2, l;相应的完成时间和分别是: 10, 8, 10，9，7，8。最佳调度: 3, 1, 2

17、; 完成时间为7。机器1机器2J1J1J3J3J2J2调度1,3,2例例 题题机器1机器2J3J3J2J2调度3,1,2J1J1算法设计与分析算法设计与分析 回溯法回溯法 作业调度 机器1 机器2 作业1 2 1 作业2 3 1 作业3 2 3 tji 这三个作业的6种可能调度方案是: 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, l, 2; 3, 2, l;相应的完成时间和分别是: 10, 8, 10，9，7，8。最佳调度: 3, 1, 2; 完成时间为7。x1=J1J2J3x2=J2J3J1x3=J3ABCDEFJ2bestx=7J3EFJ3J1J2EFJ2

18、J2J1例例 题题算法思路算法思路:将棋盘从左至右,从上到下编号为1,.,n,皇后编号为1,.,n. 设解为(x1, ., xn) , xi为皇后i的列号,且xi位于第i行.解空间:E=(x1,., xn) | xiSi, i=1,.,n, Si=1, ., n,1 i n解空间为排列树.其约束集合D为 1) xi xj 2) xi-i xj-j 3) xi+i xj+j皇后i,j不在同一斜线上算法设计与分析算法设计与分析 回溯法回溯法 n后问题5.3 n后问题皇后i,j不在同一列上问题描述问题描述:nxn棋盘上放置n个皇后使得每个皇后互不受攻击. 即任二皇后不能位于同行同列和同一斜线上. 如

19、四后问题的解算法设计与分析算法设计与分析 回溯法回溯法 n后问题回溯求解四后问题过程中被激活过的结点算法设计与分析算法设计与分析 回溯法回溯法 n后问题算法设计与分析算法设计与分析 回溯法回溯法 n后问题bool Queen: Place(int k) for (int j = 1; j n) sum+; else for (int i=1;i = n;i+) xt = i; if (Place(t) Backtrack(t + 1) intn Queen(int n) QueenX； /初始化X X. n=n；/皇后个数 X. sum=0； int*p=new int n+1； for(in

20、t i=0；i 回溯法回溯法 最大团问题设无向图G=(V, E), UV, 若对任意u, vU, 有(u,v) E, 则称U是G的一个完全子图。G的完全子图U是G的一个团团(完备子图完备子图)当且仅当U不包含在G的更大的完全子图中。G的最大团最大团是G中所含顶点数最多的团。如果UV,且对任意u,vU,(u,v )E, 则称U是G的一个空子图空子图。G的空子图U是G的一个独立集独立集当且仅当U不包含在G的更大的空子图中。G的最大独立集最大独立集是G中所含顶点数最多的的独立集。*若U是G的一个完全子图,则U是G的补图 的一个独立集.5.7 最大团问题最大团问题 问题描述:在G 中找一个最大团. G

21、例如最大团:1, 2, 5, 1, 4, 5, :2, 3, 5G的补图基本概念设无向图G=(V, E), |V|=n,用邻接矩阵a表示图G, 问题的解可表示为n元向量x1, . xn , xi0,1. 问题的解空间用排序树表示.约束条件:x1,x2,.xixi+1是团.目标函数限界:设 bestn: 已求出的最大团的尺寸; cn : 当前团的尺寸 ; r :剩余结点数目;当 cn+r bestn 时, 将cn对应右子树剪去。.算法设计与分析算法设计与分析 回溯法回溯法 最大团问题 算法思路算法思路.101101算法设计与分析算法设计与分析 回溯法回溯法 最大团问题 最大团问题的回溯算法voi

22、d clique:Backtrack(int i) if (cn+n- ibestn) if (in) /找到更大团,更新 xi = 0; /进入右子树 for (int j=1; j=n；j+) Backtrack(i + 1); bestxj = xj; bestn = cn; return; /检查顶点i是否与当前团相连 int OK = 1; for(int j =1; j 回溯法回溯法 着色问题图的m色判定问题: 给定无向连通图G和m种颜色。用这些颜色为图G的各顶点着色. 问是否存在着色方法, 使得G中任2邻接点有不同颜色。图的m色优化问题:给定无向连通图G,为图G的各顶点着色, 使

23、图中任2邻接点着不同颜色,问最少需要几种颜色。所需的最少颜色的数目m称为该图的色数。5.8 图的图的m m着色问题着色问题 问题描述若图G是个平面图,则它的色数不超过4色(4色定理). 4色定理的应用:在一个平面或球面上的任何地图能够只用4种颜色来着色使得相邻的国家在地图上着有不同颜色4321512345a).a).将将G的结点按照度数递减的次序排列的结点按照度数递减的次序排列. . b).b).用第一种颜色对第一个结点着色用第一种颜色对第一个结点着色, ,并按照结点排列的次序并按照结点排列的次序 对与前面着色点不邻接的每一点着以相同颜色对与前面着色点不邻接的每一点着以相同颜色. .c).c)

24、.用第二种颜色对尚未着色的点重复步骤用第二种颜色对尚未着色的点重复步骤b).b).用第三种颜色用第三种颜色 继续这种作法继续这种作法, , 直到所有点着色完为止直到所有点着色完为止. . 任意图的着色任意图的着色Welch PowellWelch Powell法法a1a5a4a6a2a3a7a8 排序排序: :a5, a3, a7, a1, a2, a4, a6, a8 着第一色着第一色: a5, a1,着第二色着第二色:a3,a4, a8着第三色着第三色:a7, a2, a6图论图论 对偶图与着色对偶图与着色算法设计与分析算法设计与分析 回溯法回溯法 图的m着色设图G=(V, E), |V|

25、=n, 颜色数= m, 用邻接矩阵a表示G, 用整数1, 2m来表示m种不同的颜色。顶点i所着的颜色用xi表示。问题的解向量可以表示为n元组x= x1,.,xn . xi1,2,.,m,解空间树为排序树,是一棵n+1层的完全m叉树.在解空间树中做深度优先搜索, 约束条件: xi xj, 如果aji=1. 算法思路n=3, m=3n=3, m=3时的解空间树时的解空间树132011101110a=算法设计与分析算法设计与分析 回溯法回溯法 着色问题 int mColoring(int n, int m, int *a ) Color X； /初始化X Xn=n； /图的顶点数 Xm=m /可用颜

26、色数 Xa=a； /图的邻接矩阵 XSum=0; /已找到的着色方案数 int*p=new int n+1； for (int i=0；i=n；i+) pi=0； X. x=p /当前解； X. Backtrack(1)； delete p； returnXsum； 算法复杂性算法复杂性: 着色问题回溯回溯算法 bool Color:Ok(int k) /检查颜色可用性 for(int j=1；jn) sum+； for(int i=1; i=n; i+) cout xi ； cout endl ； else for ( int i=1; i=m; i+) xt=i; if (Ok(t) Ba

27、cktrack( t+1); M叉树的剪枝条件3132学习要点学习要点理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架（1）队列式(FIFO)分支限界法（2）优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。（1）单源最短路径问题（2）装载问题；（3）布线问题（4）0-1背包问题；（5）最大团问题；（6）旅行售货员问题（7）电路板排列问题（8）批处理作业调度问题335.1 分支限界法的基本思想分支限界法与回溯法（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解

28、。 （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 345.1 分支限界法的基本思想 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。355.1 分支限界法的基本思想常见的两种

29、分支限界法（1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。365.2 单源最短路径问题1. 问题描述 下面以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。 375.2 单源最短路径问题1. 问题描述 下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。385.2 单源最短路径问题2. 算法思想 解单源最

30、短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。 算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。395.2 单源最短路径问题3. 剪枝策略 在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，

31、则算法剪去以该结点为根的子树。 在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。 405.2 单源最短路径问题 while (true) for (int j = 1; j = n; j+) if (cE.ijinf)&(E.length+cE.ijdistj) / 顶点i到顶点j可达，且满足控制约束 distj=E.length+cE.ij; prevj=E.i; / 加入活结点优先队列 MinHeapNode N; N.i=j; N.length=distj; H.Ins

32、ert(N); try H.DeleteMin(E); / 取下一扩展结点 catch (OutOfBounds) break; / 优先队列空 顶点顶点I I和和j j间有边，且此间有边，且此路径长小于原先从原点路径长小于原先从原点到到j j的路径长的路径长 415.3 装载问题1. 问题描述有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且211ccwnii装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装

33、满；(2)将剩余的集装箱装上第二艘轮船。 425.3 装载问题2. 队列式分支限界法 在算法的while循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。 活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。435.3 装载问题2. 队列式分支限界法whi

34、le (true) / 检查左儿子结点 if (Ew + wi = c) / xi = 1 EnQueue(Q, Ew + wi, bestw, i, n); / 右儿子结点总是可行的 EnQueue(Q, Ew, bestw, i, n); / xi = 0 Q.Delete(Ew); / 取下一扩展结点 if (Ew = -1) / 同层结点尾部 if (Q.IsEmpty() return bestw; Q.Add(-1); / 同层结点尾部标志 Q.Delete(Ew); / 取下一扩展结点 i+; / 进入下一层 445.3 装载问题3. 算法的改进 节点的左子树表示将此集装箱装上船

35、，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+rbestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。 另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。455.3 装载问题3. 算法的改进/ 检查左儿子结点 Type wt = Ew + wi; / 左儿子结点的重量 if (wt bestw) bestw = wt; / 加入活结点队列 if (i bestw & i 0; j-) bestxj = bestE-LChild; bestE = bestE-pa

36、rent; 485.3 装载问题5. 优先队列式分支限界法 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。 优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。 在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。 495.4 布线问题1. 算法思想 解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点。与

37、该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。 接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。即加入剪枝的广度优先搜索。505.4 布线问题Position offset4; offset0.row = 0; offset0.col = 1; / 右 offset1.row = 1; offset1.col = 0; / 下 offset2.row = 0; offset2.col

38、= -1; / 左 offset3.row = -1; offset3.col = 0; / 上定义移动方向的定义移动方向的相对位移相对位移 for (int i = 0; i = m+1; i+) grid0i = gridn+1i = 1; / 顶部和底部 for (int i = 0; i = n+1; i+) gridi0 = gridim+1 = 1; / 左翼和右翼设置边界的围墙设置边界的围墙515.4 布线问题for (int i = 0; i NumOfNbrs; i+) nbr.row = here.row + offseti.row; nbr.col = here.col

39、+ offseti.col; if (gridnbr.rownbr.col = 0) / 该方格未标记 gridnbr.rownbr.col = gridhere.rowhere.col + 1; if (nbr.row = finish.row) & (nbr.col = finish.col) break; / 完成布线 Q.Add(nbr); 找到目标位置后，可以通过回溯方法找到这条最短路径。525.5 0-1背包问题算法的思想 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。 在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量

40、价值的物品装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。535.5 0-1背包问题上界函数while (i = n & wi = cleft) / n表示物品总数，cleft为剩余空间 cleft -= wi; /wi表示i所占空间 b += pi; /pi表示i的价值 i+; if (i = n) b += pi / wi * cleft; / 装填剩余容量装满背包ret

41、urn b; /b为上界函数545.5 0-1背包问题 while (i != n+1) / 非叶结点 / 检查当前扩展结点的左儿子结点 Typew wt = cw + wi; if (wt bestp) bestp = cp+pi; AddLiveNode(up, cp+pi, cw+wi, true, i+1); up = Bound(i+1); / 检查当前扩展结点的右儿子结点 if (up = bestp) / 右子树可能含最优解 AddLiveNode(up, cp, cw, false, i+1); / 取下一个扩展节点（略）分支限界搜索分支限界搜索过程过程555.6 最大团问题

42、给定无向图G=(V，E)。如果UV，且对任意u，vU有(u，v)E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。 下图G中，子集1，2是G的大小为2的完全子图。这个完全子图不是团，因为它被G的更大的完全子图1，2，5包含。1，2，5是G的最大团。1，4，5和2，3，5也是G的最大团。 1. 问题描述565.6 最大团问题2. 上界函数用变量cliqueSize表示与该结点相应的团的顶点数；level表示结点在子集空间树中所处的层次；用cliqueSize +n-level+1作为顶点数上界upperSize的值。 在

43、此优先队列式分支限界法中，upperSize实际上也是优先队列中元素的优先级。算法总是从活结点优先队列中抽取具有最大upperSize值的元素作为下一个扩展元素。 575.6 最大团问题3. 算法思想 子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0。 算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其它顶点之间是否有边相连。当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。 接 着 继 续 考 察 当 前 扩 展 结

44、点 的 右 儿 子 结 点 。 当upperSizebestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。585.6 最大团问题3. 算法思想 算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。 对于子集树中的叶结点，有upperSizecliqueSize。此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。 595.7 旅行售货员问题1. 问题描述 某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费

45、)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。 路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。 旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。 605.7 旅行售货员问题2. 算法描述 算法开始时创建一个最小堆，用于表示活结点优先队列。堆中每个结点的子树费用的下界lcost值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用出边并用minout记录。如

46、果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。如果每个顶点都有出边，则根据计算出的minout作算法初始化。 算法的while循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分2种情况进行处理：615.7 旅行售货员问题2. 算法描述 1、首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。 2、当sn-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是x0:s，其可行儿子结点是从剩余顶点xs+1:n-1中选取的顶点xi

47、，且(xs，xi)是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x0:s，xi)的费用cc和相应的下界lcost。当lcostbestc时，将这个可行儿子结点插入到活结点优先队列中。 625.7 旅行售货员问题2. 算法描述 算法中while循环的终止条件是排列树的一个叶结点成为当前扩展结点。当s=n-1时，已找到的回路前缀是x0:n-1，它已包含图G的所有n个顶点。因此，当s=n-1时，相应的扩展结点表示一个叶结点。此时该叶结点所相应的回路的费用等于cc和lcost的值。剩余的活结点的lcost值不小于已找到的回路的费用。它们都不可能导致费用更小的回路。因此已

48、找到的叶结点所相应的回路是一个最小费用旅行售货员回路，算法可以结束。 算法结束时返回找到的最小费用，相应的最优解由数组v给出。 635.8 电路板排列问题算法描述 算法开始时，将排列树的根结点置为当前扩展结点。在do-while循环体内算法依次从活结点优先队列中取出具有最小cd值的结点作为当前扩展结点，并加以扩展。 首先考虑s=n-1的情形，当前扩展结点是排列树中的一个叶结点的父结点。x表示相应于该叶结点的电路板排列。计算出与x相应的密度并在必要时更新当前最优值和相应的当前最优解。 当sn-1时，算法依次产生当前扩展结点的所有儿子结点。对于当前扩展结点的每一个儿子结点node，计算出其相应的密

49、度node.cd。当node.cdbestd时，将该儿子结点N插入到活结点优先队列中。645.8 电路板排列问题算法描述do / 结点扩展 if (E.s = n - 1) / 仅一个儿子结点 int ld = 0; / 最后一块电路板的密度 for (int j = 1; j = m; j+) ld += BE.xnj; if (ld bestd) / 密度更小的电路板排列 delete bestx; bestx = E.x; bestd = max(ld, E.cd); S=n-1S=n-1的情况，计算出的情况，计算出此时的密度和此时的密度和bestdbestd进进行比较。行比较。655.

50、8 电路板排列问题算法描述else / 产生当前扩展结点的所有儿子结点 for (int i = E.s + 1; i = n; i+) BoardNode N; N.now = new int m+1; for (int j = 1; j = m; j+) / 新插入的电路板 N.nowj = E.nowj + BE.xij; 665.8 电路板排列问题int ld = 0; / 新插入电路板的密度 for (int j = 1; j 0 & totalj != N.nowj) ld+; N.cd = max(ld, E.cd); if (N.cd bestd) / 可能产生更好的叶结点 N