补充2回溯法 z理解回溯法的深度优先搜索策略。
z掌握用回溯法解题的算法框架
（1）递归回溯
（2）迭代回溯
（3）子集树算法框架
（4）排列树算法框架 z通过应用范例学习回溯法的设计策略。

1 算法导论 Sch2-1方法概述 z搜索算法介绍
（1）穷举搜索
（2）盲目搜索 —深度优先(DFS)或回溯搜索(Backtracking);—广度优先搜索(BFS);—分支限界法(Branch&Bound)；—博弈树搜索(α-βSearch)
（3）启发式搜索 —A*算法和最佳优先(Best-FirstSearch)—迭代加深的A*算法—B*,AO*,SSS*等算法—LocalSearch,GA等算法
2 算法导论 Sch2-1方法概述 z搜索空间的三种表示： —表序表示：搜索对象用线性表数据结构表示；—显示图表示：搜索对象在搜索前就用图（树）的数据结构表示；—隐式图表示：除了初始结点，其他结点在搜索过程中动态生成。
缘于 搜索空间大，难以全部存储。
z搜索效率的思考：随机搜索 —上世纪70年代中期开始，国外一些学者致力于研究随机搜索求解困难的组合问题，将随机过程引入搜索； —选择规则是随机地从可选结点中取一个，从而可以从统计角度分析搜索的平均性能； —随机搜索的一个成功例子是：判定一个很大的数是不是素数，获得了第一个多项式时间的算法。

3 算法导论 Sch2-1方法概述 z回溯法： —回溯法是一个既带有系统性又带有跳跃性的搜索算法；—它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结 点出发搜索解空间树。
——系统性—算法搜索至解空间树的任一结点时，判断该结点为根的子树是否包含 问题的解，如果肯定不包含，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯。
否则，进入该子树，继续深度优先的策略进行搜索。
——跳跃性—这种以深度优先的方式系统地搜索问题的解得算法称为回溯法，它适用于解一些组合数较大的问题。

4 算法导论 Sch2-1方法概述 z问题的解空间 —问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。
—显约束：对分量xi的取值限定。
—隐约束：为满足问题的解而对不同分量之间施加的约束。
—解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组， 构成了该实例的一个解空间。
注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。
n=3时的0-1背包问题用完全二叉树表示的解空间
5 算法导论 Sch2-1方法概述
6 算法导论 Sch2-1方法概述 z基本思想： —搜索从开始结点（根结点）出发，以深度优先搜索整个解空间。
—这个开始结点成为活结点，同时也成为当前的扩展结点。
在当前的扩展结点 处，搜索向纵深方向移至一个新结点。
这个新结点就成为新的活结点，并成为当前扩展结点。
—如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成为死结点。
—此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点；直到找到一个解或全部解。

7 算法导论 Sch2-1方法概述 z基本步骤： ①针对所给问题，定义问题的解空间；②确定易于搜索的解空间结构；③以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效 搜索。
常用剪枝函数：①用约束函数在扩展结点处剪去不满足约束的子树；②用限界函数剪去得不到最优解的子树。

8 算法导论 Sch2-1方法概述 z二类常见的解空间树： ①子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。
子集树通常有2n个叶子结点，其总结点个数为2n+1-
1，遍历子集树时间为Ω(2n)。
如0-1背包问题，叶结点数为2n，总结点数2n+1； ②排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。
排列树通常有n!
个叶子结点，因此，遍历排列树需要Ω(n!
)的计算时间。
如TSP问题，叶结点数为n!
，遍历时间为Ω(n!
)。

