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

目录
  • 回溯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对可行颜色搜索,或减去不可行方案。

以上就是C++算法学习之回溯法的应用的详细内容,更多关于C++回溯法的资料请关注我们其它相关文章!

(0)

相关推荐

  • C++回溯法实例分析

    本文实例讲述了C++的回溯法,分享给大家供大家参考之用.具体方法分析如下: 一般来说,回溯法是一种枚举状态空间中所有可能状态的系统方法,它是一个一般性的算法框架. 解向量a=(a1, a2, ..., an),其中每个元素ai取自一个有限序列集Si,这样的解向量可以表示一个排列,其中ai是排列中的第i个元素,也可以表示子集S,其中ai为真当且仅当全集中的第i个元素在S中:甚至可以表示游戏的行动序列或者图中的路径. 在回溯法的每一步,我们从一个给定的部分解a={a1, a2, ..., ak}开始

  • c++回溯法解决1到9之间插入加减或空使运算结果为100

    目录 问题分析 代码展示 问题分析 这时我最近偶然看到的一道题目,发现实现起来还确实有些麻烦,所以把实现的过程记录下来. 这种要罗列出所有结果的问题,我一般是采用回溯法解决的,说的通俗一点就是暴力解法,去遍历所有的情况. 这个问题有一点比较难处理的地方就在于有这个"什么都不插入"这个选项,所以干脆单独拎出来解决.也就是先把1-9这9个数组相互组合,形成一个数组,比如: {1,2,3,4,5,6,7,8,9} {1,2,3,4,5,6,7,89} {1,2,3,4,5,6,78,9} {

  • C语言回溯法解八皇后问题(八皇后算法)

    八皇后问题(N皇后问题)的回溯法求解 一.问题描述 在一个国际象棋棋盘上放置八个皇后,使得任何两个皇后之间不相互攻击,求出所有的布棋方法,并推广到N皇后情况. 二.参考资料 啥文字都不用看,B站上有个非常详细的动画视频解说,上链接!!! Click Here! 三.源代码 #include<iostream> #include<vector> #include<string> using namespace std; void put_queen(int x, int

  • C++基于回溯法解决八皇后问题示例

    本文实例讲述了C++基于回溯法解决八皇后问题的方法.分享给大家供大家参考,具体如下: 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯:否则,进入该子树,继续按深度优先策略搜索. 回溯法指导思想--走不通,就掉头.设计过程:确

  • C语言八皇后问题解决方法示例【暴力法与回溯法】

    本文实例讲述了C语言八皇后问题解决方法.分享给大家供大家参考,具体如下: 1.概述: 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上. 2.暴力法求解: #include<cstdio> #include<cmath> const int maxn=11; int count=0; //P为当前排列,hashTable记录整数x是否已经在

  • C语言回溯法 实现组合数 从N个数中选择M个数

    前言 在平时的算法的题目中,时常会遇到组合数相关的问题,暴力枚举.在N个数中挑选M个数出来.利用for循环也可以处理,但是可拓展性不强,于是写这个模板供以后参考. 两个函数和全局变量可以直接用. 代码: #include<iostream> #include<cstdio> #define N 10    //被选择的数目 #define M 5    //要选出来的数目 using namespace std; int vis[N+1];    //标志, int ans=0; 

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

    目录 回溯1 实验题目:n皇后 实验题目:符号三角形 回溯 堂练 实验题目:森林迷宫 实验题目:地图着色 回溯1 实验题目:n皇后 题目描述: N皇后的排列,每行一个不冲突:N<=13. 输入要求: 一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的 输出要求: 前三行为前三个解,每个解的两个数字之间用一个空格隔开.第四行只有一个数字,表示解的总数. 解的输出顺序为从上到下从左到右,小的优先输出 实验代码及注释: #include<bits/stdc++.h>

  • 算法详解之回溯法具体实现

    理论辅助: 回溯算法也叫试探法,它是一种系统地搜索问题的解的方法.回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试.用回溯算法解决问题的一般步骤为: 1.定义一个解空间,它包含问题的解. 2.利用适于搜索的方法组织解空间. 3.利用深度优先法搜索解空间. 4.利用限界函数避免移动到不可能产生解的子空间. 问题的解空间通常是在搜索问题的解的过程中动态产生的,这是回溯算法的一个重要特性. 还是那个基调,不喜欢纯理论的东西,喜欢使用例子来讲诉理论,在算法系列总结:动态规划(

  • Python基于回溯法子集树模板实现8皇后问题

    本文实例讲述了Python基于回溯法子集树模板实现8皇后问题.分享给大家供大家参考,具体如下: 问题 8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 分析 为了简化问题,考虑到8个皇后不同行,则每一行放置一个皇后,每一行的皇后可以放置于第0.1.2.....7列,我们认为每一行的皇后有8种状态.那么,我们只要套用子集树模板,从第0行开始,自上而下,对每一行的皇后,遍历它的8个状态即可. 代码: ''' 8皇后问题 '''

  • PHP实现基于回溯法求解迷宫问题的方法详解

    本文实例讲述了PHP实现基于回溯法求解迷宫问题的方法.分享给大家供大家参考,具体如下: 引言 最近在leetcode上看了些算法题,有些看着很简单的很常用的东西,竟然一下子想不出来怎么求解,比如说:实现sqrt函数,求数组的排列.如果高数学的不好,这些看似简单的问题,第一次碰到也会感觉很难求解,当然了,今天要说的是这样一个问题,求解迷宫的所有解,这个问题的求解用到了回溯法的思想,不了解这个思想的话,很多稍微复杂点的问题都很难解了. 问题描述 这个问题是在实在瞎逛的时候碰到的,具体哪里记不太清了.

  • Python基于回溯法子集树模板解决0-1背包问题实例

    本文实例讲述了Python基于回溯法子集树模板解决0-1背包问题.分享给大家供大家参考,具体如下: 问题 给定N个物品和一个背包.物品i的重量是Wi,其价值位Vi ,背包的容量为C.问应该如何选择装入背包的物品,使得放入背包的物品的总价值为最大? 分析 显然,放入背包的物品,是N个物品的所有子集的其中之一.N个物品中每一个物品,都有选择.不选择两种状态.因此,只需要对每一个物品的这两种状态进行遍历. 解是一个长度固定的N元0,1数组. 套用回溯法子集树模板,做起来不要太爽!!! 代码 '''0-

  • Python基于回溯法子集树模板解决取物搭配问题实例

    本文实例讲述了Python基于回溯法子集树模板解决取物搭配问题.分享给大家供大家参考,具体如下: 问题 有5件不同的上衣,3条不同的裤子,4顶不同的帽子,从中取出一顶帽子.一件上衣和一条裤子作为一种搭配,问有多少种不同的搭配? 分析 换个角度看,现有头.身.腿三个元素,每个元素都有各自的几种状态. 头元素有['帽1', '帽2', '帽3', '帽4']共4种状态,身元素有['衣1', '衣2', '衣3', '衣4', '衣5']共5种状态,腿元素有['裤1', '裤2', '裤3']共3种状

  • Python基于回溯法子集树模板解决数字组合问题实例

    本文实例讲述了Python基于回溯法子集树模板解决数字组合问题.分享给大家供大家参考,具体如下: 问题 找出从自然数1.2.3.....n中任取r个数的所有组合. 例如,n=5,r=3的所有组合为: 1,2,3 1,2,4 1,2,5 1,3,4 1,3,5 1,4,5 2,3,4 2,3,5 2,4,5 3,4,5 分析 换个角度,r=3的所有组合,相当于元素个数为3的所有子集.因此,在遍历子集树的时候,对元素个数不为3的子树剪枝即可. 注意,这里不妨使用固定长度的解. 直接套用子集树模板.

  • Python使用回溯法子集树模板解决迷宫问题示例

    本文实例讲述了Python使用回溯法解决迷宫问题.分享给大家供大家参考,具体如下: 问题 给定一个迷宫,入口已知.问是否有路径从入口到出口,若有则输出一条这样的路径.注意移动可以从上.下.左.右.上左.上右.下左.下右八个方向进行.迷宫输入0表示可走,输入1表示墙.为方便起见,用1将迷宫围起来避免边界问题. 分析 考虑到左.右是相对的,因此修改为:北.东北.东.东南.南.西南.西.西北八个方向.在任意一格内,有8个方向可以选择,亦即8种状态可选.因此从入口格子开始,每进入一格都要遍历这8种状态.

随机推荐