算法设计与分析王红梅第二版第8章-回溯法详解

第8章回溯法BackTrackMethod算法设计与分析—本科生课程DesignandAnalysisofAlgorithm海南大学信息科学技术学院CollegeofInformationScienceandTechnology,HainanUniversity2020/9/13Chapter8BackTrackMethod2在现实世界中，很多问题没有（至少目前没有）有效的算法，这些问题的解只能通过穷举搜索来得到。只有满足约束条件的解才是可行解，只有满足目标函数的解才是最优解，这就有可能避免无效的搜索，提高搜索效率。回溯法和分支限界法均属于有组织的系统化搜索技术，可看作是穷举搜索的改进。蛮力法：生成问题的所有可能解，再去评估是否满足约束条件；回溯法：每次只构造可能解的一部分，然后评估这个部分解，如果有可能导致一个完整解，则对其进一步构造，否则不必继续构造这个部分解。这样可以避免搜索所有的可能解，适用于求解组合数量较大的问题。基于搜索的算法设计技术2020/9/133教学重点回溯法的设计思想，各种经典问题的回溯思想教学难点批处理作业调度问题的回溯算法教学内容及目标知识点教学要求了解理解掌握熟练掌握问题的解空间树√回溯法的设计思想√回溯法的时间性能√图着色问题√哈密尔顿回路问题√八皇后问题√批处理作业调度问题√学习目标Chapter8BackTrackMethod2020/9/13Chapter8BackTrackMethod4本章要点8.1概述8.2图问题中的回溯法8.3组合问题中的回溯法2020/9/13Chapter8BackTrackMethod58.1概述8.1.1问题的解空间8.1.2回溯法的设计思想8.1.3回溯法的时间性能2020/9/13Chapter9BackTrackMethod6提出问题？复杂问题常常有很多的可能解，这些可能解构成了问题的解空间。解空间？就是在穷举法中提到的所有可能解的搜索空间。一般而言，解空间中应该包括所有的可能解。问题的解向量为X=（x1,x2,…,xn）。xi的取值范围为有穷集Si。把xi的所有可能取值的组合，称为问题的解空间。每一个组合是问题的一个可能解。不正确的解空间会引发问题？可能会增加很多重复解，或者根本就搜索不到正确的解。（例：用桌面上的6根火柴棒为边搭建4个等边三角形）概述-问题的解空间2020/9/13Chapter8BackTrackMethod7示例：桌子上有6根火柴棒，要求以这6根火柴棒为边搭建4个等边三角形。概述-问题的解空间(a)二维搜索空间无解(b)三维搜索空间的解图8.1错误的解空间将不能搜索到正确答案2020/9/13Chapter8BackTrackMethod8例：0/1背包问题中，xi有0/1两种取值，则S={0，1}，当n=3时，0/1背包问题的解空间是：{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}即：当输入规模为n时，有2n种可能的解。例：货郎担问题，S={1,2,…,n}，当n=3时，S={1,2,3}。货郎担TSP问题的解空间中的可能解有27个，是：{(1,1,1),(1,1,2),(1,1,3),(1,2,1),(1,2,2),(1,2,3),┅,(3,3,1),(3,3,2),(3,3,3)}当输入规模为n时，它有nn种可能的解。考虑到约束方程xi≠xj。因此，货郎担问题的解空间压缩为：{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)}当输入规模为n时，它有n!种可能的解。概述-问题的解空间2020/9/13Chapter8BackTrackMethod9可能解的表示方式？如，对于n个物品的0/1背包问题，其可能解有以下两种：可能解由一个不等长向量组成，当物品i(1≤i≤n)装入背包时，解向量中包含分量i，否则，解向量中不包含分量i，当n=3时，其解空间是：{(),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)}可能解由等长向量{x1,x2,…,xn}组成，xi=1/0(1≤i≤n)分别表示物品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)}概述-问题的解空间2020/9/13Chapter8BackTrackMethod10回溯法“可能解”及“解空间”的表达可能解的表示：用等长向量X=(x1,x2,…,xn)，其中分量xi(1≤i≤n)的取值范围是某个有限集合Si={ai1,ai2,…,airi}，所有可能的解向量构成了问题的解空间。概述-问题的解空间解空间表达：用解空间树（SolutionSpaceTrees）/也称状态空间树的方式组织：第1层（根结点）：表示搜索的初始状态第2层结点：表示对解向量的第一个分量做出选择后到达的状态第1层到第2层间边上标出对第一个分量选择的结果依此类推，从根结点叶结点的路径构成了解空间的一个可能解。2020/9/13Chapter8BackTrackMethod11可行解：满足约束条件的解，解空间中的一个子集最优解：使目标函数取极值(极大或极小)的可行解，一个或少数几个例：货郎担问题，有nn种可能解。n!种可行解，只有一个或几个是最优解。例：背包问题，有2n种可能解，有些是可行解，只有一个或几个是最优解有些问题，只要可行解，不需要最优解：例：八皇后问题和图的着色问题概述-问题的解空间2020/9/13Chapter8BackTrackMethod12例：对于n=3的0/1背包问题，其解空间树如图8.2所示，树中的8个叶子结点分别代表该问题的8个可能解。对物品1的选择对物品3的选择对物品2的选择1111110000000112345781112141531069概述-问题的解空间2020/9/13Chapter8BackTrackMethod13例：对于n=4的TSP问题，图8.3是经压缩后的解空间树，树中的24个叶子结点分别代表该问题的24个可能解，例如结点5代表一个可能解，路径为1→2→3→4→1，长度为各边代价之和。图8.3n=4的TSP问题经压缩后解空间树2434223434131424121233121341313123212142414343224341231241345710121517212326283133373942444749525457596264469111416202225273032363841434648515356586163381319242935404550556021834241123434概述-问题的解空间2020/9/13Chapter8BackTrackMethod148.1概述8.1.1问题的解空间8.1.2回溯法的设计思想8.1.3回溯法的时间性能2020/9/13Chapter8BackTrackMethod15回溯法的设计思想回溯法从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件/是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。2020/9/13Chapter8BackTrackMethod16例：对于n=3的0/1背包问题，其参数如下：重量W={20,15,10}，价值V={20,30,25}，背包容量C=25下图是解空间树结构结果，从根结点出发，其搜索过程如下：1不可行解价值=20价值=55价值=30价值=25价值=0111100000011238111214151310697不可行解回溯法的设计思想X1=1,V1=20C=25-20=5X2=1,W2=15V2=30,C=5X2=0,V=20C=5X3=0,V=20C=5可行解1X1=0,V=0C=25X2=1,V=30C=10可行解2可行解3可行解4可行解52020/9/13Chapter8BackTrackMethod17在2叉完全树中，结点总数有：1+2^1+2^2+2^2^2=151不可行解价值=20价值=55价值=30价值=25价值=0111100000011238111214151310697不可行解回溯法的设计思想1045不可行解2020/9/13Chapter8BackTrackMethod18回溯法的搜索过程涉及的结点称为搜索空间，只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索：用约束条件剪去得不到可行解的子树；用目标函数剪去得不到最优解的子树。这两类函数统称为剪枝函数（PruningFunction）。回溯法的设计思想需要注意的是：问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构，只需要存储从根结点到当前结点的路径。2020/9/13Chapter8BackTrackMethod198.1概述8.1.1问题的解空间8.1.2回溯法的设计思想8.1.3回溯法的时间性能2020/9/13Chapter8BackTrackMethod20回溯法的时间性能一般情况下，在问题的解向量X=(x1,x2,…,xn)中，分量xi(1≤i≤n)的取值范围为某个有限集合Si={ai1,ai2,…,airi}，因此，问题的解空间由笛卡儿积A=S1×S2×…×Sn构成，并且第1层的根结点有|S1|棵子树，则第2层共有|S1|个结点，第2层的每个结点有|S2|棵子树，则第3层共有|S1|×|S2|个结点；依此类推，第n+1层共有|S1|×|S2|×…×|Sn|个结点，他们都是叶子结点，代表问题的所有可能解。2020/9/13Chapter8BackTrackMethod21在用回溯法求解问题时，常用到两种典型的解空间树：（1）子集树：当问题是从n个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集树。在子集树中，|S1|=|S2|=…=|Sn|=c，即每个结点有相同数目的子树，当c=2，则子集树中共有2n个叶子结点，因此，遍历子集树需要Ω(2n)时间。如：0/1背包（2）排列树：当问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。在排列树中，通常情况下，|S1|=n，|S2|=n-1，…，|Sn|=1，所以，排列树中共有n!个叶子结点，因此，遍历排列树需要Ω(n!)时间。如：TSP问题回溯法的时间性能回溯法实际上属于蛮力穷举法，当然不能指望它有很好的最坏时间复杂性（指数阶）。其有效性往往体现在当问题规模n很大时，在搜索过程中对问题的解空间树大量剪枝。但是很难估计出在搜索过程中所产生的结点数，这也是分析回溯法的时间性能的主要困难。回溯法的时间性能2020/9/13Chapter8BackTrackMethod23本章要点8.1概述8.2图问题中的回溯法8.3组合问题中的回溯法2020/9/13Chapter8BackTrackMethod248.2图问题中的回溯法8.2.1图着色问题8.2.2哈密顿回路问题2020/9/13Chapter8BackTrackMethod25图着色问题图着色问题描述为：给定无向连通图G=(V,E)和正整数m，求最小的整数m，当用m种颜色对G中的顶点着色，使得任意两个相邻顶点着色不同。2020/9/13Chapter8BackTrackMethod26由于用m种颜色为无向图G=(V,E)着色，其中，V的顶点个数为n，可以用一个n元组C=(c1,c2,…,cn)来描述图的一种可能着色，其中，ci∈{1,2,…,m}(1≤i≤n)表示赋予顶点i的颜色。例如：•5元组(1,2,2,3,1)表示对5个顶点无向图的着色方案之一，其