- 数据结构编程实验（第3版）
- 吴永辉 王建德编著
- 3028字
- 2021-08-13 17:24:01
3.4 回溯法
回溯法是搜索算法中的一种控制策略，该算法从初始状态出发，运用题目给出的条件、规则，按选优条件向前搜索，以到达目标。当搜索到某一步时，发现原先选择并不优或者达不到目标，就退回一步重新选择。这种方法与第四篇中图的深度优先搜索（DFS）在本质上是一致的，只不过深度优先搜索一般用于显式图，而回溯法一般用于递归问题的求解，因此回溯法也被称为隐式图的深度优先搜索。
回溯法的应用范围很广：可用于计数，也可用于方案枚举；可用于计算最优性问题，也可用于求解所有的解答路径。
因此，本节通过实验阐述以下问题：回溯法的程序流程一般有什么特征？使用回溯法解题需要考虑哪些因素？怎样将这些思考变成回溯法的程序实现？
回溯法在求解最优性问题时的一般流程如下：
void run（当前状态）；
{
if （当前状态为边界）
{
if （当前状态为最佳目标状态）
记下最优结果；
return；
}
for ( int i=算符最小值；i<=算符最大值；++i )
{
算符i作用于当前状态，扩展出一个子状态；
if (子状态满足约束条件) && (子状态满足最优性要求)
run(子状态)；
}
}
上述算法流程需要根据试题要求做适当调整。例如，对非最优性问题，可略去当前状态是否为最佳目标状态和扩展出的子状态是否满足最优性要求的判断；若是求最长路径，可略去边界条件的判断；等等。
在使用回溯法解题时，一般需要结合题意考虑如下因素。
1）定义状态：如何描述问题求解过程中每一步的状况。为了精简程序，增加可读性，我们一般将参与子状态扩展运算的变量组合成当前状态列入值参或局部变量，以便回溯时能恢复递归前的状态，重新计算下一条路径。若这些参数的存储量大（例如数组），为避免内存溢出，则必须将其设为全局变量，且回溯前需恢复其递归前的值。
2）边界条件：在什么情况下，程序不再递归下去。如果是求满足某个特定条件的一条最佳路径，则当前状态到达边界时并不一定意味着此时就是最佳目标状态，因此还须增加判别最优目标状态的条件。
3）搜索范围：若当前子状态不满足边界条件，则扩展子状态。在这种情况下，应如何设计扩展子状态的算符值范围？换句话说，如何设定for语句中循环变量的初值和终值？
4）约束条件和最优性要求：扩展出的子状态应满足什么条件方可继续递归下去？如果是求满足某个特定条件的一条最佳路径，那么在扩展出某子状态后是否继续递归搜索下去，不仅取决于子状态是否满足约束条件，还取决于子状态是否满足最优性要求。
【3.4.1 Red and Black】是一个应用回溯法求解计数问题的简单实例。
【3.4.1 Red and Black】
有一个矩形房间，地上覆盖着正方形瓷砖。每个瓷砖都被涂成红色或黑色。一位男士站在黑色的瓷砖上，他可以向这块瓷砖的四块相邻瓷砖中的一块移动，但他不能移动到红色的瓷砖上，只能移动到黑色的瓷砖上。请编写一个程序来计算通过重复上述移动，他所能经过的黑色瓷砖数。
输入
输入包含多个测试用例。一个测试用例在第一行给出两个正整数W和H，W和H分别表示矩形房间的列数和行数，W和H不超过20。
每个测试用例接下来给出H行，每行包含W个字符。每个字符的含义如下所示：
·“.”表示黑砖；
·“#”表示红砖；
·“@”表示男子的初始位置（在每个测试用例中仅出现一次）。
两个零表示输入结束。
输出
对每个测试用例，程序输出一行，给出男子从初始瓷砖出发可以到达的瓷砖数。
试题来源：ACM Japan 2004 Domestic
在线测试：POJ 1979
试题解析
采用回溯法求解男子经过的瓷砖数。设n、m分别为矩形房间的行数和列数；(row,col)为男子的出发位置；ans为男子经过的瓷砖数，初始为0；map为房间的瓷砖图，其中map[i][j]为瓷砖(i,j)的字符；visited为访问标志，其中visited[i][j]=true，表明男子已经到过瓷砖(i,j)，递归过程为search(i,j)。其中：
1）状态为男子的当前位置(i,j)：(i,j)为子程序的值参。显然，递归调用search(row,col)后，便可得到男子经过的瓷砖数ans。
2）约束条件为(i<0||i>=n||j<0||j>=m||map[i][j]=='#'||visited[i][j])：若当前瓷砖在房间外或不可通行（“#”表示红砖）或已经访问过(visited[i][j]==true)，则回溯；否则设瓷砖(i,j)访问标志（visited[i][j]=true），男子经过的瓷砖数+1（++ans）。
3）搜索范围为（i,j）的四个相邻格点：依次递归（search(i-1,j)；search(i+1,j)；search(i,j-1)；search(i,j+1)）。
参考程序
#include <iostream> //预编译命令
#include <string>
using namespace std; //使用 C++标准程序库中的所有标识符
const int maxn=20+5, maxm=20+5; //行数和列数的上限
int n, m, ans; //当前测试用例的行数、列数和男子经过
//的瓷砖数
string map[maxn]; //当前测试用例的瓷砖图
bool visited[maxn][maxm]; //访问标志
void search(int row, int col) //递归计算男子由(row, col)出发经过
//的瓷砖数
{
if (row<0||row>=n||col<0||col>=m||map[row][col]=='#'||visited[row][col])return; //若当前瓷砖在房间外、不可通行或已经访问过，则回溯
visited[row][col] = true; //设当前格点访问标志
++ans; //累计经过的瓷砖数
search(row - 1, col); //递归(row, col)的四个相邻方向的格点
search(row + 1, col);
search(row, col - 1);
search(row, col + 1);
}
int main(void)
{
cin >> m >> n; //输入第1个测试用例的房间规模
while (n || m) {
int row, col;
for (int i = 0; i < n; i++) { //输入当前测试用例
cin >> map[i];
for (int j = 0; j < m; j++)
if (map[i][j] == '@') { //记录男子初始位置
row = i; col = j;
}
}
memset(visited, false, sizeof(visited)); //访问标志和经过的瓷砖数初始化
ans = 0;
search(row, col); //递归计算男子由(row, col)出发经过
//的瓷砖数
cout << ans << endl; //输出男子经过的瓷砖数
cin >> m >> n; //输入下一个测试用例的房间规模
}
return 0;
}
回溯法也可以枚举满足条件的所有方案。【3.4.2 The Sultan’s Successors】给出了一个经典回溯问题——八皇后问题的应用实例。
【3.4.2 The Sultan’s Successors】
Nubia的苏丹没有子女，所以她决定在她去世后把她的国家分成k个不同的部分，每个部分将由在一些测试中表现最好的人来继承，有可能某个人继承多个部分或者全部。为了确保最终只有智商最高的人成为她的继承者，苏丹设计了一个巧妙的测试。在一个喷泉飞溅和充满异香的大厅里放着k个国际象棋棋盘。在棋盘中，每一个方格用1～99范围内的数字进行编号，并提供8个宝石做的皇后棋子。每一个潜在的继承人的任务是将8个皇后放置在棋盘上，使得没有一个皇后可以攻击另一个皇后，并且对于棋盘上所选择的皇后占据的方格，要求方格内的数字总和要和苏丹选择的数字一样高。（这就是说，在棋盘上的每一行和每一列只能有一个皇后，并且在每条对角线上最多只能有一个皇后。）
请编写一个程序，输入棋盘的数量以及每个棋盘的详细情况，并确定在这些条件下每个棋盘可能的最高得分。（苏丹是一个好的棋手，也是一个优秀的数学家，她给出的数字是最高的。）
输入
输入首先在一行中给出棋盘的数量k，然后给出k个由64个数字组成的集合，每个集合由8行组成，每行8个数字，每个数字是小于100的正整数。棋盘的数量不会多于20。
输出
输出给出k个数字，表示你的k个得分，每个得分一行，向右对齐，占5个字符的宽度。
试题来源：ACM South Pacific Regionals 1991
在线测试：UVA 167
试题解析
对8×8的棋盘来说，八皇后的放置方案有多种（共92种），在每种方案中放置8个皇后的位置不尽相同。由于在每个棋盘中，每一个方格用不同的数字进行编号，因此每种放置方案的得分也会不同。所以，在输入棋盘数据前，先离线计算出八皇后在棋盘上所有可能的放置方式。然后对每一个棋盘数据，计算每种放置方式中的得分，并获得其中的最高得分。
（1）回溯搜索8个皇后在棋盘上的所有可能放置方式
我们自上而下搜索每一行。由于棋盘上每一行和每一列只能有一个皇后，并且在每条对角线上最多只能有一个皇后，因此需要标志每一列、每一条对角线是否被皇后选中。8×8的棋盘共有8列、15条左对角线和15条右对角线。
设col[i]为i列选中的标志（0≤i≤7），left[ld]为左对角线ld选中的标志（0≤ld<15），right[rd]为右对角线rd选中的标志（0≤rd<15）。
经过(r,c)的右对角线序号为rd=r+c，左对角线序号为ld=c-r+7（如图3.4-1所示），这样做可使15条左对角线和15条右对角线的序号互不相同。
图 3.4-1
当前皇后在r行的列位置为tmp[r]（0≤r≤7），p[n][i]存储第n种方式中8个皇后的列位置（0≤n≤91，0≤i≤7）。
我们采用回溯法计算八皇后的所有可能放置方式。考虑的因素如下。
1）状态：当前行序号r作为递归过程的值参；col[c]、left[ld]和right[rd]反映了求解过程中每一步的状况，但这些参数的存储量大，为避免内存溢出，将其设为全局变量，回溯时需恢复其递归前的值。
2）边界条件r==8：若搜索了所有行，则记下第n种方式中8个皇后的列位置（P[n][i]=tmp[i]，0≤i≤7），方式序号n++，回溯。
3）搜索范围0≤c≤7：若当前状态不满足边界条件，则依次搜索r行的每一列c，计算（r，c)的左、右对角线序号（ld=(c-r)+7，rd=c+r）。
4）约束条件（!col[c] & & !left[ld] & & !right[rd]）：若满足约束条件，则选中c列、左对角线ld和右对角线rd（col[c]=1,left[ld]=1,right[rd]=1），(r,c)放置皇后（tmp[r]=c），递归（r+1）。注意，递归回溯时需恢复递归前的参数（col[c]=0,left[ld]=0,right[rd]=0）。
显然，从0行出发递归，便可计算出所有方案中8个皇后的位置。
（2）主程序
1）递归计算8个皇后的n种放置方式P[i][j]（0≤i≤n-1，0≤j≤7）。
2）依次处理k个棋盘：
·读入当前棋盘数据board[][]；
·计算和输出当前棋盘的最高得分
。
参考程序
#include <cstdio>
using namespace std;
int P[1000][9]; //方式i中第j行皇后的列位置为P[i][j]
int tmp[8]; //当前方式中第i行皇后的列位置为tmp[i]
int n = 0; //方式数初始化
bool col[8] = {0}, left[15] = {0}, right[15] = {0}; //所有列和左、右对角线未被选中
void func(int r) //从r行出发，递归计算所有方案中8个
//皇后的位置
{
if (r == 8) { //若搜索了所有行
for (int i = 0; i < 8; ++i) //记下当前方式中8个皇后的列位置
P[n][i] = tmp[i];
++n; //方式数+1
return; //回溯
}
for (int c = 0; c < 8; ++c) { //依次搜索r行的每一列
int ld = (c - r) + 7; //计算(r, c)的左、右对角线序号
int rd = c + r;
if (!col[c] && !left[ld] && !right[rd]) { //若第c列和左、右对角线未选中，则选
//中c列和左、右对角线
col[c] = 1, left[ld] = 1, right[rd] = 1;
tmp[r] = c; //(r, c)放置皇后
func(r + 1); //递归下一行
col[c]=0, left[ld]=0, right[rd]=0; //撤去第c列和左、右对角线的选中标志
}
}
}
int main()
{
func(0); //从0行出发，自上而下递归计算所有
//方案中的8个皇后位置
int Case;
int board[8][8];
scanf("%d", &Case); //输入棋盘数
while (Case--) {
for (int i = 0; i < 8; ++i) //输入当前棋盘中每格的数字
for (int j = 0; j < 8; ++j)
scanf("%d", &board[i][j]);
int ans = 0;
for (int i = 0; i < n; ++i) { //依次搜索每个方式
int sum = 0; //第i个方式的得分初始化
for (int j = 0; j < 8; ++j) //搜索每一行，累计第i个方式的得分
sum += board[j][P[i][j]];
if (sum>ans) ans=sum //若当前方式的得分目前最高，则调整
//棋盘最高得分
}
printf("%5d\n", ans); //输出当前棋盘的最高得分
}
}
【3.4.2 The Sultan’s Successors】题解中的子程序func(r)，就是一个使用回溯法计算所有方案的程序范例。
【3.4.3 The Settlers of Catan】是一个使用回溯法求解最优性问题的范例。
【3.4.3 The Settlers of Catan】
1995年，在Settlers of Catan举办了一场游戏，玩家们要在一座岛屿的未知荒野上，通过构建道路、定居点和城市来控制这个岛屿。
你受雇于一家软件公司，该公司刚刚决定开发这款游戏的电脑版，要求你实现这款游戏的一条特殊规则：当游戏结束时，建造最长的道路的玩家将获得额外的两分。
问题是，玩家通常建造复杂的道路网络，而不是一条线性的路径。因此，确定最长的路不是容易的（虽然玩家们通常可以马上看出）。
和原始的游戏相比，我们仅要解决一个简化的问题：给出一个节点（城市）的集合和一个边（路段）的集合，这些连接节点的边的长度为1。
最长的道路被定义为网络中每条边都不会经过两次的最长的路径，虽然节点可以被经过超过一次。
例如，图3.4-2中的网络包含一条长度为12的道路。
图 3.4-2
输入
输入包含一个或多个测试用例。
每个测试用例的第一行给出两个整数：节点数n（2≤n≤25）和边数m（1≤m≤25）。接下来的m行描述m条边，每条边由这条边所连接的两个节点的编号表示，节点编号为0～n-1。边是无向边。节点的度最多为3。道路网不一定是连通的。
输入以n和m取0结束。
输出
对每个测试用例，在单独的一行中输出最长道路的长度。
试题来源：University of Ulm Local Contest 1998
在线测试：POJ 2258，ZOJ 1947，UVA 539
试题解析
道路网是一个无向图。由于最长道路中的每条边仅允许经过一次，因此设定无向图的相邻矩阵为
。
由于试题并未规定路径的起始点，因此需要将每个节点设为路径起始点计算路长，从中调整最长路长best。采用回溯法计算以i节点为首的路径长度，并调整best是比较适合的。
状态：求解过程中每一步的状况为目前路径的尾节点i和路长l，各条边的访问标志为a[][]。为了避免内存溢出，我们设递归过程的值参为(i,l)，将a[][]设为全局变量，但回溯时需恢复其递归前的未访问标志。
由于本题是求最长道路，路径能长则长，因此不设边界条件。
搜索范围0≤j≤n-1：可能与i节点关联的所有节点。
约束条件a[i][j]==1：若(i，j)是没有被经过的边，则撤去(i,j)的访问标志（a[i][j]=a[j][i]=0），递归(j，l+1)，回溯时恢复其递归前的未访问标志（a[i][j]=a[j][i]=1）。
搜索完与i节点关联的所有节点后，便得出以i节点为首的路径长度l。此时，调整最长路长best=max{best，l}。
显然，在主程序中设best=0，依次计算以每个节点为首的路径（即递归（i，0），0≤i≤n-1），便可以计算出最长路长best。
参考程序
#include <stdio.h>
#include <assert.h>
#define DBG(x)
FILE *input;
int n,m,best; //节点数为n，边数为m，最长路的长度为best
int a[32][32]; //无向图的邻接矩阵
int read_case() //输入测试用例信息，构造无向图的邻接矩阵
{
int i,j;
fscanf(input,"%d %d",&n,&m); //输入节点数和边数
DBG(printf("%d nodes, %d edges\n",n,m));
if (m==0 && n==0) return 0; //输入以n和m取0结束
for (i=0; i<n; i++) //邻接矩阵初始化为空
for (j=0; j<n; j++) a[i][j] = 0;
while (m--) //依次输入m条边信息， 构造无向图的邻接矩阵
{
fscanf(input,"%d %d",&i,&j);
a[i][j] = a[j][i] = 1;
}
return 1;
}
void visit (int i, int l) //递归计算当前路径（目前行至节点i，路长为l），调整
//最长路长
{
int j;
for (j=0; j<n; j++) //搜索i节点相关的未访问边
if (a[i][j]) //若（i, j）未访问，则设访问标志
{ a[i][j]= a[j][i]=0;
visit(j,l+1); //沿j节点递归下去
a[i][j] = a[j][i] = 1; //恢复（i, j）未访问标志
}
if (l>best) best=l; //若当前路长为最长，则调整最长路的长度
}
void solve_case() //计算和输出当前测试用例的解
{
int i;
best = 0; //最长路的长度初始化
for (i=0; i<n; i++) //依次递归以每个节点为首的路径，调整最长路长
visit(i,0);
printf("%d\n",best); //输出最长路长
}
int main()
{
input = fopen("catan.in","r"); //输入文件初始化
assert(input!=NULL);
while (read_case()) solve_case(); //反复输入测试用例，计算和输出解，直至程序结束
fclose(input); //关闭输入文件
return 0;
}