算法设计-5.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, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (

2、1, 1, 1),可表示为一棵3层的完全正则二叉树,时间复杂性: O(2n),求解过程相当于在树中搜索 满足条件的叶结点.,第五章. 回溯法 (Back traiking),算法设计与分析 回溯法,学习要点: 理解回溯法的深度优先搜索策略。 掌握用回溯法解题的算法框架 （1）递归回溯最优子结构性质 （2）迭代回溯贪心选择性质 （3）子集树算法框架 （4）排列树算法框架,第五章. 回溯法 (Back traiking),算法设计与分析 回溯法,通过应用范例学习回溯法的设计策略: （1）装载问题； （2）批处理作业调度； （3）符号三角形问题 （4）n后问题； （5）0-1背包问题； （6）最大团

3、问题； （7）图的m着色问题 （8）旅行售货员问题 （9）圆排列问题 （10）电路板排列问题 （11）连续邮资问题,第五章. 回溯法 (Back traiking),设问题的解可表示为n元组(x1, x2, xn), xisi , si为有限集, n元组的子组(x1, x2, xi) in 应满足一定的约束条件D. 设已有满足约束条件的部分解(x1, x2, xi), 添加xi+1 si+1, 若(x1, x2, xi ,xi+1 )满足约束条件, 则继续添加xi+2 ; 若所有可能的xi+1 si+1均不满足约束条件,则去掉xi , 回溯到(x1, x2, xi-1), 添加尚未考虑过的xi

4、 , 如此反复进行,直到(x1, x2, xk) kn满足所有的 约束条件或证明无解.,5.1 基本思想,算法设计与分析 回溯法,E= (x1, x2, xn), xi si , si为有限集 称为问题的解空间.,约束条件,隐约束:元组的分量间满足函数关系f(x1,.xn),显约束:每个xi 的范围都给定的约束.满足显约束的全体向量构成解空间.,显示约束条件是限定每个x只从一个给定的集合上取值。显式约束条件常见的例子是： Xi=0或Xi =1 即 Si=0，1 子集树 lixiui 即 Si =a：liaui 排列树 这些显式约束条件可以与所求解的问题的实例I有关，也可以无关。满足显式约束的所

5、有元组确定I的一个可能的解空间。 隐式约束条件则规定I的解空间中那些实际上满足规范函数的元组。因此，隐式约束描述了xi 必须彼此相关的情况。,示例：8 皇后问题可以表示成8-元组（x1，x8） ，其 中xi 是放置皇后i所在的列号。使用这种表示的显式约束条件是Si=1，2，3，4，5，6，7，8 ，1i8。 于是，解空间由88个8-元组所组成。这个问题的隐式约束条件是，没有两个xi 可以相同（即，所有皇后都必须在不同的列上）而且没有两个皇后可以在同一条斜角线上。,例 题,算法设计与分析 回溯法,1.子集树:当解向量为不定长n元组时, 树中从根至每一结点的路径 集合构成解空间.树的每个结点称为一

6、个解状态,有儿子的结点称为 可扩展结点,叶结点称为终止结点, 若结点v对应解状态(x1, x2, xi), 则其儿子对应扩展的解状态(x1, x2, xi, xi+1 ).满足所有约束条件的 解状态结点称为回答结点. 2.排序树:当解向量为定长n元组时, 树中从根至叶结点的路径的集合 构成解空间.树的每个叶结点称为一个解状态.,解空间树构造:,搜索按深度优先策略从根开始, 当搜索到任一结点时,判断该点是否 满足约束条件D(剪枝函数),满足则继续向下深度优先搜索,否则跳过 该结点以下的子树(剪枝),向上逐级回溯.,搜索过程:,求解过程可表示为在一棵解空间树 作 深度优先搜索.,0-1背包问题(0

7、-1Knapsack Problem ),例 题,n=3, C=30, w=16, 15, 15, v=45, 25, 25 开始时，Cr=C=30，V=0，A为唯一活结点，也是当前扩展结点 扩展A，先到达B结点 Cr=Cr-w1=14，V=V+v1=45 此时A、B为活结点，B成为当前扩展结点 扩展B，先到达D Crw2，D导致一个不可行解，回溯到B 再扩展B到达E,0-1背包问题(0-1Knapsack Problem ),例 题,n=3, C=30, w=16, 15, 15, v=45, 25, 25 扩展A，先到达B结点 再扩展B到达E E可行，此时A、B、E是活结点，E成为新的扩展

