回溯法经典应用——N皇后&迷宫问题
回溯法
写在前面：国庆七天没有回家，自己在台里面自习，室友们明天结伴去武汉玩，他们强烈要求全寝4人出去玩一趟，一定让我去，被平时不怎么合群的我婉拒了，不过还好他们理解了我台里面的事情，其实本身来说没事务在身我也是不想参与这次出游。现在独自在六教七楼的电视台里面写学习以及写代码看电影，很是自在，不知道为什么，我似乎更能体会到一个人生活比群体活动拥有的乐趣。并不是自我安慰，事情的的确确是这样的，没什么聊以寂寞的因素在我身上，反之我总能找到好多好玩有趣的东西，所以——一个人的国庆真是太棒啦！ 2015.10.2
——正文——
- 回溯法介绍（图片来自：维基百科）
实际上回溯法有暴力破解的意思在里面，解决一个问题，一路走到底，路无法通，返回寻找另 一条路。
回溯法可以解决很多的问题，类似我今天两个例子：N皇后问题和迷宫问题。
一.概念
回溯算法实际类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现不满足条件的时候，就回溯返回，尝试别的路径。
百度解释：回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
二.基本思想
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。
若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
三.算法框架
1.问题框架
设问题的解释一个n维向量(a1,a2,…..,an),约束条件是ai(i=1,2,3…n)之间满足某种条件，记为f(ai).
2.非递归回溯框架
1: int a[n],i;
2: 初始化数组a[];
3: i = 1;
4: while (i>0(有路可走) and (未达到目标)) // 还未回溯到头
5: {
6: if(i > n) // 搜索到叶结点
7: {
8: 搜索到一个解，输出；
9: }
10: else // 处理第i个元素
11: {
12: a[i]第一个可能的值；
13: while(a[i]在不满足约束条件且在搜索空间内)
14: {
15: a[i]下一个可能的值；
16: }
17: if(a[i]在搜索空间内)
18: {
19: 标识占用的资源；
20: i = i+1; // 扩展下一个结点
21: }
22: else
23: {
24: 清理所占的状态空间； // 回溯
25: i = i –1;
26: }
27: }
另外还有个递归式的回溯算法框架，待会两个问题都解决后进行贴出，那个实际上是深度优先搜索的问题，之后我刷算法导论的书的时候博客的时候会进行详细的内容和代码示例。
- 回溯实例1——N皇后
国际象棋中的8皇后问题，就是要统计皇后不能再同行，同列，同斜线上的所有情况，著名数学家高斯认为有76种情况，而实际上是有92种情况的。
根据以上提到的算法框架 我们能写出如下代码：
代码步骤：
先规定，a[i] = j的数列中，下标i是行，数列所对应的值j是列。
int is_conflick(int *a,int n){
int flag = 0;
int i;
for(i = 0;i < n;i++){
if(a[i] == a[n] || a[i]-a[n] == n-i || a[n]-a[i] = n-i){ //如果等式成立 则说明有冲突
flag =1;
break;
}
}
return flag;
}
因为是每一行来循环搜索的 所以只需要判断在同一列 a[i] == a[n] 还有斜线 斜线类似于y = x与 y = -x的关系 另 n-i = y a[i] - a[n] = x则有以上的等式。若成立，则说明有冲突 ，返回1，表明的确矛盾
而后是进入查找函数
int queen(int n){
int count = 0;
int a[MaxSize];
InitQ(a,n);
int i = 0; //从第一行开始
while(1){
if(a[i] < n){
if(is_conflict(a,i)){
a[i]++;
continue;
}
if(i >= n-1){
count++;
Print_Queen(a,n);//输出可行的棋盘
a[n-1]++;//并且考虑此行的下一列是否可以
continue;
}//以上部分会测试完每一行
i++;//没有冲突 尝试下一行
continue;
}
else{//如果i一直加 则最后
a[i] = 0;//将列复原
i--;//行返回
if(i<0){
return count;//如果不能再回退了说明全部情况都已经考虑完了
}
a[i]++;
continue;
}
}
}
代码分析：
1.进入while（1）这里仅仅只需要循环的循环体就可以了，所以不需要附带条件
2.若未达到目标 即a[i] < n，则先判断是否冲突is_conflict()，若冲突，则换至下一列，a[i]++;若冲突，终止本次循环，用continue，下一次循环继续判断。其实也和算法框架一致，当行达到最大的时候 i>=n-1,说明查找到了，就输出。 3.若改行的列到最后，则归零，回溯，从上一行的第一列重新开始找。如果一直回溯到第一行的时候，则说明已经全部找完，此时结束循环，直接返回count。不然的话就仍然一列一列找。
以上就是八皇后的具体流程，剩下的两个就是初始化棋盘和输出棋盘，主函数的内容就是调用测试N皇后的函数，然后输出返回count的次数就可以了。
完整代码如下：
#include <iostream>
using namespace std;
#define MaxSize 1024
//判断是否矛盾
int is_conflict(int *a,int n){
int flag = 0;
int i;
for(i=0;i<n;++i){
if(a[i] == a[n] || a[i] - a[n] == n-i || a[n] - a[i] == n-i){//如果等式成立 则说明有冲突
flag = 1;
break;
}
}
return flag;
}
//初始化棋盘
void InitQ(int *a,int n){
int i;
for(i=0;i<n;++i){
a[i] = 0;
}
}
//打印出八皇后
void Print_Queen(int *a,int n){
int j,i;
for(i = 0;i<n;i++){
for(j = 0;j < a[i];j++){cout<<"_";}
cout<<"Q";
for(j=a[i]+1;j<n;j++){cout<<"_";}
cout<<endl;
}
cout<<"--------------"<<endl;
}
//主要测试摆放部分 more importantly!
int queen(int n){
int count = 0;
int a[MaxSize];
InitQ(a,n);
int i = 0; //从第一行开始
while(1){
if(a[i] < n){
if(is_conflict(a,i)){
a[i]++;
continue;
}
if(i >= n-1){
count++;
Print_Queen(a,n);//输出可行的棋盘
a[n-1]++;//并且考虑此行的下一列是否可以
continue;
}//以上部分会测试完每一行
i++;//没有冲突 尝试下一行
continue;
}
else{//若不满足 a[i] < n 则表明已经到最后一列了 则归零
a[i] = 0;//将列复原
i--;//行返回
if(i<0){
return count;//如果不能再回退了说明全部情况都已经考虑完了
}
a[i]++;
continue;
}
}
}
int main(void) {
int n = 8;
int count = queen(n);
printf("%d solutions in %d queens problem/n", count, n);
return 0;
}
运行结果：
- 回溯实例2——迷宫问题
同样 我们可以用回溯法来实现找迷宫出路
如图迷宫：
图中很明确表明，一个二维数组，第一个元素表示行，第二个元素表示列，在查找的过程中，进行上下左右的适应。入口时（1，1） 出口是 （8，8）
具体代码实现步骤以及详细说明：
1.需要一个栈来存放走过的路程，定义一个结构体，拥有3个元素，i表示行，j表示列，di表示下一步可执行的方向，为0 1 2 3 来判断，然后栈顶元素为top。
struct{
int i;//行
int j;//列
int di;//下一步可走的方向
}Stack[MaxSize];
int top = -1;//顶端元素的初始化
然后给出迷宫的样式，1代表墙壁，0代表通路
int mg[M+1][N+1]={ /*M=10,N=10*/
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}};
此二维元素的排列与迷宫第一张图的结构一致。
然后是查找环节
具体代码：
void mgpath(){
int i,j,find,k,di;mg[1][1]=-1;//将数据都初始化 (1.1)是入口
top++;//top先入栈
Stack[top].i=1;Stack[top].j=1;Stack[top].di=-1;mg[1][1]=-1;
while(top > -1){
i = Stack[top].i ; j = Stack[top].j;di = Stack[top].di;
if(i == M-2 && j == N-2){
//找到
cout<<"可行的路径是:"<<endl;
for(k=0;k<=top;k++){
cout<<"("<<Stack[k].i<<","<<Stack[k].j<<")";
if((k+1)%5 == 0) cout<<endl;
}
cout<<endl;
return;
}
//找的过程
find = 0;
while(di < 4 && find == 0 ){
di++;
switch(di){
case 0:i = Stack[top].i-1;j = Stack[top].j;break;
case 1:i = Stack[top].i+1;j = Stack[top].j;break;
case 2:i = Stack[top].i;j = Stack[top].j-1;break;
case 3:i = Stack[top].i;j = Stack[top].j+1;break;
}
if(mg[i][j] == 0) find = 1;//如果以上4种情况找到的是通路 则find=1
}
if(find == 1){//显示如果是找到的情况
Stack[top].di = di;//记录当前的位置（有点疑问）
top++;//下一个可走的方框进栈
Stack[top].i = i; Stack[top].j = j;Stack[top].di=-1;mg[i][j] = -1;//将刚刚的位置放进新的栈顶 走过的位置赋为-1 防止再次进入
}
else{ //没有找到di可以让find == 1 回溯
mg[Stack[top].i][Stack[top].j] = 0;//这一步有疑问
top--;//让刚刚的再回去 重新考虑
}
}
cout<<"没有可行路径";
}
1.将数据一个一个初始化，注意在一下所有的i和Stack[top].i要区分开来，前者是入栈的部分，就是可用的路径，后者是尝试的路径，在后面的赋值过程不要搞混淆了。
2.初始mg[1][1]=-1.入口时(1,1) 。然后top++代表top入栈，在没有引入类的定义下来解题其实还是有点麻烦的昂….
3.与框架一致，当栈非空的时候循环，与八皇后中的while（1）一致，只要提供一个一直可以循环的循环体，内部查找完毕之后自行退出循环。
4.如框架一样噢，当找到的时候输出，找到的时候输出，找到的依据是到达出口（8，8），即(i== M-2 && j==N-2)两个要同时满足，然后输出
5.框架第三步，如果没有找寻到就进入找的过程，先find = 0,找到后才变成find = 1;
找四个方向（当没找到且di还是<4时候） di 来解决 switch来构造4种情况。若找到，找到的依据是遇到mg[i][j] == 0;则把find = 1;
6.如果找到之后，di的位置入栈，top++，然后根据位置将i 和 j赋予给当前的坐标.还有一个步骤，把走过的那一个坐标变成-1，以防回溯的时候又走进来。
7.还有 走过的路都被赋予了-1，当回溯的时候，把原来的道路归零，top–出栈重新找。
以上就是详解，在详解的注释里面我标注了两个疑问，之后会去请教一下老师，然后回来修改。
完整代码：
#include <iostream>
using namespace std;
#define MaxSize 2014
#define M 10
#define N 10
struct{
int i;//代表行
int j;//代表列
int di;//代表下一个方位的位置
}Stack[MaxSize];
int top = -1;//定义指针栈
//迷宫
int mg[M+1][N+1]={ /*M=10,N=10*/
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}};
//求解过程
void mgpath(){
int i,j,find,k,di;mg[1][1]=-1;//将数据都初始化 (1.1)是入口
top++;//top先入栈
Stack[top].i=1;Stack[top].j=1;Stack[top].di=-1;mg[1][1]=-1;
while(top > -1){
i = Stack[top].i ; j = Stack[top].j;di = Stack[top].di;
if(i == M-2 && j == N-2){
//找到
cout<<"the path is:"<<endl;
for(k=0;k<=top;k++){
cout<<"("<<Stack[k].i<<","<<Stack[k].j<<")";
if((k+1)%5 == 0) cout<<endl;
}
cout<<endl;
return;
}
//找的过程
find = 0;
while(di < 4 && find == 0 ){
di++;
switch(di){
case 0:i = Stack[top].i-1;j = Stack[top].j;break;
case 1:i = Stack[top].i+1;j = Stack[top].j;break;
case 2:i = Stack[top].i;j = Stack[top].j-1;break;
case 3:i = Stack[top].i;j = Stack[top].j+1;break;
}
if(mg[i][j] == 0) find = 1;//如果以上4种情况找到的是通路 则find=1
}
if(find == 1){//显示如果是找到的情况
Stack[top].di = di;//记录当前的位置（有点疑问）
top++;//下一个可走的方框进栈
Stack[top].i = i; Stack[top].j = j;Stack[top].di=-1;mg[i][j] = -1;//将刚刚的位置放进新的栈顶 走过的位置赋为-1 防止再次进入
}
else{ //没有找到di可以让find == 1 回溯
mg[Stack[top].i][Stack[top].j] = 0;//让
top--;//让刚刚的再回去 重新考虑
}
}
cout<<"没有可行路径";
}
//主函数
int main(){
mgpath();
return 0;
}
——
啊哈哈，写完啦，上火了但好想吃辣条咧！ 好想贴个图来这，今早上在学习马哥linux的文档上看到的，马哥的视频教学真的是很励志很良心的，虽然我总是看着看着睡着，不过内容的确很丰富很技术派。
他教学文档上13年3月7号打了句这段话：
昨晚看MIT的算法导论视频时候，那个教授说了句这段话，也挺好的：
If you want to be a excellent programmer,you have to pragram everyday for 2 years,and if you want to be world class programmer,then you should pragram everyday for 10 years,or program 2 years and take Algorithm lesson.
如果你想成为一名优秀的程序员，那你需要持续2年每天编程，如果你想成为世界级的程序员，那你就要么码10年，要么码2年程序，并且攻读算法学。
算法很重要，我更新完数据结构系列内容之后就开始刷算法导论喽！好了，累屎个亲娘了，休息去~ 欢迎理智地和技术帝指正~
Enjoy Reading This Article?
Here are some more articles you might like to read next: