C++算法学习之回溯法的应用

发布于：2022-05-26 15:21:09  栏目：技术文档

目录回溯1实验题目：n皇后实验题目：符号三角形回溯 堂练实验题目：森林迷宫实验题目：地图着色

回溯1

实验题目：n皇后题目描述：

N皇后的排列，每行一个不冲突；N<=13。

输入要求：

一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的

输出要求：

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

解的输出顺序为从上到下从左到右，小的优先输出

实验代码及注释:`#include<bits/stdc++.h>using namespace std;

int q[15] = { 0 }; //记录n个皇后的摆放位置// 下标为行，数组元素为列int sum = 0;int n;

void queen(int i){ int j; int col, flag;

if (i == n + 1)//所有的行全部走完，即成功找到一种解法
{
    sum++;
    if (sum <= 3) // 输出前三行结果
    {
        for (j = 1;j <= n;j++)
        {
            if (j == n)
                cout << q[j] << endl;
            else
                cout << q[j] << " ";
        }
    }
    return;
}
else
{
    for (col = 1;col <= n;col++)//遍历i行的每一列
    {
        flag = 1; // 假定棋子可放在i行col列
        for (j = 1;j < i;j++)//n遍历前i行是否符合
        {
            if (col == q[j] || i - col == j - q[j] || i + col == j + q[j])
            {
                flag = 0; //与前面棋子发生冲突
                break;
            }
        }
        if (flag == 1)//未与前面棋子发生冲突
        {
            q[i] = col;
            queen(i + 1);//遍历下一行
        }
    }
}

}int main(void){ cin >> n; memset(q, -1, sizeof(q)); //初始化棋子，-1表示未放上棋盘 queen(1); //从第一行开始遍历 cout << sum << endl; return 0;}`算法分析与知识点：

本题采用回溯算法思想来解决N皇后问题，这里用一个q[N]数组来记录棋子摆放情况：

1.算法开始, 清空棋盘，当前行设为第一行，当前列设为第一列

2.在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没有两个皇后)，若不满足，跳到第4步

3.在当前位置上满足条件的情形：

在当前位置放一个皇后，若当前行是最后一行，记录一个解；若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个待测位置；若当前行是最后一行，当前列不是最后一列，当前列设为下一列；若当前行是最后一行，当前列是最后一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置；以上返回到第2步4.在当前位置上不满足条件的情形：

若当前列不是最后一列，当前列设为下一列，返回到第2步；

若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的

下一个待测位置，返回到第2步;

实验题目：符号三角形题目描述：

符号三角形的 第1行有n个由“+”和“-”组成的符号 ，以后每行符号比上行少1个，2个同号下面是“+”，2个异号下面是“-” 。计算有多少个不同的符号三角形，使其所含“+” 和“-” 的个数相同。

输入要求：

整数n(n<=20)。

输出要求：

符合要求的符号三角形的个数。

实验代码及注释:`#include<bits/stdc++.h>using namespace std;int a[30][30] = { 0 };int n, sum = 0, sum1 = 0;

void check() { int t = n, sum2 = 0; while (t—) { for (int i = 1;i <= t;i++) { a[t][i] = 1 - (a[t + 1][i] + a[t + 1][i + 1]) % 2; // 递推第t层i列的符号 if (a[t][i])//若为＋ sum2++; } } if (2 (sum1 + sum2) == (n (n + 1) / 2)) //记录+总数是否为符号总数的一半 sum++;}void dfs(int x) { // x表示考虑顶层第x个位置的符号 for (int i = 0;i < 2;i++) { //0=>-;1=>+ if (i) sum1++; // 记录顶层+的数量 a[n][x] = i; if (x == n)//考虑完顶层的一种符号摆放，进行检查 check(); else dfs(x + 1); if (i) sum1—; // 若上摆放为+，则+数量回退1 }}int main(){ cin >> n; if ((n * (n + 1) / 2) % 2 == 1) //判断符号总数奇偶性 cout << 0 << endl; else { dfs(1); cout << sum << endl; } return 0;}`算法分析与知识点：

本题主要运用回溯的思想，这题的特点是不能输入元素，而且只要确定的顶层的n的符号的排列情况，就可以得到整个符号三角形的排列情况，因此只需要对符号三角形的顶层进行遍历就好了。题目中有要求+和-的数量要一样，所以符号三角形的符号总数要是偶数，否则解决方案数为0。

令0和1分别代表-和+，其他层在顶层确定后即确定了，不需要枚举。采用dfs对第一层的符号排列情况进行遍历，遍历完n后就可得到答案。

回溯 堂练

实验题目：森林迷宫题目描述：

一天Luna在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态：^ 和 # ；前者表示可以通行后者表示不能通行。当Luna处在某个格点时，她只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Luna想要从起点A走到终点B（中途不能走出迷宫）。如果起点或者终点有一个不能通行(为#)，则当做无法通行。

输入要求：

第1行是测试数据的组数k，后面跟着k组输入。

每组测试数据的第1行是一个正整数n (1 <= n <= 100)，表示迷宫的规模是n * n的。

接下来是一个n * n的矩阵，矩阵中的元素为 . 或者 #。