8、结点 扩展E，先到达J Crw3，J导致一个不可行解，回溯到E 再次扩展E到达K 由于K是叶结点，即得到一个可行解x=(1,0,0)，V=45 K不可扩展，成为死结点，返回到E E没有可扩展结点，成为死结点，返回到B B没有可扩展结点，成为死结点，返回到A,0-1背包问题(0-1Knapsack Problem ),例 题,n=3, C=30, w=16, 15, 15, v=45, 25, 25,旅行售货员问题 某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线。目标是使总的路程最短,例 题,旅行售货员问题： 该问题是一个NP完

9、全问题， 有(n-1)!条可选路线 最优解(1,3,2,4,1)，最优值25,回溯法解题步骤: 1).针对所给问题,定义问题的解空间 2).确定解空间结构. 3).以深度优先方式搜索解空间.,算法设计与分析 回溯法,常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树；（显、隐） 用限界函数剪去得不到最优解的子树。 关于复杂性： 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n)。而显式地存储整个解空间则需要O(2h(n)或O(

10、h(n)!)内存空间。,递归回溯,算法设计与分析 回溯法,void Backtrack(int t) if (t n) Output(x); else for (int i = f(n,t);i =g(n,t) ;i +) xt = h(i); if (Constraint(t) while (t 0) if (f(n,t) = g(n,t) for (int i = f(n,t);i = g(n,t);i +) xt = h(i); if (Constraint(t) ,迭代回溯,算法思路1:问题的解可表示为k元向量x1, x2, . xk , 1 kn, xiW 解空间树为排序树. 1)当

11、i j , xi xj (元素不能重复选取) 2) xixi+1 3) 4),问题陈述:给定n个不同正实数的集合W=w(i)|1 i n 和一个正整 数M,要求找到子集S, 使得 =M,算法设计与分析 回溯法子集和,例如 设n=4, W=(11,13, 24, 7), M=31,满足约束条件的子集为(11,13,7), 和 (24, 7),附加. 子集和问题,S=(1, 2, 4), 和 S=(3, 4),+ xj+1 M,+ M,约束 条件,x1=w1,w2,w3,w4,x2=w2,w3,w4,w4,w4,w4,w3,w3,w4,w4,w4,算法设计与分析 回溯法,算法思路2:问题的解可表示

