第5章回溯法
5.回溯法概述
1
回溯法(backtrackmethod)是一种比枚举“聪明”的常用算法。
本章介绍回溯设计及其应用,并在案例的回溯求解中比较回溯相对于枚举的特点与
优势。
1.回溯的概念
5.1
有许多问题,当需要找出它的解集,或者要求回答什么解是满足某些约束条件的最佳解
时,往往使用回溯法。
回溯法有“通用解题法”的美称,是一种比枚举“聪明”的效率更高的搜索技术。回溯在
搜索过程中动态地产生问题的解空间,系统地搜索问题的所有解。如果需要,可通过比较,
在所有解中找出满足某些约束条件的最佳解。
回溯法是一种试探求解的方法:通过对问题的归纳分析,找出求解问题的一个线索,沿
着这一线索往前试探,若试探成功,即得到解;若试探失败,就逐步往回退,换其他路线再往
前试探。因此,回溯法可以形象地概括为“向前走,碰壁回头”,这样可大大缩减无效操作,提
高搜索效率。
回溯法的试探搜索是一种组织得井井有条的、能避免一些不必要搜索的枚举式搜索。
回溯法在问题的解空间树中,从根结点出发搜索解空间树,搜索至解空间树的任意一个结
点,先判断该结点是否包含问题的解;如果肯定不包含,则跳过对该结点为根的子树的搜索,
逐层向其父结点回溯;否则,进入该子树,继续搜索。
从解的角度理解,回溯法将问题的候选解按某种顺序进行枚举和检验。当发现当前候
选解不可能是解时,就选择下一个候选解。在回溯法中,放弃当前候选解,寻找下一个候选
解的过程称为回溯。如果当前候选解除了不满足问题规模要求外,满足所有其他要求,则继
续扩大当前候选解的规模,并继续试探。如果当前候选解满足包括问题规模在内的所有要
求,则该候选解就是问题的一个解。
与枚举法相比,回溯法的“聪明”之处在于能适时“回头”,若再往前走不可能得到解,就
回溯,退一步另找线路,这样可省去大量的无效操作。因此,与枚举相比,回溯更适宜于问题
规模比较大,候选解比较多的案例求解。
1.回溯描述
5.2
1.
回溯的一般方法
下面简要阐述回溯的一般方法。
回溯求解的问题P通常要能表达为:对于已知的由
n
元组(x1,x2,…,xn
)组成的一个
状态空间E={(x1,xn
xi∈i,=2,…,给定关于
n
元组中的一个分量的约
x2,…,)|si1,n},
·126· 计算机常用算法与程序设计案例教程(第3版)
束集D,要求
E
中满足
D
的全部约束条件的所有
n
元组。其中,
i
的定义域,
s是分量xi
i=
1,2,…,。称
E
中满足
D
的全部约束条件的任一
n
元组为问题P的一个解。
解问题(n) P的最朴素的方法就是枚举,即对
E
中的所有
n
元组逐一地检验其是否满足
D
的全部约束。若满足,则为问题P的一个解。显然,当P的数量规模比较大时,枚举的计算
量是相当大的。
对于约束集
D
具有完备性的问题P,一旦检测断定某个
j
元组(x1,x2,…,xj
)违反
D
中仅涉及x1,x2,…,xj
的一个约束,就可以肯定以(x1,x2,…,xj
)为前缀的任何
n
元组
(x1,xj+1,…,都不会是问题P的解,因而就不必去搜索它们,省略了对部分
x2,…,xj
,xn
)
元素(xj+1,…,)的操作与测试。回溯法正是针对这类问题,利用这类问题的上述性质而
xn
提出来的比枚举效率更高的算法。
2.4皇后问题的回溯举例
为了具体说明回溯的实施过程,先看一个简单实例。
如何在4×4 的方格棋盘上放置4个皇后,使皇后互不攻击,即任意两个皇后不允许处
在同一横排或同一纵列,也不允许处在与棋盘边框成45°角的同一斜线上。
图5-1所示为应用回溯的实施过程,其中方格中的数字表示皇后所在位置(列), 方格中
的×表示由于受前面已放置的皇后的攻击而放弃的位置。
图5-
1 4
皇后问题回溯实施
图5-1(a)为在第1行第1列放置一个皇后的初始状态。
图5-1(b)中,第2个皇后不能放置在第1、2列,因而放置在第3列。
图5-1(c)中,表示第3行的所有各列均不能放置皇后,则回溯至第2行,第2个皇后需
后移。
图5-1(d)中,第2个皇后后移到第4列,第3个皇后放置在第2列。
图5-1(e)中,第4行的所有各列均不能放置皇后,则回溯至第3行;第3个皇后后移的
所有位置均不能放置皇后,则回溯至第2行;第2个皇后已无位可退,则回溯至第1行;第1
个皇后需后移。
图5-1(中,
f) 第1个皇后后移至第2格。
图5-1(g)中,第2个皇后不能放在第1、2、3列,因而放置在第4列。
图5-1(h)中,第3个皇后放在第1列;第4个皇后不能放置在第1、2列,于是放置在第
3列。
经以上探索与回溯,得到4皇后问题的一个解:2413(第1行皇后在第2列,第2行皇
后在第4列,第3行皇后在第1列,第4行皇后在第3列)。
继续探索与回溯,可得4皇后问题的另一个解:3142。
继续探索与回溯,直到第1行的皇后至第4格后无位可退,探索结束。
3.回溯法框架描述
1)回溯描述
对于一般含参量m、n的搜索问题,回溯法框架描述如下:
输入正整数n,m,(n≥m)
i=1;a[i]=<元素初值>;
while(1)
{
for(g=1,k=i-1;k>=1;k--)
if(<约束条件1>) g=0; //检测约束条件,不满足则返回
if(g &&<约束条件2>)
printf(a[1: m]); //输出一个解
if(i<n && g)
{i++;a[i]=<取值点>;continue;}
while(a[i]==<回溯点>&& i>1) i--; //向前回溯
if(a[i]==n && i==1) break; //退出循环,结束
else a[i]=a[i]+1;
}
具体求解问题的探索搜索范围与要求不同,在应用回溯设计时,需根据问题的具体情况
确定数组元素的初值、取值点与回溯点,同时需把问题中的约束条件进行必要的分解,以适
应上述回溯流程。
其中,实施向前回溯的循环
while(a[i]==<回溯点>&& i>1) i--;
是向前回溯一步还是回溯两步或更多步,完全根据a[i]是否达到回溯点来确定。例如,回
溯点是n,i=6,当a[6]=n 时回溯到i=5;若a[5]=n 时回溯到i=4;以此类推。
以上回溯由迭代式i--;(即i=i-1;)实现,因而又称为迭代回溯。
图5-1所示的4皇后问题迭代回溯过程描述如下:
i=1;a[i]=1;
while(1)
{
g=1;for(k=i-1;k>=1;k--)
if(a[i]=a[k]|| abs(a[i]-a[k])=i-k)
g=0; //检测约束条件,不满足则返回
if(g && i==4)
printf(a[1: 4]); //输出一个解
if(i<4 && g) {i++;a[i]=1;continue;}
while(a[i]==4 && i>1) i--; //向前回溯
if(a[i]==4 && i==1) break; //退出循环结束探索
else a[i]=a[i]+1;
}
2)递归回溯
在第4章应用递归实现排列组合的设计中,我们已经知道递归也能实现回溯。递归回
第5章 回 溯 法·127·
溯通过递归尝试遍历问题的各个可能解的通路。当发现此路不通时,回溯到上一步,继续尝
试别的通路。
递归回溯描述如下:
int put(int k)
{ int i,j,u;
if( k<=<规模>)
{ u=0;
if(<约束条件>) u=1; //当u=1 时不可操作
if(u==0) //当u=0 时可操作
{ if(k==<规模>) //若已满足规模,则打印出一个解
printf(<一个解>);
else put(k+1); //调用put(k+1)
}
}
}
在调用put(k)时,当检测约束条件知不可操作(记u=1),即再往前不可能得解,此时当
然不可能输出解,也不调用put(k+1),而是回溯,返回调用put(k)之处。这就是递归回溯
的机理。
如果是主程序调用put(1),最后返回到主程序调用put(1)的后续语句,完成递归。
图5-1所示的4皇后问题迭代回溯过程描述如下:
int put(int k)
{ int i,j,u;
if(k<=4)
{ for(i=1;i<=4;i++) //探索第k 行从第1 格开始放皇后
{ a[k]=i;
for(u=0,j=1;j<=k-1;j++)
if(a[k]==a[j]|| abs(a[k]-a[j])==k-j)
u=1; //若第k 行第i 格放不下,则置u=1
if(u==0) //若第k 行第i 格可放,则检测是否满4 行
{ if(k==4) //若已放满4 行,则打印出一个解
{ s++; printf(" ");
for(j=1;j<=4;j++)
printf("%d",a[j]);
}e
lse put(k+1); //若没放满4 行,则放下一行: put(k+1)
}
}
}
}
4.回溯法的效益分析
应用回溯设计求解实际问题,由于解空间的结构差异,很难精确计算与估计回溯产生的
结点数,这是分析回溯法效率时遇到的主要困难。回溯法实际产生的结点数通常只有解空
间所有结点数的一小部分,这也是回溯法的探索效率大大高于枚举的原因所在。
回溯求解过程实质上是遍历一棵“状态树”的过程,只是这棵树不是遍历前预先建立的。
回溯法在搜索过程中,只要所激活的状态结点满足终结条件,应该把它输出或保存。由于在
回溯法求解问题时,一般要求输出问题的所有解,因此,在得到并输出一个解后并不终止,还
·128· 计算机常用算法与程序设计案例教程(第3版)
要进行回溯,以便得到问题的其他解,直至回溯到状态树的根且根的所有子结点均已被搜索
过为止。
组织解空间便于算法在求解集时更易于搜索,典型的组织方法是图或树。一旦定义了
解空间的组织方法,这个空间即可从开始结点进行搜索。
回溯法的时间通常取决于状态空间树上实际生成的那部分问题状态的数目。对于元组
长度为n 的问题,若其状态空间树中结点总数为n!,则回溯算法的最坏情形的时间复杂度
可达O(p(n)n!);若其状态空间树中结点总数为2n ,则回溯算法的最坏情形的时间复杂度
可达O(p(n)2n),其中p(n)为n 的多项式。
对于不同的实例,回溯法的计算时间有很大的差异。对于数量规模比较大的求解实
例,应用回溯法一般可在较短的时间内求得其解,可见回溯法不失为一种快速有效的
算法。
对于某一具体情况问题的回溯求解,常通过计算实际生成结点数的方法即蒙特卡罗方
法(MonteCarlo)来评估其计算效率。蒙特卡罗方法的基本思想是:在状态空间树上随机
选择一条路径(x0,x1,…,xn-1),设X 是这一路径上部分向量(x0,x1,…,xk-1)的结点,如
果在X 处不受限制的子向量数是mk ,则认为与X 同一层的其他结点不受限制的子向量数
也都是mk 。也就是说,若不受限制的x0 取值有m0 个,则该层上有m0 个结点;若不受限制
的x1 取值有m1 个,则该层上有m0m1 个结点;以此类推。由于认为在同一层上不受限制
的结点数相同,因此,该路径上实际生成的结点数估计为
m =1+m0+m0m1+m0m1m2+…
计算路径上结点数m 的蒙特卡罗算法描述如下:
//已知随机路径上取值数据m0,m1,…,mk-1
m=1;t=1;
for(j=0;j<=k-1;j++)
{ t=t*m[j];
m=m+t;
}p
rintf("%ld",m);
把所求得的随机路径上的结点数(或若干条随机路径的结点数的平均值)与状态空间树
的总结点数进行比较,由其比值可以初步看出回溯设计的效益。
5.2 桥本分数式与10数字分数式
桥本分数式是一个填数趣题,本节从桥本分数式及其引申10数字分数式这两个难度不
高的典型数式案例的求解入手,看看回溯求解的具体实现。
5.2.1 桥本分数式
1.案例背景
日本数学家桥本吉彦教授于1993年10月在我国山东举行的中日美三国数学教育研讨
会上向与会者提出以下填数趣题:把1~9这9个数字填入下式的9个方格中(数字不得重
复),使分数等式成立。
第5章 回 溯 法·129·
·130
·
计算机常用算法与程序设计案例教程(第3版
)
桥本教授当即给出了一个解答。这一填数趣题的解是否唯一
?
如果不唯一,究竟有多
少个解
?
试求出所有解答(等式左边两个分数交换次序只算一个解答)。
2.
回溯设计
我们采用回溯法逐步调整探求。把式中9个□规定一个顺序后,先在第一个□中填入
一个数字(从1开始递增)
,
然后从小到大选择一个不同于前面□中的数字填在第二个□中
,
以此类推,把9个□都填入没有重复的数字后,检验是否满足等式。若等式成立,打印所得
的解。
可见,问题的解空间是9位的整数组,其约束条件是9位数中没有相同数字且必须满足
分式的要求。
为此,设置
a
数组,式中每一□位置用一个数组元素来表示
:
a[1]
a[4]
a[7]
a[a[a[
=
a[a[
a[2]3]
+
5]6]8]9]
同时,记式中的3个分母分别为
2]3]a[3]m1=a[a[=2]×10+a[
m2=a[5]6]=a[5]×10+a[6]
a[
m3=a[a[=8]×10+a[
8]9]a[9]
所求分数等式等价于整数等式a[1]m2m3+a[4]m1m3=a[7]m1m2
成立。这一转换可以
把分数的测试转换为整数测试。
注意到等式左侧两个分数交换次序只算一个解,为避免解的重复,设a[1]<a[4]。
式中9个□各填一个数字,不允许重复。为判断数字是否重复,设置中间变量g,先赋
值g=1;
即a[=a[或a[>a[4]
,
0(
若出现某两数字相同
(
i]k]
)
1]则赋值g=重复标记)。
首先从a[1]1开始
,
i](赋值
,
i]
=逐步给a[1≤i≤9)
每一个a[赋值从1开始递增至
9,直至a[9]赋值,判断
:
=g=m2m3+a[m1m3=
(1)若i9,1,a[1]4]a[7]m1m2
同时满足,则为一组解,用
n
统计解的个数后,输出这组解。
(2)若i<
9
且g=表明还不到9个数字
,
i]从1开始赋值继续。
1,
则下一个a[
(3)若a[=9,
8]
此时,9]
再试。
9]则返回前一个数组元素a[增1赋值
(
a[又从1开始
)
若a[8]=9,则返回前一个数组元素a[7]增1赋值再试。以此类推,直到a[1]=9时,已无
法返回,意味着已全部试毕,求解结束。
按以上所描述的回溯的参量:m=n=9
。
元素初值:a[1]=1,数组元素初值取1
。
取值点:a[=各元素从1开始取值
。
i]1,
回溯点:a[=各元素取值至9后回溯
。
i]
i9]
,
a[1]>a[其中i>k
。
约束条件1:a[==k]||a[4]
,
约束条件2:i=9&
&
a[1]m2m3+a[4]m1m3=a[7]m1m2
。
3.桥本分数式回溯程序设计
//桥本分数式回溯实现,c521
//把1~9 填入□/□□+□/□□=□/□□
#include<stdio.h>
void main()
{ int g,i,k,s,a[10];
long m1,m2,m3;
i=1;a[1]=1;s=0;
while(1)
{ g=1;
for(k=i-1;k>=1;k--)
if(a[i]==a[k]) {g=0;break;} //两数相同,标记g=0
if(i==9 && g==1 && a[1]<a[4])
{ m1=a[2]*10+a[3];
m2=a[5]*10+a[6];
m3=a[8]*10+a[9];
if(a[1]*m2*m3+a[4]*m1*m3==a[7]*m1*m2) //判断等式
{ s++;printf("(%2d) ",s);
printf("%d/%ld+%d/",a[1],m1,a[4]);
printf("%ld=%d/%ld ",m2,a[7],m3);
if(s%2==0) printf("\n");
}
}i
f(i<9 && g==1)
{i++;a[i]=1;continue;} //不到9 个数,往后继续
while(a[i]==9 && i>1) i--; //往前回溯
if(a[i]==9 && i==1) break;
else a[i]++; //至第1 个数为9 时结束
}p
rintf(" 共以上%d 个解。\n",s);
}
4.程序运行结果与说明
(1) 1/26+5/78=4/39 (2) 1/32+5/96=7/84
(3) 1/32+7/96=5/48 (4) 1/78+4/39=6/52
(5) 1/96+7/48=5/32 (6) 2/68+9/34=5/17
(7) 2/68+9/51=7/34 (8) 4/56+7/98=3/21
(9) 5/26+9/78=4/13 (10) 6/34+8/51=9/27
共以上10 个解。
关于桥本分数式求解,已有应用程序设计得到9个解,显然遗失了一个解。可见在程序
设计求解时,如果程序中结构欠妥或参量设置不当,也可能造成解的遗失。
5.2.2 10数字分数式
本节推出的10数字分数式是前面桥本分数式的引申,并添加“最简真分数”的条件
限制。
1.案例提出
把0,1,2,…,9这10个数字填入下式的10个方格中。
第5章 回 溯 法·131·
要求:
(1)各数字不得重复。
(2)数字0不得填在各分数的分子或分母的首位。
(3)式中各分数为最简真分数,即分子、分母没有大于1的公因数。
这一分数等式填数趣题究竟有多少个解答? 试求出所有解答。
2.回溯设计
设置a 数组表示式中的10个数字,即
a[1]
a[2]a[3]+ a[4]
a[5]a[6]a[7]= a[8]
a[9]a[10]
同时,记式中的3个分母分别为
m1=a[2]a[3]=a[2]×10+a[3]
m2=a[5]a[6]a[7]=a[5]×100+a[6]×10+a[7]
m3=a[9]a[10]=a[9]×10+a[10]
在上述回溯设计的基础上修改若干参数:
(1)数字从9个增加到10个,因而i<9改为i<10;i==9改为i==10。
(2)数组元素取值修改为从0开始,即a[1]=0,a[i]=0。
(3)数字0不得在各分数的分子与分母的首位,即0只能在a[3]、a[6]、a[7]与a[10]
这4个数字中,因而在输出解的条件中增加a[3]a[6]a[7]a[10]=0。
此外,需增加判断3个分数是否为最简真分数的测试循环。
3.10数字分数式程序实现
//10 数字分数式,c522
#include<stdio.h>
void main()
{ int g,i,k,s,t,u,a[11]; long m1,m2,m3;
i=1;a[1]=0;s=0;
while(1)
{ g=1;
for(k=i-1;k>=1;k--)
if(a[i]==a[k]) {g=0;break;} //两数相同,标记g=0
if(i==10 && g==1 && a[3]*a[6]*a[7]*a[10]==0)
{ m1=a[2]*10+a[3];
m2=a[5]*100+a[6]*10+a[7];
m3=a[9]*10+a[10];
if(a[1]*m2*m3+a[4]*m1*m3==a[8]*m1*m2) //判断等式
{ t=0;
for(u=2;u<=9;u++) //测试3 个分数是否为真分数
{ if(a[1]%u==0 && m1%u==0) {t=1;break;}
if(a[4]%u==0 && m2%u==0) {t=1;break;}
if(a[8]%u==0 && m3%u==0) {t=1;break;}
·132· 计算机常用算法与程序设计案例教程(第3版)
}i
f(t==0)
{ printf(" %d/%ld+%d/",a[1],m1,a[4]);
printf("%ld=%d/%ld\n ",m2,a[8],m3);
}
}
}i
f(i<10 && g==1)
{i++;a[i]=0;continue;} //不到10 个数,往后继续
while(a[i]==9 && i>1) i--; //往前回溯
if(a[i]==9 && i==1) break;
else a[i]++; //至第1 个数为9 时结束
}
}
4.程序运行结果与变通
4/19+5/608=7/32
以上10数字分数式求解是在桥本分数式设计基础上变通所得的,结构完全相同。请比
较以上两个回溯设计的参数变化。
如果把问题要求中的第(3)点去掉,即不要求各分数为最简真分数,程序应如何修改?
以上桥本分数式与10数字分数式的回溯设计都能快捷地通过上机求解,速度明显快于
枚举设计。
5.3 直尺与串珠
本节应用回溯探索涉及直尺刻度分布的“古尺神奇”与环序列覆盖的“数码串珠”两个有
趣的案例。
5.3.1 古尺神奇
1.案例提出
有一把年代不明的古尺长36寸(1寸≈3.33厘米),因使用日久,尺上的刻度只剩下8
条,其余刻度均已不复存在。神奇的是,用该尺仍可一次性度量1~36的任意整数寸长度。
试确定古尺上8条刻度分布的位置。
2.回溯设计
这是一个新颖且有一定难度的实用案例。
我们探索更具一般性的尺长s,刻度数为n(s、n 均为正整数)的完全度量问题。
为了确定实现尺长s 完全度量的n 条刻度的分布位置,设置a、b 两个数组。
a 数组元素a[i]为第i 条刻度距离尺左端线的长度,约定a[0]=0以及a[n+1]=s
对应尺的左右端线。注意到尺的两端至少有一条刻度距端线为1(否则长度s-1不能度
量),不妨设a[1]=1,其余的a[i](i=2,3,…,n)在2~s-1中取数。不妨设
2≤a[2]<a[3]<…<a[n]≤s-1
从a[2]取2开始,以后a[i]从a[i-1]+1开始递增1取值,直至s-(n+1)+i 为止。
第5章 回 溯 法·133·
当i=n 时,n 条刻度连同尺的两条端线共n+2条,从n+2取2的组合数为C(n+2,2),
记为m,显然有
m =C(n+2,2)=(n+1)(n+2)
2
m 种长度赋给b 数组元素b[1],b[2],…,b[m ]。为判定某种刻度分布能否实现完全
度量,设置特征量u,对于1≤d≤s 的每一个长度d,如果在b[1]~b[m ]中存在某一元素等
于d,特征量u 值增1。
若u=s,说明从1至尺长s 的每一个整数d 都有一个b[i]相对应,即达到完全度量,于
是输出直尺的n 条刻度分布位置。
(1)若i<n,i 增1,a[i]=a[i-1]+1,继续探索。
(2)若i>1,a(i)增1,至a[i]=s-(n+1)+i 时回溯。
3.古尺刻度回溯程序设计
//尺长s,寻求n 条刻度分布回溯探索,c531
#include<stdio.h>
void main()
{ int d,i,j,k,t,u,s,m,n,a[30],b[300];
printf(" 尺长s,寻求n 条刻度分布,请确定s,n: ");
scanf("%d,%d",&s,&n);
a[0]=0;a[1]=1;a[n+1]=s;
m=(n+2)*(n+1)/2;
i=2;a[i]=2;
while(1)
{ if(i<n)
{i++; a[i]=a[i-1]+1; continue;}
else
{ for(t=0,k=0;k<=n;k++)
for(j=k+1;j<=n+1;j++)
{t++;b[t]=a[j]-a[k];} //序列部分和赋值给b 数组
for(u=0,d=1;d<=s;d++)
for(k=1;k<=m;k++)
if(b[k]==d) {u+=1;k=m;} //检验b 数组取1~s 有多少个
if(u==s) //b 数组值包括1~s 所有整数
{ if((a[n]!=s-1) || (a[n]==s-1) && (a[2]<=s-a[n-1]))
{ printf("┌"); //输出尺的上边
for(k=1;k<=s-1;k++) printf("─");
printf("┐\n");
printf("│");
for(k=1;k<=n+1;k++) //输出尺的数字标注
{ for(j=1;j<=a[k]-a[k-1]-1;j++) printf(" ");
if(k<n+1) printf("%2d",a[k]);
else printf("│\n");
}p
rintf("└"); //输出尺的下边与刻度
for(k=1;k<=n+1;k++)
·134· 计算机常用算法与程序设计案例教程(第3版)