9 算法导论 Sch2-1方法概述 例1[0-1背包]：n=3,w=(16,15,15),v=(45,25,25),c=30
(1)定义解空间：X={(0,0,0),(0,0,1),(0,1,0),…,(1,1,0),(1,1,1)}
(2)构造解空间树： 10 算法导论 Sch2-1方法概述 11 算法导论 Sch2-1方法概述 z例2[TSP问题]:
（1）定义解空间：X={12341,12431,13241,13421,14231,14321}
（2）构造解空间树：
（3）从A出发按DFS搜索整棵树：最优解：13241，14231成本：25 12 算法导论 Sch2-1方法概述 z用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。
在任何时刻，算法只保存从根结点到当前扩展结点的路径。
如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。
而显式地存储整个解空间则需要O(2h(n))或O(h(n)!
)内存空间。
13 算法导论 Sch2-2算法框架 z回溯法对解空间作深度优先搜索，因此在一般情况下可用递归函数来实现回溯法： z子集树回溯算法 Backtrack(intt)//搜索到树的第t层 {//由第t层向第t+1层扩展，确定x[t]的值 ift>nthenoutput(x);//叶子结点是可行解 else while(allXt)do //Xt为当前扩展结点的所有可能取值集合 { x[t]=Xt中的第i个值； if(Constraint(t)andBound(t)) Backtrack(t+1); } } 执行时，从Backtrack
(1)开始。
14 算法导论 Sch2-2算法框架 z排列树回溯法 Backtrack(intt)//搜索到树的第t层{//由第t层向第t+1层扩展，确定x[t]的值 ift>nthenoutput(x);//叶子结点是可行解else fori=ttondo{ swap(x[t],x[i]);if(Constraint(t)andBound(t)) Backtrack(t+1);swap(x[t],x[i]);}} 15 算法导论 Sch2-3排列生成问题 z问题定义：给定正整数n，生成1,
2,…,n所有排列。
z解空间树（排列树）： 当n=3时， 16 算法导论 Sch2-3排列生成问题 17 算法导论 Sch2-4TSP问题 z问题描述：略 z基本思想：利用排列生成问题的回溯算法Backtrack
(2)，对x[]={1,
2,…,n}的x[2..n]进行全排列，则(x[1],x[2])，(x[2],x[3])，…,(x[n],x[1])构成一个回路。
在全排列算法的基础上，进行路径计算保存以及进行限界剪枝。
zmain(intn){a[n][n];x[n]={1,
2,…,n};bestx[];=0.0;=∞;//bestx保存当前最佳路径，保存当前最优值input(a);//输入邻接矩阵TSPBacktrack
(2);output(,bestx[]);} 18 算法导论 Sch2-4TSP问题 TSPBacktrack(inti) {//记录(x[1],x[2]),…,(x[i-1],x[i])的距离和 if(i>n){//搜索到叶结点，输出可行解与当前最优解比较 if(+a[x[n]][1]不受攻击的条件是彼此不在同行（列）、斜线上。
求出全部的放法。
z解表示： 20 算法导论 Sch2-5n皇后问题 21 算法导论 Sch2-5n皇后问题 22 算法导论 Sch2-5n皇后问题 23 算法导论 Sch2-6符号三角形问题 下图是由14个“+”和14个“-”组成的符号三角形。
2个同号下面都是“+”，2个异号下面都是“-”。
++-+-+++----+-+++-++-+-+ 在一般情况下，符号三角形的第一行有n个符号。
符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。
24 算法导论 Sch2-6符号三角形问题 z解向量：用n元组x[1:n]表示符号三角形的第一行，x[i]=1表示符号三角形的第一行第i个符号为“+”，x[i]=0表示符号三角形的第一行第i个符号为“-”。
z可行性约束函数：当前符号三角形所包含的“+”个数与“-”个数均不超过n*(n+1)/4 z无解的判断：n*(n+1)/2为奇数 ++-+-++----+++-++-+- ++-+-+++----+-+++-++-+-+ 25 算法导论 Sch2-6符号三角形问题 voidTriangle::Backtrack(intt) {//是一棵子集树,t控制着第一行符号个数，对应于树的层次 if((count>half)||(t*(t-1)/2-count>half))return;//剪枝法，剪除不必要的子树 if(t>n)sum++; //到叶子结点，”+”号数和”-”号数相同的符号三角形个数增加
1 else for(inti=0;i<2;i++){//当前扩展结点Z只有两种可能的取值0或
1，即只可能有2个孩子 p[1][t]=i; //二维数据p记录了符号三角形矩阵 count+=i; //当前符号三角形矩阵中，”+”号的个数 for(intj=2;j<=t;j++){//从第二行起计算”+”号个数，计算可行性约束 p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2]; count+=p[j][t-j+1]; } Backtrack(t+1);
//扩展到第t+1层 for(intj=2;j<=t;j++)//必须回退！因为外层for循环是对当前扩展结点两个子树分别搜索！ count-=p[j][t-j+1]; count-=i; }26} 算法导论 Sch2-6符号三角形问题 z复杂度分析： 计算可行性约束需要O(n)时间，在最坏情况下有O(2n)个结点需要计算可行性约束，故解符号三角形问题的回溯算法所需的计算时间为O(n2n)。
27 算法导论 Sch2-70-1背包问题 z问题描述：略z解表示和解空间：{(x1,x2,…,xn)|xi∈{0,1},i=1‾n}z解空间树： 28 算法导论 Sch2-70-1背包问题 z无限界函数的算法 KnapBacktrack(inti) {//cw当前背包重量，cv当前背包价值，当前最优价值 if(i>n){//搜索到可行解 =(cv:; output(x); } else{ if(cw+w[i]<=c){//走左子树 x[i]=1;cw+=w[i];cv+=v[i]; KnapBacktrack(i+1); cw-=w[i];cv-=v[i]; }//以下走右子树x[i]=0;KnapBacktrack(i+1);} main(floatc,intn,floatw[],floatv[],intx[]){//主程序 floatcw=0.0,cv=0.0,=0.0;KnapBacktrack
(1);} } 29 算法导论 Sch2-70-1背包问题 z有限界函数的算法 —基本思想： ¾设r是当前扩展结点z的右子树（或左子树）的价值上界，如果cv+r<=时，则可以裁剪掉右子树（或左子树）。
¾一种简单的确定z的左、右子树最优值上界的方法（设z为第k层结点）：左子树上界=i=k∑i=nvi，右子树上界=i=k+1∑i=nvi —求经扩展结点z的可行解价值上界的方法： ¾计算至扩展结点的当前背包价值已知xi，i=1‾k-
1，当前背包价值cv=i=1∑i=k-1vixi ¾最后，经z左子树的可行解价值上界=cv+左子树上界经z右子树的可行解价值上界=cv+右子树上界 —算法（略） 30 算法导论 Sch2-8图的m着色问题 z问题描述： 给定无向连通图G和m种不同的颜色。
用这些颜色为图G的各顶点着色，每个顶点着一种颜色。
是否有一种着色法使G中每条边的2个顶点着不同颜色。
这个问题是图的m可着色判定问题。
若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。
求一个图的色数m的问题称为图的m可着色优化问题。
z四色猜想： 在一个平面或球面上的任何地图能够只用4种颜色来着色，使相邻的国家在地图上着不同的颜色。
假设每个国家在地图上是单连通区域，两个国家相邻则其边界长度不为
0. 右图是一个有5个区域的地图及其相应的平面图。
31 算法导论 Sch2-8图的m着色问题 z解向量：(x1,x2,…,xn)表示顶点i所着颜色x[i]；z可行性约束函数：顶点i与已经着色的相邻顶点颜色不重复。
voidColor::Backtrack(intt){ if(t>n){sum++;for(inti=1;i<=n;i++)cout<对于每一个内结i=
0 点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。
因此，回溯法总的时间耗费是 ∑n−1mi(mn)=nm(mn−1)/(m−1)=O(nmn) i=0 33 算法导论 Sch2-9回溯法效率分析 通过前面具体实例的讨论容易看出，回溯算法的效率在很大程度上依赖于以下因素：
(1)产生x[t]的时间；
(2)满足显约束的x[t]值的个数；
(3)计算约束函数constraint的时间；
(4)计算上界函数bound的时间；
(5)满足约束函数和上界函数约束的所有x[k]的个数。
好的约束函数能显著地减少所生成的结点数。
但这样的约束函数往往计算量较大。
因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。
34 算法导论 Sch2-9回溯法效率分析 z对于许多问题而言，在搜索试探时选取x[i]的值顺序是任意的。
在其它条件相当的前提下，让可取值最少的x[i]优先。
从图中关于同一问题的2棵不同解空间树，可以体会到这种策略的潜力。
(a) (b) 图(a)中，从第1层剪去1棵子树，则从所有应当考虑的3元组中一次消去12个3元组。
对于图(b)，虽然同样从第1层剪去1棵子树，却只从应当考虑的3元组中消去8个3元组。
前者的效果明显比后者好。
35 算法导论 Q&
A Thanks!
36