12、为n元向量x1, x2, . xn , xi=1或0 则问题的解空间树为子集树,约束条件:,子集和,+ M,n=4, W=(11,13, 24, 7), M=31,算法设计与分析 回溯法 子集合,n=6,m=30,w=5,10,12,13,15,18时由算法生成的部分解空间树,子集和s,剩余元素之和r,当前层次k,子集树,算法设计与分析 回溯法,void Backtrack(int t) if (t n) Output(x); else for (int i = 0i =1 ;i +) xt = i; if (Constraint(t) else for (int i = 0;i =n ;i

13、+) swap(xt, xi); if (Constraint(t) ,算法设计与分析 回溯法 n后问题,5.2 装载问题,问题描述:n个集装箱装到2艘载重量分别为c1,c2的货轮,其中集装箱i的重量为wi且 问题要求找到一个合理的装载方案可将这n个货箱装上这2艘轮船。,例如 当n=3, c1=c2=50, w=10, 40, 40, 可将货箱1和2装到第一艘船上; 货箱3装到第二艘船上; 若w=20, 40, 40, 则无法将全部货箱装船.,当 时问题等价于子集和问题; 当c1=c2且 时 问题等价于划分问题.,若装载问题有解, 采用如下策略可得一个最优装载方案: (1)将第一艘轮船尽可能装

14、满; (2)将剩余的货箱装到第二艘轮船上。 将第一艘船尽可能装满等价于如下0-l背包问题:,xi0,1, 1in,可采用动态规划求解, 其时间复杂性为:O(C1,2n),算法设计与分析 回溯法 ,装载问题,算法思路:用子集树表示解空间,则解为n元向量x1, . ,xn , xi0, 1,+ wj+1 c1,约束条件:,由于是最优化问题, 可利用最优解性质进一步剪去不含最优解的子树: 设 bestw: 当前最优载重量, cw = : 当前扩展结点的载重量 ; r = : 剩余集装箱的重量; 当 cw+r (限界函数)bestw 时, 将cw对应右子树剪去。,cw+r bestw,+ wj+1 c

15、1,算法设计与分析 回溯法 ,装载问题,例如 n=4, c1=12, w=8, 6, 2, 3.,cw=0,cw=8,cw=14,cw=8,cw=10,cw=13,bestw=10,cw=8,bestw=11,cw=0,cw=6,cw=8,bestw=11,算法设计与分析 回溯法 ,装载问题,template void Loading:Backtrack(int i) / /搜索第i层结点 if (in) /到达叶结点 if (cwbestw) bestw=cw； return； /搜索子树 if (cw+wi=c) /xi=1 cw += wi； Backtrack (i+1)； cw -

16、= wi; Backtrack(i+1)；/xi=0 ,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.Backtrack(1)； return X.bestw； ,装载问题的回溯算法,算法复杂性: O(2n),算法设计与分析 回溯法 ,装载问题,template void Loading:Backtrack(int i) /

17、/搜索第i层结点 if (in) /到达叶结点 bestw=cw； return； /搜索子树 r - = wi; if (cw+wi bestw) /xi=0 Backtrack(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; i+) X. r +=w

18、i /计算最优载重量 X.Backtrack(1)； return X.bestw； ,上届函数-装载问题的回溯算法,算法复杂性: O(2n),算法设计与分析 回溯法 n后问题,53 批处理作业调度,问题描述:给定n个作业的集合J=(J1, J2, . , Jn)。每一作业Ji都有两项 任务要分别在2台机器上完成. 每一作业须先由机器l处理, 再由机器2处理. 设tji是作业Ji在机器j上的处理时间, i=1,.,n, j=1, 2.Fji是作业Ji在机器j上完成处理的时间. 所有作业在机器2上完成时间和: f=F2i 称为该作业调度的完成时间和. 对于给定的J, 要求制定一个最佳作业调度方案

19、, 使完成时间和最小.,算法思路:设解为n元向量x1,. ,xn , xi1,.n, 用排序树表示解空间 约束条件: 当i j , xi xj (元素不能重复选取) 限界函数: bestx:为当前最小时间和 x : 当前扩展结点的时间和; 当 bestx = x时, 将x对应左子树剪去,例 题,例 题,算法设计与分析 回溯法 作业调度,机器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; 相应的完成时间和分别是: 19, 18, 20，

20、21，19，19。 最佳调度: 1, 3, 2。,机器1,机器2,J1,J1,J3,J3,J2,J2,调度1,3,2,例 题,机器1,机器2,J3,J3,J2,J2,调度3,1,2,J1,J1,算法设计与分析 回溯法 作业调度,void Flowshop: :Backtrack(int i) if (in) for(int j = 1;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 *

21、 M, int n, int bestx ) int ub = 32767; Flowshop X; X.x = new int n+ 1; /当前调度 X.f2 = new intn+ l; /机器2完成处理时间 X.M = M; /各作业所需处理时间 X.n= n; /作业数 X.bestx = bestx; /当前最优调度 X. bestf = ub; /当前最优调度时间 X.fl = 0; /机器1完成处理时间 X.f = 0; /完成时间和 for(int i = 0;i= n; i+) X.f2i = 0,X.xi=i; X. Backtrack( 1 ); delete X. x

22、; delete X. f2; return X. bestf ;,算法复杂性: O(n!),作业调度回溯算法,算法设计与分析 回溯法 作业调度,机器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，8，8。 最佳调度: 1, 3, 2; 完成时间为8。?,x1=J1,J2,J3,x2=J2,J3,J1,x3=J3,A,B,C,D,E,F,J2,Bestx=8,J3,E,F,J3,J2,J

23、1,E,F,J1,J2,J2,例 题,算法设计与分析 回溯法 n后问题,5.4 符号三角形问题,问题描述:下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。在一般情况下，符号三角形的第一行有n个符号。 目标是：符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。,例 题,例 题,+ + - + - + + + - - - - + - + + + - - + + - - + - - - +,算法设计与分析 回溯法 n后问题,5.4 符号三角形问题,问题描述:下图是由14个“+”和14个“-”组成的符号

24、三角形。2个同号下面都是“+”，2个异号下面都是“-”。在一般情况下，符号三角形的第一行有n个符号。 目标是：符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。,例 题,例 题,+ + - + - + + + - - - - + - + + + - - + + - - + - - - +,算法设计与分析 回溯法 n后问题,5.4 符号三角形问题,算法思路:解向量用n元组x1:n表示符号三角形的第一行。 约束函数：当前符号三角形所包含的“+”个数与“-”个数均不超过 n*(n+1)/4 无解的判断：n*(n+1)/2为奇数限界函数:,例 题,例 题

25、,void Triangle:Backtrack(int t) if (counthalf)|(t*(t-1)/2-counthalf) return; if (tn) sum+; else for (int i=0;i2;i+) p1t=i; count+=i; for (int j=2;j=t;j+) pjt-j+1=pj-1t-j+1pj-1t-j+2; count+=pjt-j+1; Backtrack(t+1); for (int j=2;j=t;j+) count-=pjt-j+1; count-=i; ,复杂度分析 计算可行性约束需要O(n)时间，在最坏情况下有 O(2n)个结点

26、需要计算可行性约束，故解符号三角形问题的回溯算法所需的计算时间为 O(n2n)。,算法思路:将棋盘从左至右,从上到下编号为1,.,n,皇后编号为1,.,n. 设解为(x1, ., xn) , xi为皇后i的列号,且xi位于第i行. 解空间:E= (x1,., xn) | xiSi, i=1,.,4, Si=1, ., 4,1 i n 解空间为排列树? 其约束集合D为 1) xi xj 2) xi-i xj-j 3) xi+i xj+j,皇后i,j不在同一斜线上,算法设计与分析 回溯法 n后问题,5.5 n后问题,皇后i,j不在同一列上,问题描述:nXn棋盘上放置n个皇后使得每个皇后互不受攻击.