再接下来一行是4个整数ar,ac,br,bc。表示A处在第ar行，第ac列，B处在第br行, 第bc列。注意坐标ar，ac，br，bc全部是从0开始计数的类似[1,4][5,6]被认为是覆盖了[1,6]。

输出要求：

YES或NO

实验代码及注释:`#include<bits/stdc++.h>using namespace std;char s[105][105]; // 记录地图int n, ha, la, hb, lb, dir[4][2] = { {0,-1},{0,1},{-1,0},{1,0} }, flag;//flag标记搜索完毕后是否能到达终点void dfs(int ha, int la){ if (ha == hb && la == lb) // 判断是否达到终点 { flag = 1; } if (flag) { cout << “YES” << endl; return; } for (int i = 0;i < 4;i++) { int dx = ha + dir[i][0]; int dy = la + dir[i][1]; if (dx >= 0 && dx < n && dy >= 0 && dy < n && s[dx][dy] == ‘^’) { s[dx][dy] = ‘#’;//只走一次，每个方都要走一遍，只要连通，肯定能到终点 dfs(dx, dy); } }}int main(){ int k; cin >> k; while (k—) { cin >> n; for (int i = 0;i < n;i++) for (int j = 0;j < n;j++) cin >> s[i][j]; cin >> ha >> la >> hb >> lb; if (s[ha][la] == ‘#’ || s[hb][lb] == ‘#’) cout << “NO” << endl;//提前判断始点和终点是否符合要求 else { flag = 0; dfs(ha, la); //dfs搜索路径 if (flag == 0) cout << “NO” << endl; }

}
return 0;

}`算法分析与知识点：

本采用深度优先的搜索方式来搜索全部路径，大致思路为：从当前点出发，往四个方位探寻找出所有与之相邻的且尚未被访问过的点，从中暂时先选取一个点作为当前点继续上述过程，直到到达目的地或者再也无法探寻到能前进的点，再返回。如果当前搜索的点到达了目标点，flag标记为true，返回即可。若所有能到达的点都搜索完了，flag仍为false，则无法到达。

实验题目：地图着色题目描述：

给定图G=(V, E)，需要为图G的各顶点着色，是否有一种着色法使G中相邻的两个顶点有不同的颜色?

输入要求：

第一行是顶点的个数n（2≤n≤10），颜色数m（1≤m≤n）。

接下来是顶点之间的连接关系：a b；表示a和b相邻。顶点从1开始计。

当a，b同时为0时表示输入结束。

输出要求：

输出着色方案总数和最少颜色数。如果无可行方案，颜色数为0。

实验代码及注释:`#include<bits/stdc++.h>using namespace std;

define N 10

int n, sum = 0, m;int x[N + 1]; //记录可行解int g[N + 1][N + 1];//邻接矩阵int ans = N;int ok(int t) // 判断当前层节点是否可行{ for (int j = 1; j <= n; j++) if (g[t][j] == 1 && x[t] == x[j]) return 0; return 1;}

int num_m() { //计算可行解中的颜色种类数 int ans = 0; int temp[101] = { 0 }; for (int i = 1;i <= n;i++) { temp[x[i]] = 1; } for (int i = 1;i <= 100;i++) ans += temp[i]; return ans;}void back_track(int t){ int i; if (t > n) { sum++; //找到可行解，总数+1 //for (i = 1; i <= n; i++) // printf(“%d “, x[i]); // printf(“\n”); int xx = num_m(); if (xx < ans) ans = xx; } else { for (int i = 1; i <= m; i++)// 遍历节点的每种颜色取值 { x[t] = i; if (ok(t)) back_track(t + 1); x[t] = 0; } }}

int main(){ cin >> n >> m; //n个顶点，m种颜色

int a, b;
cin >> a >> b;
while (!(a == 0 && b == 0)) { //构造邻接矩阵
    g[a][b] = 1;
    g[b][a] = 1;
    cin >> a >> b;
}
back_track(1);
if (sum)
    cout << sum << " " << ans << endl;
else
    cout << 0 << " " << 0 << endl;
return 0;

}`算法分析与知识点：

这个问题和八皇后还有求子集和等问题都具有类似之处，其核心在通过遍历找到所有的问题子集 ，但是在递归遍历的时候，都在加一个判断，将那些明显不满足条件的情况给直接排出，减少问题的规模，其实这类问题，在递归遍历的时候都是类似与对一颗树的便利每个节点相当走到此时的状态，然后再判断此时的状态是否能继续走下去，如果不能就将其回溯到上一个节点，避免浪费时间。

给定图g（v，e）和m种颜色，如果这个图不是m可着色，给出否定回答，是的话找出所有不同着色法。

分析：

用邻接矩阵表示图g，如果顶点i跟j之间有边，则g[i][j] = 1,否则g[i][j] = 0.用整数1，2，…，m表示m种颜色，顶点i的颜色用x[i]表示，所以x[1：n]是一种着色方案。

在算法traceback中，当i>n时，就是所有顶点都上了色，得到新的m着色方案，当前m着色方案总数sum增一，输出方案。

当i<n时，就是未着色完所有顶点，当前顶点i有x[i] = 1, 2…m种颜色可图，对于每种颜色由函数ok判断可行性，并用dfs对可行颜色搜索，或减去不可行方案。

相关推荐