回溯法采用类似穷举法的搜索尝试过程,在搜索尝试过程中寻 找问题的解,当发现已不满足求解条件时就“回溯”(即回退), 尝试其 他路径,所以回溯法有“通用解题法”之称。本章介绍回溯法求解问 题的一般方法,并给出一些用回溯法求解的经典示例。本章的学习 要点和学习目标如下: (1)掌握问题解空间的结构和深度优先搜索过程。 (2)掌握回溯法的原理和算法框架。 (3)掌握剪支函数(约束函数和限界函数)设计的一般方法。 (4)掌握各种回溯法经典算法的设计过程和算法分析方法。 (5)综合运用回溯法解决一些复杂的实际问题。 5.1回溯法概述 5.1.1问题的解空间 先看看求解问题的类型,通常求解问题分为两种类型,一种类型是给定一个约束函数, 需要求所有满足约束条件的解,称为求所有解类型。例如鸡兔同笼问题中,所有鸡兔头数为 a,所有腿数为b,求所有头数为a、腿数为b的鸡兔数,设鸡兔数分别为x和y,则约束函数 是x+y=a,2x+4y=b。另外一种类型是除了约束条件外还包含目标函数,最后是求使目 标函数最大或者最小的最优解,称为求最优解类型。例如鸡兔同笼问题中,求所有鸡兔头数 为a、所有腿数为b并且鸡最少的解,这就是一个求最优解问题,除了前面的约束函数外还 包含目标函数min(x) 。这两类问题本质上是相同的,因为只有求出所有解再按目标函数 进行比较才能求出最优解。 求问题的所有解时涉及解空间的概念,在3.1节中讨论穷举法时简要介绍过解空间,这 里作进一步讨论。实际上问题的一个解是由若干个决策(即选择)步骤组成的决策序列,可 以表示成解向量x=(x0,x1,…,xn-1), 其中分量xi对应第i步的选择,通常可以有两个 或者多个取值,表示为xi∈Si(0≤i≤n-1),Si为xi的取值候选集,即Si=(vi,0,vi,1,…, vi,|Si|-1) 。x中各个分量xi所有取值的组合构成问题的解向量空间,简称为解空间,解空 间一般用树形式来组织,树中每个结点对应问题的某个状态,所以解空间也称为解空间树或 者状态空间树。 例如,对于如图5.1(a)所示的连通图,现在要求从顶点0到顶点4的所有路径(默认为 简单路径), 这是一个求所有解问题,约束条件就是0→4 的路径,由于路径是一个顶点序列, 所以对应的解向量x=(x0,x1,…,xn-1)表示一条路径,这里x0=0(没有其他选择), 需要 求出满足约束条件的其他xi(i≥1), 这里的路径有多条,每条路径对应一个解向量,对应的 解空间如图5.1(b)所示,图中i表示结点的层次,由于x0 是固定的,只需要从x1 开始求 起,所有根结点层次i=1,从中看出S1={1,3},S2={2,4},S3={4} 。在确定解空间后该 问题转换为在其中从根结点出发搜索到叶子结点并且叶子结点为顶点4的所有解,对应的 两个解为x={0,3,2,4}和x={0,3,4} 。如果问题是求从顶点0到顶点4的一条最短路 图5.一个连通图及其问题的解空间 1 148 径,属于求最优解问题,同样需要求从顶点0到顶点4的所有路径,通过对路径长度的比较 得到一条最短路径是x={0,3,4} 。 归纳起来,解空间的一般结构如图5.2所示,根结点(为第0层)的每个分支对应分量 x0的一个取值(或者说x0 的一个决策), 若x0 的候选集为S0={v0,1,…,v0,a}, 即根结点 的子树个数为|S0|,例如x0=v0,0时对应第1层的结点A0,x0=v0,1时对应第1层的结点 A1,… 。对于第1层的每个结点Ai,Ai的每个分支对应分量x1的一个取值,若x1 的取值 候选集为S1={v1,0,…,v1,b},Ai的分支数为|S1|,例如对于结点A0,当x1=v1,0时对应 第2层的结点B0,… 。以此类推,最底层是叶子结点层,叶子结点的层次为n,解空间的高度为 n+1 。从中看出第i层的结点对应xi的各种选择,从根结点到每个叶子结点有一条路径, 路径上的每个分支对应一个分量的取值,这是理解解空间的关键。 图5.2解空间的一般结构 从形式化角度看,解空间是S0×S1×…×Sn-1的笛卡儿积,例如当|S0|=|S1|=… |Sn-1|=2时解空间是一棵高度为n+1 的满二叉树。需要注意的是,问题的解空间是虚拟 的,并不需要在算法运行中真正地构造出整棵树结构,然后在该解空间中搜索问题的解。实 际上,有些问题的解空间因过于复杂或结点过多难以画出来。 5.1.2什么是回溯法 从前面的讨论看出问题的解包含在解空间中,剩下的问题就是在解空间中搜索满足约 束条件的解。所谓回溯法就是在解空间中采用深度优先搜索方法从根结点出发搜索解,与 树的遍历类似,当搜索到某个叶子结点时对应一个可能解,如果同时又满足约束条件则该可 能解是一个可行解。所以一个可行解就是从根结点到对应叶子结点的路径上所有分支的取 值,例如一个可行解为(a0,a1,…,an-1), 其图示如图5.3所示,在解空间中搜索到可行解的 部分称为搜索空间。简单地说,回溯法采用深度优先搜索方法寻找根结点到每个叶子结点 的路径,判断对应的叶子结点是否满足约束条件,如果满足该路径就构成一个解(可行解) 。 回溯法在搜索解时首先让根结点成为活结点,所谓活结点是指自身已生成但其孩子结 点没有全部生成的结点,同时也成为当前的扩展结点,所谓扩展结点是指正在产生孩子结点 的结点。在当前扩展结点处沿着纵深方向移至一个新结点,这个新结点又成为新的活结点, 并成为当前扩展结点。如果在当前扩展结点处不能再向纵深方向移动,则当前扩展结点就 成为死结点,所谓死结点是指其所有子结点均已产生的结点,此时应往回移动(回溯)至最 近的一个活结点处,并使这个活结点成为当前的扩展结点。 149 如图5.4所示,从结点A扩展出子结点B,从结点B继续扩展,当结点B的所有子结点 扩展完毕,结点B变为死结点,从结点B回退到结点A(即回溯), 通过回溯使结点A恢复 为扩展结点B之前的状态,再扩展出子结点C,此时开始做结点C的扩展,结点C就是扩展 结点,由于结点A可能还有尚未扩展的其他子结点,结点A称为活结点。 图5.3求解的搜索空间图5.4回溯过程 从上看出,求问题解的过程就是在解空间中搜索满足约束条件和目标函数的解。所以 搜索算法设计的关键点有3个: ①根据问题的特性确定结点是如何扩展的,不同的问题扩展方式是不同的。例如,求 图中从顶点s到顶点t的路径时,其扩展十分简单,就是从一个顶点找所有相邻顶点。 ②在解空间中按什么方式搜索解,实际上树的遍历主要有先根遍历和层次遍历,前者 就是深度优先搜索(DFS), 后者就是广度优先搜索(BFS ) 。回溯法就是采用深度优先搜索 解,第6章介绍的分支限界法则是采用广度优先搜索解。 ③解空间通常十分庞大,如何高效地找到问题的解,通常采用一些剪支的方法实现。 所谓剪支就是在解空间中搜索时提早终止某些分支的无效搜索,减少搜索的结点个数 但不影响最终结果,从而提高了算法的时间性能。常用的剪支策略如下。 ①可行性剪支:在扩展结点处剪去不满足约束条件的分支。例如,在鸡兔同笼问题 中,若a=3,b=8,兔数的取值范围只能是0~2,因为3只或者更多只兔子时腿数就超过8 了,不再满足约束条件。 ②最优性剪支:用限界函数剪去得不到最优解的分支。例如,在求鸡最少的鸡兔同笼 问题中,若已经求出一个可行解的鸡数为3,后面就不必搜索鸡数大于3的结点。 ③交换搜索顺序:在搜索中改变搜索的顺序,比如原先是递减顺序,可以改为递增顺 序,或者原先是无序,可以改为有序,这样可能减少搜索的总结点。 严格来说交换搜索顺序并不是一种剪支策略,而是一种对搜索方式的优化。前两种剪 支策略采用的约束函数和限界函数统称为剪支函数。归纳起来,回溯法可以简单地理解为 深度优先搜索加上剪支。因此用回溯法求解的一般步骤如下: ①针对给定的问题确定其解空间,其中一定包含所求问题的解。 ②确定结点的扩展规则。 ③采用深度优先搜索方法搜索解空间,并在搜索过程中尽可能采用剪支函数避免无效 搜索。 150 151 5.1.3 回溯法算法的时间分析 通常以回溯法的解空间中的结点个数作为算法的时间分析依据。假设解空间树共有 n+1层(根结点为第0层,叶子结点为第n 层),第1层有m0 个结点,每个结点有m1 个子 结点,则第2层有m0m1 个结点,同理,第3层有m0m1m2 个结点,以此类推,第n 层有 m0m1…mn-1个结点,则采用回溯法求所有解的算法的执行时间为T (n)=m0+m0m1+ m0m1m2+…+m0m1m2…mn-1。这是一种最坏情况下的时间分析方法,在实际中可以通 过剪支提高性能。为了估算更精确,可以选取若干条不同的随机路径,分别对各随机路径估 算结点总数,然后再取这些结点总数的平均值。通常情况下,回溯法的效率高于穷举法。 5.2 深度优先搜索 深度优先搜索是在访问一个顶点v 之后尽可能先对纵深方向进行搜索,在解空间中搜 索时类似树的先根遍历方式。 5.2.1 图的深度优先遍历 图遍历是从图中某个起始点出发访问图中所有顶点并且每个顶点仅访问一次的过程, 其顶点访问序列称为图遍历序列。采用深度优先搜索方法遍历图称为图的深度优先遍历, 得到的遍历序列称为深度优先遍历序列,其过程是从起始点v 出发,以纵向方式一步一步 沿着边访问各个顶点。例如,对于图5.1(a)所示的连通图,采用如下邻接表存储: int adj[][]={{1,3},{0},{3,4},{0,2,4},{2,3}}; 从顶点v 出发求深度优先遍历序列ans的算法如下: int visited[]; //访问标记数组 Listans; //存放一个DFS 序列 void dfs1(int adj[][],int v) { //深度优先遍历 ans.add(v); //访问顶点v visited[v]=1; for(int u:adj[v]) { //找到v 的相邻点u if(visited[u]==0) //若顶点u 尚未访问 dfs1(adj,u); //从u 出发继续搜索 } }L istdfs(int adj[][],int v) { //返回DFS 序列 ans=new ArrayList<>(); //存放一个DFS 序列 visited=new int[adj.length]; Arrays.fill(visited,0); //初始化所有元素为0 dfs1(adj,v); return ans; } 152 上述算法求得一个深度优先遍历序列为{0,1,3,2,4}。需要注意的是深度优先遍历特 指图的一种遍历方式,而深度优先搜索是一种通用的搜索方式,前者是后者的一种应用,但 目前人们往往将两者等同为一个概念。 5.2.2 深度优先遍历和回溯法的差别 深度优先遍历和回溯法都是基于深度优先搜索,但两者在处理方式上存在差异,下面通 过一个示例进行说明。 【例5-1】 对于图5.1(a)所示的连通图,求从顶点0到顶点4的所有路径。 解:采用深度优先遍历求u 到v 的所有路径时是从顶点u 出发以纵向方式进行顶点搜 索,用x 存放一条路径,用ans存放所有的路径,如果当前访问的顶点u=v,将找到的一条 路径x 添加到ans中,同时从顶点u 回退以便找其他路径,否则找到u 的所有相邻点w ,若 顶点w 尚未访问,则从w 出发继续搜索路径,当从u 出发的所有路径搜索完毕,再从u 回 退。对应的算法如下: int visited[]; List>ans; //存放所有路径 void dfs11(int adj[][],int u,int v,ArrayListx) { //深度优先遍历 x.add(u); //访问顶点u visited[u]=1; if(u==v) { //找到一条路径 ans.add(new ArrayList<>(x)); //将路径x 添加到ans 中 visited[u]=0; //置u 可以重新访问 x.remove(x.size()-1); //路径回退 return; } for(int w:adj[u]) { //找到u 的相邻点w if(visited[w]==0) //若顶点w 尚未访问 dfs11(adj,w,v,x); //从w 出发继续搜索 } visited[u]=0; /从/u 出发的所有路径找完后回退 x.remove(x.size()-1); //路径回退 }L ist>dfs1(int adj[][],int u,int v) { //求u 到v 的所有路径 ans=new ArrayList<>(); //存放所有路径 ArrayListx=new ArrayList<>(); //存放一条路径 visited=new int[adj.length]; Arrays.fill(visited,0); //初始化所有元素为0 dfs11(adj,u,v,x); return ans; } 调用上述dfs1(adj,0,4)时求出的两条路径是0→3→2→4和0→3→4。现在采用回溯 153 法,对应的解空间如图5.1(b)所示,解向量x 表示一条路径,首先将起始点u(初始u=0) 添加到x 中,再求xi(i≥1),当u=v(v=4)时对应解空间的一个叶子结点,此时x 中就是 一条满足约束条件的路径,将其添加到ans中,否则从顶点u 进行扩展,若相邻点w 尚未访 问,将w 添加到x 中,然后从w 出发进行搜索,当从w 出发的路径搜索完后再回退到顶点 u,简单地说从u 出发搜索再回到u,这就是回溯法的核心。对应的算法如下: void dfs21(int adj[][],int u,int v,ArrayListx) { //回溯法 if(u==v) //找到一条路径 ans.add(new ArrayList<>(x)); //将路径x 添加到ans 中 else { for(int w:adj[u]) { //找到u 的相邻点w if(visited[w]==0) { //若顶点w 尚未访问 x.add(w); //访问v,将v 添加到ans 中 visited[w]=1; dfs21(adj,w,v,x); //从w 出发继续搜索 visited[w]=0; //从w 回退到u x.remove(x.size()-1); } } } }L ist>dfs2(int adj[][],int u,int v) { // 求 u 到 v 的所有路径 ans=new ArrayList<>(); //存放所有路径 ArrayListx=new ArrayList<>(); //存放一条路径 visited=new int[adj.length]; Arrays.fill(visited,0); //初始化所有元素为0 x.add(u); //将起始点u 添加到x 中 visited[u]=1; dfs21(adj,u,v,x); return ans; } 调用上述dfs2(adj,0,4)时同样求出的两条路径是0→3→2→4和0→3→4。从中看出, 深度优先遍历主要考虑顶点u 的前进和回退,不需要专门表示回退到哪个顶点,而回溯法 主要考虑顶点u 扩展的子结点以及从子结点的回退,需要专门处理出发点u 和子结点w 之 间的扩展和回退关系。尽管都是采用深度优先搜索,但后者解决问题的思路更清晰,特别是 对于复杂的问题求解要方便得多。 5.2.3 实战———二叉树的所有路径(LeetCode257★) 1.问题描述 给定一棵含n(1≤n≤100)个结点的二叉树的根结点root,结点值在[-100,100]内,设 计一个算法按任意顺序返回所有从根结点到叶子结点的路径。例如,对于如图5.5所示的 扫一扫 视频讲解 154 图5.5 一棵二叉树 二叉树,返回结果是{"1->2->5","1->3"}。要求设计如下方法: public ListbinaryTreePaths(TreeNode root) { } 2.问题求解———深度优先遍历 采用深度优先遍历。从根结点root出发搜索到每个叶子结点时构成一条路径apath, 将其转换为路径字符串tmp后添加到ans中,由于是树结构,不会重复访问顶点,不必设置 访问标记数组。对应的程序如下: class Solution { Listans=new ArrayList<>(); //存放所有路径 public ListbinaryTreePaths(TreeNode root) { if(root==null) return ans; ArrayListapath=new ArrayList<>(); // 存 放 一条路径 dfs(root,apath); //DFS 求ans return ans; } void dfs(TreeNode root,ArrayList apath) { //回溯算法 apath.add(root.val); if(root.left==null && root.right==null) { //找到一条路径 String tmp=""; //路径转换为字符串 tmp+=apath.get(0); for(int i=1;ians=new ArrayList<>(); //存放所有路径 public ListbinaryTreePaths(TreeNode root) { if(root==null) return ans; ArrayListapath=new ArrayList<>(); //存放一条路径 apath.add(root.val); //将根结点添加到路径中 dfs(root,apath); //DFS 求ans return ans; } void dfs(TreeNode root,ArrayList apath) { //回溯算法 if(root.left==null && root.right==null) { //找到一条路径 String tmp=""; //路径转换为字符串 tmp+=apath.get(0); for(int i=1;in) //搜索到叶子结点,输出一个可行解 输出一个解; else { for(j=下界;j<=上界;j++){ //用j 表示x[i]的所有可能候选值 x[i]=j; //产生一个可能的解分量 … //其他操作 if(constraint(i,j) && bound(i,j)) dfs(i+1); //满足约束条件和限界函数,继续下一层 回溯x[i]; … } } } 对采用上述算法框架的几点注意事项说明如下: ① 如果i 从1开始调用上述递归框架,此时根结点为第1层,叶子结点为第n+1层。 i 也可以从0开始,这样根结点为第0层,叶子结点为第n 层,所以需要将上述代码中的 “if(i>n)”改为“if(i>=n)”。 ② 上述递归框架中通过for循环用j 枚举xi 的所有可能候选值,如果扩展路径只有两 条,可以改为两次递归调用(例如求解0/1背包问题、子集和问题等都是如此)。 ③ 这里递归框架只有i 一个参数,在实际应用中可以根据具体情况设置多个参数。 5.3.2 实战———子集(LeetCode78★★) 1.问题描述 见3.3.5节,这里采用回溯法求解。 扫一扫 视频讲解