27、 即任二皇后不能位于同行同列和同一斜线上.,如四后问题的解,abs(i-j) abs(xi xj),算法设计与分析 回溯法 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) ,int nQueen(int n) QueenX； /初始化X X. n=n；/皇后个数 X. sum=0； int*p

28、=new int n+1； for(int i=0；i=n；i+) pi= 0； X.x=p； X.Backtrack(1)； delete p； returnX. sum；,n后问题的递归回溯算法,算法复杂性:,算法设计与分析 回溯法 n后问题,void Queen: Backtrack(void) x1=0; int k=1; while(k0) xk+=1; while(xk=n) ,int nQueen(int n) QueenX； /初始化X X. n=n；/皇后个数 X. sum=0； int*p=new int n+1； for(int i=0；i=n；i+) pi= 0； X.

29、x=p； X.Backtrack( )； delete p； returnX. sum；,n后问题的迭代回溯算法,算法设计与分析 回溯法 0-1背包问题,5.6 0-1背包问题,解空间：子集树 可行性约束函数： 上界函数：,背包问题，最优解？（贪心） 装载问题 怎么剪掉左子树? 装载问题 怎么剪掉右子树?,例如 当n=4, C=7, P=9,10,7,4,W=3,5,2,1, 则P/W=3,2,3.5,4. 最大价值22 X=1,0.2,1,1,算法设计与分析 回溯法 0-1背包问题,5.6 0-1背包问题,template Typep Knap:Bound(int i) / 计算上界 Typ

