第
5
章
回溯法
..5.1概述
在现实世界中,很多问题没有(至少目前没有)有效的算法,这些问题的求
解只能通过蛮力穷举搜索来实现。但蛮力法需要生成并评估所有的解,执行效
率低下。
回溯法(BackTrackingMethod)是一种深度优先搜索算法,该方法试图穷
举所有可能的解,因此,回溯法能够确保获得最优解。在搜索过程中根据问题
约束等规则对搜索树进行剪枝操作,跳过部分搜索区域,提高算法性能。回溯
法按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并
不优或达不到目标,就退回一步重新选择,这种走不通就退回再选择另外一个
方向试探的技术即为回溯法,满足回溯条件的某个状态的点称为“回溯点”。回
溯法把问题的解空间转化成了图或者树的结构表示,然后使用深度优先搜索策
略进行遍历,遍历的过程中记录和寻找所有可行解或者最优解。
..5.回溯法设计思路
2
复杂问题常常有很多可能解,这些可能解构成问题的解空间,也就是在穷
举法中提到的所有可能解的搜索空间。一般而言,解空间中应该包括所有的可
能解。
回溯法按深度优先策略搜索问题的解空间树。首先从根结点出发搜索解
空间树,当算法搜索至解空间树的某一结点时,先利用剪枝函数判断该结点是
否可行(即能得到问题的解)。如果不可行,则跳过对该结点为根的子树的搜
索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。
..5.回溯法示例与过程分析
3
5.1 n
皇后问题
3.
例5.1
在n×n
格的国际象棋棋盘上摆放
n
个皇后( 1, 8),
见图5.此时n=
82算法设计与问题求解(微课版)
图5.1八皇后问题示意图
使其不能互相攻击,即任意两个皇后都不能处于
同一行、同一列或同一斜线上,有多少种摆法?
n皇后是由八皇后问题演变而来的。该问题
由国际象棋棋手马克斯·贝瑟尔于1848 年提出:
在8×8 格的国际象棋棋盘上摆放8个皇后,使其
不能互相攻击,即任意两个皇后都不能处于同一
行、同一列或同一斜线上,求有多少种摆法。高斯
认为有76 种方案。1854 年在柏林的象棋杂志上
不同的作者发表了40 种不同的解,后来有人用图
论的方法解出92 种结果。
下面用数组模拟棋盘,从第一行开始,依次选
择位置,如果当前位置满足条件,则向下选位置,
如果不满足条件,那么当前位置后移一位。以四皇后为例,从第一行开始,依次选择位置,
如果当前位置满足条件,则向下选位置,如果不满足条件,那么返回上一步。
如图5.2(a)所示,第一个皇后放置于第一行第一列(1-1), 则第二个皇后可放置于
(2-3), 此时第三个皇后所有位置均不可放置,返回上一步。
图5.四皇后问题回溯模拟图
2
第5章 回溯法 83
如图5.2(b)所示,第二个皇后放置于(2-4),则第三个皇后可放置于(3-2),此时第四
个皇后所有位置均不可放置,返回上一步。
如图5.2(c)所示,第一个皇后放置于(1-2),则第二、三、四个皇后可顺利放置于
(2-4)、(3-1)、(4-3)中,得到一个可行解。
同理,如图5.2(d)所示,第一个皇后放置于(1-3),则第二、三、四个皇后可顺利放置于
(2-1)、(3-4)、(4-2)中,得到第二个可行解。
值得注意的是,问题的求解并不需要用n×n 的数组来表示结果,而只需要一个n 长
度的数组来表示每一行的皇后位置即可,即arr[i]=k,表示第i 行的皇后位置为k。此
时使用一个arr[n]的数组就可以表示一个解,通过回溯可以使我们得到所有可行解。
n 皇后问题的回溯法算法如下所示。
//输入: n,表示皇后个数
//输出: n 皇后问题的所有可行解
1. 初始化解向量arr[i]={-1}
2. i=1
3. while(i>=1)
3.1 把皇后i 摆放在下一列,即arr[i]++
3.2 从arr[i]位置开始依次考察每一列,如果皇后i 摆放在arr[i]位置不发生冲突,则转3.3
步骤;否则arr[i]++试探下一列
3.3 若n 个皇后已全部摆放,则输出一个解,算法结束
3.4 若尚有皇后未摆放,则转步骤3 摆放下一个皇后
3.5 若arr[i]出界,则回溯,即arr[i]=-1,i--,转步骤3 重新摆放皇后i
4. 退出循环,说明n 皇后问题无解
0-1背包问题
5.3.2 0-1背包问题
例5.2 有一个背包,最多能承载10kg,现在有3个物品,质量分别为[4,8,5]、价值
分别为[24,40,20],详情如表5.1所示。那么应该如何选择才能使得你的背包背走最多
价值的物品?
表5.1 0-1背包问题示例
物品质量(w)/kg 价值(v)/元价值/质量(v/w)
1 4 24 6
2 8 40 5
3 5 20 4
0-1背包问题属于最优解问题,用回溯法需要构造解的子集树。对于每一个物品i,
该物品只有选与不选2个决策,总共有n 个物品,可以顺序依次考虑每个物品,这样就形
成了一棵解空间树。求解的基本思想就是遍历这棵树,以枚举所有情况,最后进行判断,
如果质量不超过背包容量,且价值最大的话,该方案就是最后的答案。
84 算法设计与问题求解(微课版)
0-1背包问题的回溯法解空间树如图5.3所示。
图5.3 0-1背包问题的回溯法解空间树
0-1背包问题的回溯法求解过程如下。
(1)选择物品1,此时背包的质量为4,价值为24。
(2)选择物品2,此时背包的质量为12,超出背包容量,因此物品2不可选择,回溯至
结点2。
(3)不选择物品2,行至结点6;选择物品3,行至结点7,此时背包的质量为9,价值为
44,由于已达叶子结点,则得到可行解(1,0,1),即该解选择物品1与3。
(4)回溯至结点6,不选择物品3,则得到可行解(1,0,0),即该解选择物品1,总价值
为24,小于先前最优解44。
(5)回溯至结点1,不选择物品1,行至结点9。
(6)选择物品2,此时背包的质量为8,价值为40,行至结点10。
(7)选择物品3,行至结点11,超出背包容量,回溯至结点10。
(8)不选择物品3,行至结点12,则得到可行解(0,1,0),即该解选择物品2,总价值为
40,小于先前最优解44。
(9)回溯至结点9,不选择物品2,行至结点13。
(10)选择物品3,此时背包的质量为5,价值为20,行至结点14,则得到可行解(0,0,1),
即该解选择物品3,总价值为20,小于先前最优解44。
(11)回溯至结点13,不选择物品3,行至结点15,则得到可行解(0,0,0),即该解不选
择任何物品,总价值为0,小于先前最优解44。
(12)解空间树遍历完毕,输出最优解(1,0,1),总价值为44。
0-1背包问题的回溯法算法如下所示。
//输入: 背包的最大容量C,物品个数n,每一个物品的质量wi,价值vi
//输出: 问题的最优解选择的物品x0[],总价值max
rv=0;rw=0; //未考虑的物品总价值与总质量初始化
knapsack(k,r,cv,rc,rw) //k 为解空间树的层数,r 为背包当前剩余容量,cv 为当前结
//点已装入背包物品的总价值
第5章 回溯法 85
if r>=0 and cv>max then //找到并更新最优解
max = cv; x0[]= x[1..k]; x0[k+1..n]= 0;
end if
if rw<=r then //剪枝
if cv+rv>max then
max=cv+rv; x0[]= x[1..k]; x0[k+1..n]= 0;
end if
else
if r>0 and cv+rv>max then
rv=rv-v[k+1]; rw=rw-w[k+1];
x[k+1]=0;
knapsack(k+1,r,cv,rc,rw); //搜索左子树
x[k+1]=1;
knapsack(k+1,r-w[k+1],cv+v[k+1];,rc,rw); //搜索右子树
end if
end if
end knapsack
图的m 着
色问题
5.3.3 图的m 着色问题
例5.3 给定无向连通图G=(V,E)和正整数m ,求最小的整数m ,使得用m 种颜色
对G 中的顶点着色后任意两个相邻顶点着色不同。
用m 种颜色为无向图G=(V,E)着色,其中,V 的顶点个数为n,可以用一个n 元组
C=(c1,c2,…,cn)来描述图的一种可能着色,其中,ci∈{1,2,…,m }(1≤i≤n)表示赋予
顶点i 的颜色。
如图5.4(a)所示,有A、B、C、D、E共5个顶点组成的无向图G,如果采用图5.4(b)的
着色方法,可以看到相邻顶点B、C着色相同,因此该解为错误解;如果采用图5.4(c)的着
色方法,则满足题目条件,因此该解为可行解。
图5.4 图的m 着色问题示例
以图5.4(a)为例,图的m 着色问题的解空间树搜索过程如下。
(1)A=1,即顶点A 着色1。
(2)B=1,即顶点B着色1,而A、B两顶点相邻,不满足题意,因此进行回溯。
86 算法设计与问题求解(微课版)
(3)B=2,即顶点B着色2。
(4)C=1,即顶点C着色1,而A、C两顶点相邻,不满足题意,因此进行回溯。
(5)C=2,即顶点C着色2,而B、C两顶点相邻,不满足题意,因此进行回溯。
(6)C=3,即顶点C着色3。
(7)D=1,即顶点D着色1。
图5.5 图的m 着色问题解
空间树搜索过程
(8)E=1,即顶点E着色1,而D、E两顶点相邻,不满足
题意,因此进行回溯。
(9)E=2,即顶点E着色2,而B、E两顶点相邻,不满足
题意,因此进行回溯。
(10)E=3,即顶点E着色3,而C、E两顶点相邻,不满足
题意,因此进行回溯。
(11)E=3,即顶点E着色3,而C、E两顶点相邻,不满足
题意,因此进行回溯。
(12)D=2,即顶点D着色2,而B、D两顶点相邻,不满足
题意,因此进行回溯。
(13)D=3,即顶点D着色3。
(14)E=1,即顶点D着色1,此时所有顶点均完成着色,
且满足题意,得到可行解5元组(1,2,3,3,1)。
图的m 着色问题的解空间树搜索过程如图5.5所示。
图的m 着色问题的回溯法算法如下所示。
//输入: 无向图点与边之间的关系(邻接矩阵),m 种颜色
//输出: 无向图各顶点的着色记录color[n]
1 将数组color[n]初始化为0
2 k=0; //第一个顶点
3 while(k>=0)
3.1 依次考察每一种颜色,若顶点k 的着色与其他顶点的着色不发生冲突,则转步骤3.2;否则,
搜索下一个颜色
3.2 若顶点已全部着色,则输出数组color[n],返回
3.3 否则
3.3.1 若顶点k 是合法着色,则k=k+1,转步骤3 处理下一顶点
3.3.2 否则,重置顶点k 的着色情况,k=k-1,转步骤3 回溯
5.3.4 批处理作业调度问题
例5.4 设有n 个作业{1,2,…,n}要在两台机器上处理,每个作业要先在机器1上
处理,再在机器2上处理,请给出一种作业调度方案,使得所有任务完成的总时间最短。
对于这个问题,不难想到一个最优调度应使机器1没有空闲时间,且机器2的空闲时
间最小。
我们给出一个实例,现有3个作业{1,2,3},在机器1上所需的处理时间为(2,3,2),
第5章回溯法87
在机器2上所需的处理时间为(1,1,3) 。如果以图5.6的调度方案,即作业处理顺序为
1、2、3,则完成时间为10;如果以图5.7的调度方案,即作业处理顺序为1、3、2,则完成时
间为8。调度方案与处理过程描述如下。
图5.6批处理作业调度方案一
图5.7批处理作业调度方案二
1.调度方案一
(1)机器1处理作业1,时间为0~2,此时机器2空闲。
(2)机器1处理作业2,时间为2~5;机器2处理作业1,时间为2~3,到时间3时,机
器2空闲。
(3)机器1处理作业3,时间为5~7;机器2处理作业2,时间为5~6,到时间7时,机
器2空闲。
(4)机器2作业3,时间为7~10,完成全部作业。
2.
调度方案二
(1)机器1处理作业1,时间为0~2,此时机器2空闲。
(2)机器1处理作业3,时间为2~4;机器2处理作业1,时间为2~3,到时间3时,机
器2空闲。
(3)机器1处理作业2,时间为4~7;机器2处理作业3,时间为4~7,机器2无空闲。
(4)机器2处理作业2,时间为7~8,完成全部作业。
由上述两种调度方案可以看出,方案一中机器2的总空闲时间为5,方案二中机器2
的总空闲时间为3,因此方案二比方案一节省了时间2,验证了我们之前的设想。
为了求解该问题,我们进行如下假设。
x[:表示
n
个作业批处理的调度方案。
n]
k]: 表示第
k
个作业的编号
。
x[
n]:机器1当前完成时间
。
sum1[
sum2[:机器2当前完成时间
。
n]
sum1[:安排第
k
个作业后
,
k]机器1完成时间。
88 算法设计与问题求解(微课版)
sum2[k]:安排第k 个作业后,机器2完成时间。
则:
sum1[k]=sum1[k-1]+作业x[k]在机器1的处理时间。
sum2[k]=max{sum1[k],sum2[k-1]}+作业x[k]在机器2的处理时间。
批处理作业调度问题的回溯算法可表示如下。
//输入: n 个作业在机器1 上的处理时间a[n],在机器2 上的处理时间b[n]
//输出: 最优调度序列x[n]
1.初始化解向量x[n]={-1};最短完成时间bestTime=MAX;
2.初始化调度方案中机器1 和机器2 的完成时间
sum1[n]=sum2[n]={0}; k=1
3. while(k>=1)
3.1 依次考察每一个作业,如果作业x[k]尚未处理,则转步骤3.2,否则尝试下一个作业,即
x[k]++
3.2 处理作业x[k]:
3.2.1 sum1[k]=sum1[k]+a[x[k]]
3.2.2 sum2[k]=max{sum1[k],sum2[k-1]}+b[x[k]]
3.2.3 若sum2[k]<bestTime,则转步骤3.3,否则实施剪枝
3.3 若n 个作业已全部处理,则输出一个解;
3.4 若尚有作业没被处理,则k++,转步骤3 处理下一个作业
3.5 回溯,x[k]= -1, k--, 转步骤3 重新处理第k 个作业
.. 5.4 能力拓展
5.4.1 全排列问题
例5.5 规定n 的全排列是自然数1到n 的所有不重复排列。现在给出n,要求输出
n 的全排列。
问题分析:首先考虑规模较小情况,当n=3时,全排列为{123,132,213,231,312,
321}。由于问题要求输出所有不重复的情况,因此很容易就想到可以采用枚举的方法输
出所有的情况。
题目明确要求将n 个数放置在n 个位置上,所以可以枚举n 个位置,在每个位置上
填入n 个数放到当前位置上,同时还需要保证不跟之前已填入的数重复,所以在求解过
程中还要记录前面已经填入的数来确保没有重复情况。当将n 个数放完之后,就可以输
出一个结果,然后向上回溯遍历其他情况。
以n=3为例,回溯法的解决思路如下(见图5.8)。
(1)在位置1中填入数字1,位置2中填入数字2,位置3中填入数字3,此时已填入n
个数字,到达叶子结点,可输出结果123。
(2)回溯至位置2,在位置2中填入数字3,位置3中填入数字2,此时已填入n 个数
字,可输出结果132。
第5章回溯法89
图5.8回溯法求解全排列问题示意图
(3)回溯至位置1,在位置1中填入数字2,位置2中填入数字1,位置3中填入数字
3,此时已填入n个数字,可输出结果213 。
(4)回溯至位置2,在位置2中填入数字3,位置3中填入数字1,此时已填入n个数
字,可输出结果231 。
(5)回溯至位置1,在位置1中填入数字3,位置2中填入数字1,位置3中填入数字
2,此时已填入n个数字,可输出结果312 。
(6)回溯至位置2,在位置2中填入数字2,位置3中填入数字1,此时已填入n个数
字,可输出结果321 。
4.存在障碍物的迷宫问题
5.2
例5.给定一个n×m
的迷宫,迷宫中有些格子存在障碍物,无法移动到这个格子
6
里面,其余格子均为空。求从起点到终点至少需要多少步。规定每次移动只能水平或垂
直移动。
输入描述:第一行输入两个整数n、m,表示迷宫的行数和列数。
接下来
n
行,每行输入
m
个字符,表示整个迷宫。
空的格子用“.表(”) 示,有障碍物的格子用#表示。
起点用S表示,终点用T表示。
首先利用图5.
9所示问题来进行分析。位置S表示迷宫起
点,位置T表示迷宫终点,#表示该位置有障碍物,“.表(”) 示该位
置可到达。
由于起点和终点位置未知,因此需要先遍历找出起点S和
终点T的位置。根据题目要求,我们只能水平或垂直移动,所以
在移动的过程中只有上、下、左、右4个方向。每次移动时枚举
这4种情况,并判断是否会出界。因为要求找到从起点S到终
点T的最短距离,所以还需要对当前所在位置的步数进行标记, 9
每次移动完毕后判断此时走到该点的步数是否小于上次途径该
图5.存在障碍物的
迷宫问题示例
点的频数,不小于则向上回溯,小于则继续向下走。同时,当走
90算法设计与问题求解(微课版)
到一个无法再移动的点时也需要向上回溯(表明迷宫中此处不通) 。如果移动至终点,则
更新最短路径结果,并向上回溯其他的情况。
以图5.9为例,回溯法的求解思路如下。
(1)遍历整个二维数组(迷宫中所有位置), 找出起点S和终点T。
(2)从起点S(1,1)出发,假设以上左下右的优先方式进行移动,结合不能越界、不能
通过障碍物的约束条件,向下依次经过(2,1) 、(3,1) 、(4,1) 、(5,1), 无法再移动,回溯至
(4,1), 同样无法再移动,回溯至(3,1) 。
(3)从位置(3,1)向右移动至(3,2) 、(3,3), 并依次向上移动至(2,3), 向右移动至
(2,4), 向上移动至(1,4), 此时无法再移动,回溯至(2,4), 并向下通过(3,4) 、再向下到达
终点(4,4), 此时路径长度结果为8。
(4)回溯至位置(3,3), 以上左下右的优先方式依次经过(4,3) 、(5,3) 、(5,4)并到达
终点(4,4), 此时路径长度结果为8。
(5)回溯至位置(4,3), 并直接向右到达终点(4,4), 此时路径长度结果为6,更新最短
路径结果。
(6)再次回溯至位置(3,3), 并经过(3,4)到达终点(4,4), 此时路径长度结果也为6。
5.4.3图的m着色问题变种
例5.7我们规定字母表示一个电台,数字则表示广播电台的无线频谱。如果相邻两
个电台之间运用同样的无线频谱就会互相干扰。所以只有所有相邻电台运用的都是不同
的无线频谱,所有电台才能都正常运作。最少需要多少个无线频谱才能让所有电台都正
常运作?
本题跟图的
m
着色问题类似,但是该题要求的是至少需要多少种颜色才能让每个相
邻点之间颜色不相同(最少需要多少种无线频谱才能
使相邻的电台互不干扰)。
以图5.电台A与电台B、电台B
10 为例,C相邻,
与电台A、C、D相邻,电台C与电台A、B、D相邻,电台
D与电台B、C相邻。
回溯法的求解思路如下。图5.10
图的
m
着色问题变种示例
(1)对A点(电台A)进行操作,因为至少需要一
种无线频谱,所以sum=1,此时A点相邻的B、C两点均未给定无线频谱,因此遍历B点。
(2)将无线频谱1给予B点,发现存在A点与它相邻并且无线频谱相同。所以B点
不能使用无线频谱1,我们需要加入一个新的无线频谱才能让B点拥有无线频谱并且满
足条件。因此,给B点无线频谱2,此时其他相邻点的无线频谱均与其不同。
sum++,
(3)同上将无线频谱1给予C点,发现存在相邻点A与之干扰,将无线频谱2给予C
点,同时发现存在相邻点B与之干扰,所以加入一个新的无线频谱3给予C点,sum++,
此时其他相邻点的无线频谱均与其不同。
(4)此时我们发现对于D点来说,使用无线频谱1即可满足所有约束条件。
(5)完成所有电台的无线频谱安排,输出结果“最少需要3种无线频谱”。