关键词：
实际上回溯法有暴力破解的意思在里面，解决一个问题，一路走到底，路无法通，返回寻找另 一条路。
回溯法可以解决很多的问题，如：N皇后问题和迷宫问题。
一.概念
回溯算法实际类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现不满足条件的时候，就回溯返回，尝试别的路径。
百度解释：回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
二.基本思想
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。
若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
三.n皇后问题
////N皇后是典型DPS问题，这里是用递归实现的，要想输出必须要存储上级运算结果。 #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<string> #include<cctype> #include<cmath> #include<map> #include<set> #include<vector> #include<queue> #include<stack> #include<ctime> #include<algorithm> #include<climits> using namespace std; const int N=101; static int disp[16]; int C[N]; int tot; int n; void search(int cur) { if(cur==n){ for( int i = 0; i<n; i++ ) printf( "%d " , disp[i] ); printf("\n"); tot++; } else for(int i=0;i<n;i++) { int ok=1; C[cur]=i;//尝试把cur行的皇后放在第i列 for(int j=0;j<cur;j++)//检查是否和前面的皇后冲突 if(C[cur]==C[j]||cur-C[cur]==j-C[j]||cur+C[cur]==j+C[j]) { ok=0;break; } if(ok) { disp[cur]=i;//当前行的皇后在第几列 search(cur+1); } } } int main() { while(cin>>n) { tot=0; search(0); cout<<tot<<"种方法"<<endl; } return 0; }
#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> using namespace std; int c[150],vis[3][150],tot,n=8,sum_max; int mapn[9][9]; void search(int cur) { if(cur==n)//递归边界，只要走到了这里，所有皇后必然不冲突 { if(sum_max<tot) sum_max = tot; } else for(int i=0;i<n;i++) { if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+n])//利用二维数组直接判断 {//0为竖行，1为副对角线，2为主对角线 c[cur] = i;//保存下每行皇后的位置 tot += mapn[cur][i]; vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1; search(cur+1); vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0;//记得改回来 tot -= mapn[cur][i]; } } } int main() { int T; cin >> T; while(T--) { sum_max = 0,tot = 0; memset(vis,0,sizeof(vis)); for(int i=0;i<8;i++) for(int j=0;j<8;j++) { cin >> mapn[i][j]; } search(0); printf("%5d\n",sum_max); } return 0; }
算法入门经典7.4回溯法八皇后问题
7.4.1方法1.#include<stdio.h>#include<string.h>intans,n,map[20];voidsearch(intcur){inti,j,flag;if(cur==n+1)//递归边界ans++;else{for(i=1;i<=n;i++){map[cur]=i;//把第cur行的皇后放在第i列flag=1;for(j=1;j< 查看详情
算法入门经典-第七章例题7-1除法
除法输入正整数n，按从小到大的顺序输出所有形如abcde/fghij=n的表达式，其中a~j恰好为数字0~9的一个排列，2<=n<=79.样例输入：62样例输出：79546/01238=6294736/01528=62#include<stdio.h>#include<string.h>intmain(){intn;//x/y=nx用abcde表示... 查看详情
算法入门经典-第七章例题7-2-2可重集的排列
可重：如果问题变成输入数组p，并按字典序输出数组A个元素的所有全排列，则需要修改代码集的全排列//RujiaLiu#include<cstdio>#include<algorithm>usingnamespacestd;intP[100],A[100];//输出数组P中元素的全排列。数组P中可能有... 查看详情
有关int范围的例题（算法竞赛入门经典）
对于任意大于1的自然数n，若n为奇数，则将n变为3n＋1，否则变为n的一半。经过若干次这样的变换，一定会使n变为1。例如，3→10→5→16→8→4→2→1。输入n，输出变换的次数。n≤109。样例输入：3样例输出：71#include<iostream>2#... 查看详情
算法入门经典-第四章例题4-3救济金发放
救济金的问题抽象出来就是几个人围成一个圈坐，给每一个人编号，一个人从1开始，一个人从n开始，从一开始的点到k时，出列一人，n逆时针点人，点到m出列一人。如果我们出列用删除操作，则大大的降低了效率，我们将删除... 查看详情
《算法竞赛入门经典》例题5.4.1(代码片段)
题目：现代数学的著名证明之一是GeorgCantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：第一项是1/1，第二项是是1/2，第三项是2/1，第四项是3/1，第五项是2/2，……。输入n，... 查看详情
八皇后问题的两个高效的算法（回溯与递归）
...、同一斜线上的皇后都会自动攻击）。求解八皇后问题是算法中回溯法应用的一个经典案例 回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进... 查看详情
算法学习——dfs（暴力搜索）n皇后问题(代码片段)
...另一条路继续一条路走到黑。属于入门时非常常用的暴力算法，考察的知识点主要是对递归的掌握和理解。递归也是新生入门算法时必经的一道门槛，理解透彻递归，就能明白DFS。 #include<bits/stdc++.h>usingnamespacestd;cons... 查看详情
dfs与dp算法之关系与经典入门例题(代码片段)
...具体代码dp思路解题思路具体代码声明本文不介绍dfs、dp算法的基础思路，有想了解的可以自己找资源学习。本文适合于刚刚接触dfs和dp算法的人，发现两种算法间的内在联系。本人算法之路走之甚短，如果理解出现问题欢迎大家... 查看详情
算法入门经典第六章例题6-15给任务排序
假设有n个变量，还有m个二元组（u，v），分别表示变量u小于v。那么，所有变量从小到大排列起来应该是什么样子呢？例如，有4个变量a,b,c,d,若已知a<b,c<b,d<c,则这4个变量的排序可能是a<d<c<b。尽管还有其他可能... 查看详情
算法动态规划dp自学笔记入门：基本知识+经典例题(代码片段)
...述动态规划，是利用历史记录来避免重复计算的一种算法，是求解决策过程最优化的过程。一般用一维数组/二维数组来保存历史记录。一般动态规划有三个步骤：定义数组元素的含义，一般求什么就定义成什么找... 查看详情
算法入门经典第六章例题6-14abbott的复仇(abbott'srevenge)bfs算法实现
SampleInput31N33 11WLNR* 12WLFNRER* 13NLER* 21SLWRNF* 22SLWFELF* 23SFREL* 0SampleOutput(3,1)(2,1)(1,1)(1,2)(2,2)(2,3)(1,3)(1,2)(1,1)(2,1) (2,2)(1,2)(1,3)( 查看详情
算法入门经典第六章例题6-5移动盒子
例题6-5移动盒子（BoxesinaLine,UVa127675）问题给定一行盒子，从左到右编号依次为1，2，...，n.可以执行以下命令：1XY 把盒子X移动到Y的左边（如果已经在左边，忽略此命令）2XY 把盒子X移动到Y右边（如果X已经在Y的右边，忽... 查看详情
算法入门经典-第五章例题5-7丑数
#include<iostream>#include<vector>#include<queue>#include<set>usingnamespacestd;typedeflonglongll;constintcoeff={2,3,5};intmain(){//一些常见的优先队列，STL提供了更为简单的定义方法//对于任意丑数x则2x,3x,5x也 查看详情
第四：搜索算法应用-四皇后问题(代码片段)
四皇后问题在n行n列的国际象棋上摆放n个皇后，使其不能互相攻击（即任意两个皇后都不能处于同一行、同一列或同一斜线上）。请问有多少种摆法，以及如何摆放这些皇后。这就是经典的n皇后问题。如下图所示... 查看详情
n皇后问题（递归回溯）
...在同一行，同一列，同一斜线。因为这几天学习的是回溯算法，很简单的想到了回溯。这个问题也是经典的回溯算法习题之一。 下面来想一下问题所包含的条件，明显的条件就是棋盘 查看详情
n皇后！(代码片段)
提到回溯算法那肯定离不开n皇后这道算法题，它实在是太经典了。所谓n皇后问题，指的是如何将n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。皇后彼此不能相互攻击，也就是说：任何两个... 查看详情
算法竞赛入门经典例题3-4回文串
输入一个字符串。求出当中最长的回文子串。子串的含义是：在原串中连续出现的字符串片段。回文的含义是：正着看和倒着看同样。如abba和yyxyy。在推断时，应该忽略全部标点符号和空格。且忽略大写和小写。但输出应保持原... 查看详情