30、ew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品单位重量价值递减序装入物品 while (i = n ,算法设计与分析 回溯法 最大团问题,设无向图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的

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

32、,.,1,0,1,1,0,1,算法设计与分析 回溯法 最大团问题,最大团问题的回溯算法,void 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 i ; j+) if (xj ,int MaxClique(int * a, int vi, int n) Clique Y; Y.x

33、 = new int n+l; Y.a= a; /图G的邻接矩阵 Y.n= n; /图G顶点数 Y.cn = 0; /当前团顶点数 Y.bestn=0; /当前最大团顶点数 Y.bestx = v; /当前最优解 Y. Backtrack( 1 ); delete Y. x; return Y. best,算法设计与分析 回溯法 着色问题,图的m色判定问题: 给定无向连通图G和m种颜色。用这些颜色为图G的各顶点着色. 问是否存在着色方法, 使得G中任2邻接点有不同颜色。 图的m色优化问题:给定无向连通图G,为图G的各顶点着色, 使图中任2邻接点着不同颜色,问最少需要几种颜色。所需的最少颜色的数

34、目m称为该图的色数。,5.8 图的m着色问题,问题描述,若图G是可平面图,则它的色数不超过4色(4色定理). 4色定理的应用:在一个平面或球面上的任何地图能够只用4种颜色来着色使 得相邻的国家在地图上着有不同颜色,4,3,2,1,5,1,2,3,4,5,a).将G的结点按照度数递减的次序排列. b).用第一种颜色对第一个结点着色,并按照结点排列的次序 对与前面着色点不邻接的每一点着以相同颜色. c).用第二种颜色对尚未着色的点重复步骤b).用第三种颜色 继续这种作法, 直到所有点着色完为止.,任意图的着色,Welch Powell法,a1,a5,a4,a6,a2,a3,a7,a8, 排序:a5

35、, a3, a7, a1, a2, a4, a6, a8, 着第一色: a5, a1,着第二色:a3,a4, a8,着第三色:a7, a2, a6,图论 对偶图与着色,算法设计与分析 回溯法 图的m着色,设图G=(V, E), |V|=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=3时的解空间树,1,3,2

36、,a=,算法设计与分析 回溯法 着色问题,int mColoring(int n, int m, int *a ) Color X； /初始化X Xn=n； /图的顶点数 Xm=m /可用颜色数 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；j=n；j+) if(ak

37、j=1)(xj=xk) ) return false； retrun true；,voidColor backtrack(int t) if (tn) 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) Backtrack( t+1); ,算法设计与分析 回溯法 着色问题,某售货员要到若干城市去推销商品，已知各城市之间的路程（旅费），他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（总旅费）最小。,5.9旅行售货员问题,问题描述,算法设计与分析 回溯法 着色问题,旅行售货员问题的解空间是一棵排列树。对于排列树的回溯法与生成1,2,n的所有排列的递归算法Perm类似。开始时x=1,2,n,则相应的排列树有x1:n的所有排列构成。 在递归算法Backtrack中，当i=n时，当前扩展节点是排列树的叶节点的父节点。此时算法检测图G是否存在一条从顶点xn-1到顶点xn的边和一条从顶点xn到顶点1的边。如果这两条边都存在，则找到一条旅行员售货回路。此时，算法还需要判断这条回路的费用是否优于已找到的当前最优回流的费用bestc