计算机算法设计与分析--第5章回溯算法.ppt

计算机算法设计与分析 Design and Analysis of Computer Algorithms,第五章 回溯算法 Backtrack Algorithm,王红霞 理学院,2019年4月16日,2,理解回溯法的深度优先搜索策略。 掌握用回溯法解题的算法框架 （1）递归回溯 （2）迭代回溯 （3）子集树算法框架 （4）排列树算法框架,学习要点,2019年4月16日,3,提纲,一、回溯法的算法框架 二、装载问题 三、n后问题 四、0-1背包问题 五、最大团问题 六、图的m着色问题 七、旅行售货员问题,2019年4月16日,4,提纲,一、回溯法的算法框架 二、装载问题 三、n后问题 四、0-1背包问题 五、最大团问题 六、图的m着色问题 七、旅行售货员问题,2019年4月16日,5,深度优先搜索算法,深度优先搜索算法（Depth-First-Search），是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支，如果发现目标，则算法中止，属于盲目搜索。 深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。,2019年4月16日,6,同时深度优先搜索算法的时间复杂度不高（为线性时间复杂度），遍历图的效率往往非常高。因此，鉴于深度优先搜索算法的强大功能以及高效性往往被研究图论问题的专家所推崇，他们常建议在遇到未知性质的图时，先对图进行深度优先遍历，以了解未知图的性质。 因发明“深度优先搜索算法”，霍普克洛夫特与陶尔扬共同获得计算机领域的最高奖：图灵奖,2019年4月16日,7,搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。,2019年4月16日,8,迷宫游戏,2019年4月16日,9,例：迷宫游戏,2019年4月16日,10,例：N后问题,2019年4月16日,11,引言,有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。 回溯法的基本做法是搜索，或是一种组织得井井有条的、能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。,2019年4月16日,12,5.1 回溯法的算法框架,本节介绍回溯法算法框架的有关问题： 一、问题的解空间 二、回溯法的基本思想 三、递归回溯 四、迭代回溯 五、子集树与排列树,2019年4月16日,13,5.1.1 问题的解空间,问题所有可能的解构成了问题的解空间，解空间也就是进行穷举的搜索空间。 确定正确的解空间很重要！,例如：桌子上有6根火柴棒，要求以这6根火柴棒为边搭建4个等边三角形。,2019年4月16日,14,5.1.1 问题的解空间,对于任何一个问题，可能解的表示方式和它相应的解释隐含了解空间及其大小。 例如，对于有n个物品的0/1背包问题，其可能解的表示方式可以有以下两种： （1）可能解由一个不等长向量组成，当物品i(1in)装入背包时，解向量中包含分量i，否则，解向量中不包含分量i，当n=3时，其解空间是： ( ), (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3) （2）可能解由一个等长向量x1, x2, , xn组成，其中xi=1(1in)表示物品i装入背包，xi=0表示物品i没有装入背包，当n=3时，其解空间是： (0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1) ,2019年4月16日,15,问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。 显约束：对分量xi的取值限定。 隐约束：为满足问题的解而对不同分量之间施加的约束。 解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。,注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。,2019年4月16日,16,5.1.1 问题的解空间,为了用回溯法求解一个具有n个输入的问题，一般情况下，将其可能解表示为满足某个约束条件的等长向量X=(x1, x2, , xn)，其中分量xi (1in)的取值范围是某个有限集合Si=ai1, ai2, , airi，所有可能的解向量构成了问题的解空间。 问题的解空间一般用解空间树（Solution Space Trees,也称状态空间树）的方式组织，树的根结点位于第1层，表示搜索的初始状态，第2层的结点表示对解向量的第一个分量做出选择后到达的状态，第1层到第2层的边上标出对第一个分量选择的结果，依此类推，从树的根结点到叶子结点的路径就构成了解空间的一个可能解。,2019年4月16日,17,5.1.1 问题的解空间 1.背包问题,对于n=3的0/1背包问题，其解空间树如下图所示，树中的8个叶子结点分别代表该问题的8个可能解。,2019年4月16日,18,2 旅行售货员问题,问题描述：某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。 该问题是一个NP完全问题， 有(n-1)!条可选路线 最优解(1,3,2,4,1)，最优值25,2019年4月16日,19,5.1.2 回溯法的基本思想,回溯法从根结点出发，按照深度优先策略搜索（遍历）解空间树，搜索满足约束条件的解。 初始时，根结点成为一个活结点，同时也称为当前的扩展结点。在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为一个新的活结点，并成为当前的扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为一个死结点（即不再是一个活节点）。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。,2019年4月16日,20,5.1.2 回溯法的基本思想,在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出限界函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。 在搜索过程中，通常采用两种策略避免无效搜索： （1）用约束条件剪去得不到可行解的子树； （2）用限界函数剪去得不到最优解的子树。 这两类函数统称为剪枝函数（Pruning Function）。,2019年4月16日,21,5.1.2 回溯法的基本思想,例如，对于n=3的0/1背包问题，三个物品的重量为16, 15, 15，价值为45, 25, 25，背包容量为30，从其解空间树的根结点开始搜索，搜索过程如下：,2019年4月16日,22,5.1.2 回溯法的基本思想,回溯法是一种通用性解法，可以将回溯法看作是带优化的穷举法。 回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点，搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。 在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造；,2019年4月16日,23,5.1.3 递归回溯,void backtrack (int t) /t表示递归深度，即对解空间树的第t层节点进行深度优先搜索； if (tn) output(x); /n表示解空间树的高度； else for (int i=f(n,t);i=g(n,t);i+) /f(n,t)和g(n,t)分别表示在当前扩展结点处未搜索过的子树的起始 编号和终止编号； xt=h(i); /h(i)表示在当前扩展结点处xt的第i个可选值； if (constraint(t) / constraint(t)和bound(t)分别表示在当前扩展结点处的约束函数 和限界函数； ,2019年4月16日,24,5.1.4 迭代回溯,void IterativeBacktrack () int t=1; while (t0) if (f(n,t)=g(n,t) for (int i=f(n,t);i=g(n,t);i+) xt=h(i); if (constraint(t) ,2019年4月16日,25,遍历子集树需O(2n)计算时间,遍历排列树需要O(n!)计算时间,void backtrack (int t) if (tn) output(x); else for (int i=0;i=1;i+) xt=i; if (constraint(t) ,void backtrack (int t) if (tn) output(x); else for (int i=t;i=n;i+) swap(xt, xi); if (constraint(t) ,5.1.5 子集树与排列树,2019年4月16日,26,对于n=4的旅行售货员问题（TSP），其解空间树如下图所示。叶子结点代表该问题的可能解，例如结点5代表一个可能解，路径为12341，长度为各边代价之和。,2019年4月16日,27,5.1.6 回溯法的求解过程,(1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (3) 深度优先搜索解空间，并在搜索中用剪枝函数避免无效搜索。,常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树。,需要注意的是，问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n)。而显式地存储整个解空间则需要O(2h(n)或O(h(n)!)内存空间。,2019年4月16日,28,提纲,一、回溯法的算法框架 二、装载问题 三、n后问题 四、0-1背包问题 五、最大团问题 六、图的m着色问题 七、旅行售货员问题,2019年4月16日,29,5.2.1装载问题问题定义,有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且wic1+c2 装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。 例如：当n=3，c1=c2=50，w=10,40,40，可以将集装箱1和2装到第一艘轮船上，将集装箱3装到第二艘轮船上。 如果w=20,40,40，则无法将这3个集装箱都装上轮船。,2019年4月16日,30,5.2.2问题分析,如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案： (1)首先将第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船。 将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近c1 。由此可知，装载问题等价于以下特殊的0-1背包问题。,2019年4月16日,31,5.2.3算法设计,解空间：子集树 可行性约束函数(选择当前元素)： 上界函数(不选择当前元素)： 当前载重量cw+剩余集装箱的重量r当前最优载重量bestw,1,0,1,1,1,1,0,0,0,不满足 约束函数,1,不满足 上界函数,0,0,1,2019年4月16日,32,5.2.4 算法描述,void backtrack (int i) / 搜索第i层结点 if (i n) / 到达叶结点 更新最优解bestx,bestw;return; r -= wi; if (cw + wi bestw) / 搜索右子树 xi = 0; backtrack(i + 1); r += wi; ,复杂度分析 算法backtrack在最坏情况下可能需要更新当前最优解O(2n)次，每次更新bestx需计算时间O(n)，从而整个算法的计算时间复杂性为O(n2n)。 进一步改进算法，可降低时间复杂性为O(2n)。,2019年4月16日,33,习题5-1,2019年4月16日,34,2019年4月16日,35,习题5-2,2019年4月16日,36,2019年4月16日,37,2019年4月16日,38,提纲,一、回溯法的算法框架 二、装载问题 三、n后问题 四、0-1背包问题 五、最大团问题 六、图的m着色问题 七、旅行售货员问题,2019年4月16日,39,N 皇后问题是由八皇后问题演化而来的。八皇后问题于1848 年由国际象棋棋手MaxBazzel 提出。八皇后问题自从提出之后, 吸引了许多著名数学家的关注, 其中包括Carl Gauss。近年来, N 皇后问题成为计算机应用领域内的一个经典问题, 不但成为测试算法的一个工具, 还成为检验计算机系统效率的一个有效工具。,引言,2019年4月16日,40,3.1 问题定义,八皇后问题是一个非常著名的问题，最初是由著名数学家高斯提出的。问题的描述是这样的：在一个8 8的棋盘上，摆放8个皇后，任意两个皇后不能处在同一行、同一列和同一斜线上。该问题也可以被扩展为在一个n n的棋盘上摆放n个皇后的问题。,2019年4月16日,41,例：4后问题,2019年4月16日,42,经典的回溯算法，该算法的思路如下： 依次在棋盘的每一行上摆放一个皇后。 每次摆放都要检查当前摆放是否可行。如果当前的摆放引发冲突，则把当前皇后摆放到当前行的下一列上，并重新检查冲突。 如果当前皇后在当前行的每一列上都不可摆放，则回溯到上一个皇后并且将其摆放到下一列上，并重新检查冲突。 如果所有皇后都被摆放成功，则表明成功找到一个解，记录下该解并且回溯到上一个皇后。,N后问题回溯算法,2019年4月16日,43,3.2问题分析,皇后不在同一行上同一列上: 设解向量：(x1, x2, , xn)，xi表示皇后i放在棋盘的第i行的第xi列。 那么：第i皇后的位置（ i, xi ） 则：不在同一行上同一列上可以表示为： 当(ij) 时，x i x j,2019年4月16日,44,皇后不在同一斜线上,i- x i = j -x j,i + x i = j + x j,皇后不在同一斜线上: |i-j|x i -x j |,2019年4月16日,45,两个皇后不冲突的条件：,当(ij) 时， x i x j |i-j|x i -x j |,2019年4月16日,46,/place函数测试若将皇后k放在xk列是否与前面已放置的k-1个皇后都不在同一列，而且都不在同一斜线上。 bool Queen:Place(int k) for (int j=1;jk;j+) if (abs(k-j)=abs(xj-xk)|(xj=xk) return false; return true; ,3.3算法描述,2019年4月16日,47,Void Queen:Backtrack(void) X1=0; Int k=1; While(k0) xk+=1; while(xk=n) ,3.3算法描述,2019年4月16日,48,3.4 问题的解,4皇后问题：,8皇后问题：,2019年4月16日,49,参考文献,1张万军，N 皇后问题回溯算法探讨， 宜宾学院学报，2006.6 2韩宇南, 吕英华, 黄小红，并行改进回溯算法实现N 皇后问题的快速计 数，博士论坛 3 苏德富.计算机算法设计与分析.电子工业出版 社，2001.1 4 Sara Baase等.计算机算法-设计与分析导论 （英文影印版）.高等教育出版社，2001.7 5 卢开澄.计算机算法导引-设计与分析.清华大学 出版社，1998.3 6 M.R.加里等著，张立昂等译.计算机和难解性- NP完全性理论导印.科学出版社，1987.1 7 M.H.Alsuwaiyel著,吴伟昶等译.算法设计技巧与分析电子工业出版社，2004.8,2019年4月16日,50,为了用回溯法求解4皇后问题，算法尝试生成并以深度优先方式搜索一棵完全四叉有根树，树的根对应于没有放置皇后的情况。第一层的节点对应于皇后在第一行的可能放置情况，第二层的节点对应于皇后在第二行的可能放置情况，依次类推。,2019年4月16日,51,N后问题的时间复杂性,如果只要找出N后问题的一个解，那么这是一个求路径的问题。 求路径：只需要找到一条路径便可以得到解。设每个状态有k个后继，其搜索树为K叉树，其结点总数为kn+11，遍历的时间为O(kn)，这里n为找到解的路径长度。 N后问题的路径深度为n，可选择的后继有n个，所以时间复杂性为O(nn)。,2019年4月16日,52,提纲,一、回溯法的算法框架 二、装载问题 三、n后问题 四、0-1背包问题 五、最大团问题 六、图的m着色问题 七、旅行售货员问题,2019年4月16日,53,4.1问题定义,给定n种物品和一个背包，物品i的重量是wi，价值pi,背包容量为C，问如何选择装入背包的物品，使装入背包中的物品的总价值最大？ 对于每种物品只能选择完全装入或不装入，一个物品至多装入一次。,2019年4月16日,54,4.2问题分析,解空间：子集树 可行性约束函数： 或：cw+wi=c,template Typep Knap:Bound(int i) / 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品单位重量价值递减序装入物品 while (i = n ,上界函数：,2019年4月16日,55,4.3 算法描述,template Typep Knap:Backtrack(int i) if (in) best = cp; return; if (cw+wi bestp) /xi=0，否则剪去右子树 backtrack(i+1); ,复杂度分析 计算上界函数Bound需要O(n)时间，最坏情况下有O(2n)个右儿子结点需要计算上界函数。所以，0-1背包问题的回溯法backtrack所需的计算时间为O(n2n)。,2019年4月16日,56,提纲,一、回溯法的算法框架 二、装载问题 三、n后问题 四、0-1背包问题 五、最大团问题 六、图的m着色问题 七、旅行售货员问题,2019年4月16日,57,5.1问题定义,完全子图：给定无向图G=(V，E)。如果UV，且对任意u，vU有(u，v)E，则称U是G的完全子图。 团：G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。 G的最大团：是指G中所含顶点数最多的团。,2019年4月16日,58,5.1问题定义,空子图：如果UV且对任意u，vU有(u，v)E，则称U是G的空子图。 独立集：G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。 G的最大独立集：是G中所含顶点数最多的独立集。 补图：对于任一无向图G=(V，E)其补图G=(V1，E1)定义为：V1=V，且(u，v)E1当且仅当(u，v)E。 U是G的最大团当且仅当U是G的最大独立集。,2019年4月16日,59,5.2 问题分析,解空间：子集树 可行性约束函数： 顶点i到已选入的顶点集中每一个顶点都有边相连。 上界函数： 有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。,2019年4月16日,60,5.3 算法描述,void Clique:Backtrack(int i)/ 计算最大团 if (i n) / 到达叶结点 for (int j = 1; j bestn) / 进入右子树 xi = 0; Backtrack(i+1); ,复杂度分析 最大团问题的回溯算法backtrack所需的计算时间为O(n2n)。,2019年4月16日,61,提纲,一、回溯法的算法框架 二、装载问题 三、n后问题 四、0-1背包问题 五、最大团问题 六、图的m着色问题 七、旅行售货员问题,2019年4月16日,62,6.1 问题定义,给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。 若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。 求一个图的色数m的问题称为图的m可着色优化问题。,2019年4月16日,63,6.1 问题定义,可平面图：如果一个图的所有顶点和边都能用某种方式画在一个平面上且没有任何两边相交，则称这个图是可平面图。 四色定理：任何平面图都是可以4着色的。,2019年4月16日,64,6.1 问题定义,图的m着色问题： 给定一个一般连通图G=(V,E)和m种颜色，如果这个图不是m可着色的就给出否定回答，如果这个图是m可着色的，则要找出所有不同的着色方案。,2019年4月16日,65,6.2 问题分析,解向量：(x1, x2, , xn)表示顶点i所着颜色xi 。 解空间：完全m叉树 可行性约束函数：顶点i与已着色的相邻顶点颜色不重复。,2019年4月16日,66,6.3 算法描述,void Color:Backtrack(int t) if (tn) sum+; /当前已找到的可m着色方案数加1； 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); bool Color:Ok(int k) / 检查第k个顶点当前所选颜色xk的可用性； for (int j=1;j=n;j+) if (akj=1) ,2019年4月16日,67,6.4 复杂性分析,图m可着色问题的解空间树中内结点个数是mi(0in-1)。 对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。因此，回溯法总的时间耗费是 mi(mn)=nm(mn-1)/(m-1)=O(nmn) (0in-1),2019年4月16日,68,提纲,一、回溯法的算法框架 二、装载问题 三、n后问题 四、0-1背包问题 五、最大团问题 六、图的m着色问题 七、旅行售货员问题,2019年4月16日,69,旅行商问题是一个经典的组合优化问题。经典./- 可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton 回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP 完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究。,2019年4月16日,70,哈密顿回路,天文学家哈密顿(William Rowan Hamilton) 提出，在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。 这个问题和著名的过桥问题的不同之处在于，某些城市之间的旅行不 一定是双向的。比如AB,但BA是不允许的。换一种说法，对于一个给定的网络，确定起点和终点后，如果存在一条路径，穿过这个网络，我们就说这个网络存在哈密顿路径。哈密顿路径问题在上世纪七十年代初，终于被证明是“NP完备”的。据说具有这样性质的问题，难于找到一个有效的算法。实际上对于某些顶点数不到100的网络，利用现有最好的算法和计算机也需要比较荒唐的时间（比如几百年）才能确定其是否存在一条这样的路径。,2019年4月16日,71,从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。 要满足两个条件： 1.封闭的环 2.是一个连通图，且图中任意两点可达 经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。 经过图中所有顶点一次且仅一次的回路称为哈密顿回路。 具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。 平凡图是哈密顿图。,2019年4月16日,72,哈密顿 哈密顿，WR(Hamilton，William Rowan) 1805年8月4日生于爱尔兰都柏林；1865年9月2日卒于都柏林力学、数学、光学,2019年4月16日,73,哈密顿的父亲阿其巴德(Archibald Rowan Hamilton)为都柏林市的一个初级律师哈密顿自幼聪明，被称为神童他三岁能读英语，会算术；五岁能译拉丁语、希腊语和希伯来语，并能背诵荷马史诗；九岁便熟悉了波斯语，阿拉伯语和印地语14岁时，因在都柏林欢迎波斯大使宴会上用波斯语与大使交谈而出尽风头 哈密顿自幼喜欢算术，计算很快1818年遇到美国“计算神童”Z科耳本(C