C++ 基础算法 - 搜索与回溯算法

今天，我们将要学习第五个算法 - 搜索与回溯算法。

搜索

搜索，是有目的地进行穷举一个问题结果的范围，直至找出正确答案为止 ( 说白了就是穷举，但不意味着完全相同 )

搜索算法有很多种，比如深度优先搜索 ( DFS )，广度优先搜索 ( BFS )，A* 等

下面以一张迷宫图来看看搜索的过程 ( 这里利用 DFS 进行搜索 )

红色代表起点，白色代表空气，黑色代表墙，绿色代表终点

太过于简单的迷宫

相信所有人都能够很快地解出来吧?

还是非常简单的...我只试了亿次就过了

如果我们要让计算机来走迷宫要怎么办呢

因为输入地图比较麻烦，可以把地图变成这个样子

int Map[10][10]=

{
 {1,1,1,1,1,1,1,1,1,1},
 {1,2,1,0,1,0,1,0,0,1},
 {1,0,1,0,0,0,1,0,1,1},
 {1,0,1,0,1,0,1,0,0,1},
 {1,0,1,0,1,0,1,1,0,1},
 {1,0,1,0,1,0,0,0,0,1},
 {1,0,0,0,1,0,1,1,0,1},
 {1,1,1,1,1,0,1,0,0,1},
 {1,0,0,0,0,0,1,3,0,1},
 {1,1,1,1,1,1,1,1,1,1},
};//直接赋初始值

非常的直观，1 是墙，0 是空气，2 是起点，3 是终点

这里先展示出代码，代码的结果就是迷宫是否有解 ( YES 代表有解，NO 代表无解 )，接下来就以这个代码来进行讲解

#include<iostream>

#include<cstdio>
using namespace std;
bool data[10][10],win(false);
int Map[10][10]=
{
 {1,1,1,1,1,1,1,1,1,1},
 {1,2,1,0,1,0,1,0,0,1},
 {1,0,1,0,0,0,1,0,1,1},
 {1,0,1,0,1,0,1,0,0,1},
 {1,0,1,0,1,0,1,1,0,1},
 {1,0,1,0,1,0,0,0,0,1},
 {1,0,0,0,1,0,1,1,0,1},
 {1,1,1,1,1,0,1,0,0,1},
 {1,0,0,0,0,0,1,3,0,1},
 {1,1,1,1,1,1,1,1,1,1},
};
void search(int x,int y)
{
 if(data[x][y]) return;
 if(Map[x][y]==3)
 {
win=true;
return;
 }
 data[x][y]=true;
 if(Map[x+1][y]!=1&&!win) search(x+1,y);
 if(Map[x-1][y]!=1&&!win) search(x-1,y);
 if(Map[x][y+1]!=1&&!win) search(x,y+1);
 if(Map[x][y-1]!=1&&!win) search(x,y-1);
}
int **in()
{
 search(1,1);
 if(win) printf("YES\n");
 else printf("NO\n");
 return 0;
}

不要看有整整 38 行代码，以后还有更长的，这里的赋值就占了一大半，所以也不是很长了

那么，要让机器去走迷宫，就要有一个出发点，一个目标，以及过程

目标也很明确，就是 3 的地方，搜索到它的地方后就表示成功了，即在递归中的返回操作

if(Map[x][y]==3)

{
 win=true;
 return;
}

过程也很简单，就是通过计算机进行上下左右的查找，能走则走，直至找到答案，就是向上下左右寻找可以走的点即可

if(Map[x+1][y]!=1) search(x+1,y);

if(Map[x-1][y]!=1) search(x-1,y);
if(Map[x][y+1]!=1) search(x,y+1);
if(Map[x][y-1]!=1) search(x,y-1);

例如，从起点出发，一直走到第一个路口前都没有其它的路 ( 除了来时的路，所以如果让程序能够让 4 个方向走时一定要规定不要往回走，否则就会卡死 )，到了第一个路口，先让程序像上走，发现除了来时的路，已经没有任何路了，所以程序都会回溯 ( 先不管怎么做到的，先知道这个概念 ) 回溯到上一个选择处，继续选择下一个路口走

如果按照这样的方法走，找到了目标就标记成功并退出即可，但是如果没有可行的路线，程序会怎么样呢

程序在没有选择时会进行回溯，退回到上一个选择并重新选择，但是，程序如果退回到了最开始的地方也没有路可走，就会直接退出

回溯

搜索有了基本的概念，接下来看看回溯是怎么做到的，我们知道，搜索没了选择就会回溯，目的是重新选择其它的路，产生新的不同的结果

可回溯的搜索中是利用递归实现的，所以回溯就是利用递归的性质回退到上一个能选择的路口中，但是这里的回溯不是很明显，因为这里只要返回并寻找新的路径即可，所以唯一可以讲的就是选择新路径，每一个不同的路口就是一个 if 语句，当一个路径口退出了，就会继续判断下一个路径是否可行，这样就无形之中做到了回溯这一点

其它

如何做到在遇到已经走过的路后不再继续走 ? 可以用一个数组来表示哪里已经走过，这样就可以少走弯路，加快速度 ( 其实这是必须的，要不然根本停不下来... )，还有在成功到达终点后不能直接返回，否则程序就会以为是回溯，要重新进行递归查找，虽然这样也能成功，但是会消耗不比消耗的时间，所以可以设置一个变量，记录是否成功查找到了，如果查找到了就不必继续搜索了，加速退出，当然这是视情况而定的，就比如有些是必须要搜索到底的

一本通平台讲解

1317 - 1318，1212 - 1222

1317：【例5.2】组合的输出

这道题和 1199：全排列 类似，只不过是将字母换成了数字

代码如下

#include<iostream>

#include<io**nip>//setw()函数所需的头文件
#include<cstdio>
using namespace std;
int n,r,a[30];
bool used[30];
void print()
{
 int i;
 for(i=1;i<=r;i++) cout<<setw(3)<<a;

 //设置长宽还可以直接用printf更加简单
 //可以将cout<<setw(3)<<a;

 //替换成printf("%3d",a);

 //两者都是具有同样效果的
 printf("\n");
}
void search(int x)
{
 int i;
 for(i=a[x-1];i<=n;i++)//从上一次选取的值开始枚举
 {
if(!used)//是否使用过

{
 used=true;

 a[x]=i;
 if(x==r) print();//输出
 else search(x+1);//继续查找
 used=false;

}
 }
}
int **in()
{
 scanf("%d%d",&n,&r);
 a[0]=1;
 search(1);
 return 0;
}

#include<iostream>

#include<cstdio>
using namespace std;
int n,a[10001],sum=0;
void print(int m)
{
 int i;
 sum++;
 printf("%d=",n);
 for(i=1;i<m;i++) printf("%d+",a);

 printf("%d\n",a[m]);
}
void search(int x,int m)
{
 int i;
 for(i=a[m-1];i<=x;i++)//枚举可行的数
 {
if(i<n)
{
 a[m]=i;
 x-=i;
 if(x==0) print(m);//分解成功就输出
 else search(x,m+1);//继续分解
 x+=i;
}
 }
}
int **in()
{
 int i;
 for(i=0;i<=10000;++i) a=1;

 scanf("%d",&n);
 search(n,1);
 return 0;
}

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,**xn=0,mov[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//移动数组,用于一个点的延伸
bool num[26];//标记某个字母是否走过
char Map[30][30];
void search(int x,int y,int step)
{
 int i,nx,ny;//NewX,NewY,用于确定新延伸的点
 **xn=**x(step,**xn);
 for(i=0;i<4;i++)
 {
nx=x+mov[0];//找到新的点

ny=y+mov[1];

if(nx>=0&&nx<n&&ny>=0&&ny<m&&!num[Map[nx][ny]-'A'])
//判断是否出界或是否走过这个字母
{
 num[Map[nx][ny]-'A']=true;//标记字母为走过
 search(nx,ny,step+1);//继续寻找
 num[Map[nx][ny]-'A']=false;//标记字母未走过
}
 }
}
int **in()
{
 int i,j;
 scanf("%d%d",&n,&m);
 for(i=0;i<n;i++) for(j=0;j<m;j++) cin>>Map[j];

 num[Map[0][0]-'A']=true;//标记走过
 search(0,0,1);//搜索
 printf("%d\n",**xn);//输出
 return 0;
}

#include<iostream>

#include<cstdio>
using namespace std;
int a[9][9],b[9];
bool Map[20][3];
int sum;
void search(int num)
{
 int i;
 if(num==9)
 {
sum++;
for(i=1;i<=8;i++) a[sum]=b;//标记

return;
 }
 for(i=1;i<=8;i++)
 {
if(!Map[0]&&!Map[num+i][1]&&!Map[num-i+8][2])

{
 Map[0]=true;

 Map[i+num][1]=true;
 Map[num-i+8][2]=true;//分别标记上下左右和斜边不能够放置了
 b[num]=i;//记录第num个皇后放在哪里
 search(num+1);//枚举下一个皇后的位置
 Map[0]=false;

 Map[i+num][1]=false;
 Map[num-i+8][2]=false;//标记上下左右斜边可以放置了
}
 }
}
int **in()
{
 int k,i,j;
 search(1);
 for(k=1;k<=sum;k++)
 {
printf("No. %d\n",k);//输出
for(i=1;i<=8;i++)
{
 for(j=1;j<=8;j++)
 {
if(a[k][j]==i) printf("1 ");
else printf("0 ");
 }
 printf("\n");
}
 }
 return 0;
}

#include<iostream>

#include<cstdio>
using namespace std;
bool path[10][10];
int num=0;
bool check(int x,int y)//判断函数,用于判断点(x,y)处能否放置皇后
{
 int i,j;
 for(i=0;i<8;++i) if(path[x]) return false;

 for(i=0;i<8;++i) if(path[y]) return false;

 for(i=0;i<8;++i) for(j=0;j<8;++j) if(i-j==x-y&&path[j]) return false;

 for(i=0;i<8;++i) for(j=0;j<8;++j) if(i+j==x+y&&path[j]) return false;

 return true;
}
void dfs(int s,int test)
{
 int i,j;
 if(s==8)//放满了就输出
 {
num++;
if(test==num) for(i=0;i<8;++i) for(j=0;j<8;++j) if(path[j]) printf("%d",j+1);

return;
 }
 for(i=0;i<8;++i)
 {
if(check(s,i))
{
 path[s]=true;//标记放了皇后

 dfs(s+1,test);
 path[s]=false;

}
 }
}
int **in()
{
 int n,x;
 scanf("%d",&n);
 while(n--)
 {
scanf("%d",&x);
dfs(0,x);
num=0;
printf("\n");
}
return 0;
}

#include<iostream>
#include<cstring>//memset函数所需的头文件
#include<cstdio>
using namespace std;
int mov[4][2]={{0,1},{1,0},{0,-1},{-1,0}},sx,sy,ex,ey,n;
char **p[101][101];
bool **p1[101][101],f;
void search(int x,int y)
{
 int i,nx,ny;
 if(x==ex&&y==ey)
 {
f=true;//找到了目标
return;//返回
 }
 for(i=0;i<4;i++)
 {
nx=x+mov[0];

ny=y+mov[1];

if(**p[nx][ny]=='.'&&**p1[nx][ny]==0&&nx>=0&&nx<n&&ny>=0&&ny<n)//符合
{
 **p1[nx][ny]=1;
 search(nx,ny);//继续寻找
}
 }
}
int **in()
{
 int i,j,k;
 scanf("%d",&k);
 while(k--)
 {
memset(**p,0,sizeof(**p));//初始化函数
memset(**p1,0,sizeof(**p1));
scanf("%d",&n);
for(i=0;i<n;i++) for(j=0;j<n;j++) cin>>**p[j];

scanf("%d%d%d%d",&sx,&sy,&ex,&ey);//输入
f=false;
if(**p[sx][sy]=='#'||**p[ex][ey]=='#')//先行判断
{
 printf("NO\n");
 continue;
}
search(sx,sy);//搜索
if(f) printf("YES\n");
else printf("NO\n");
 }
 return 0;
}

#include<iostream>

#include<cstring>
#include<cstdio>
using namespace std;
char t;
int m,n,**p[1001][1001],mov[4][2]={{0,1},{0,-1},{1,0},{-1,0}},sum;
bool visited[1001][1001];
void search(int x,int y)//搜索
{
 int i,nx,ny;
 for(i=0;i<4;i++)
 {
nx=x+mov[0];

ny=y+mov[1];

if(!visited[nx][ny]&&**p[nx][ny]==1&&nx>0&&nx<=n&&ny>0&&ny<=m)
{
 visited[nx][ny]=true;
 sum++;
 search(nx,ny);
}
 }
}
int **in()
{
 int i,j,x,y;
 while(true)
 {
scanf("%d%d",&m,&n);
if(m==0&&n==0) break;
sum=1;
memset(visited,false,sizeof(visited));//初始化很重要
memset(**p,0,sizeof(**p));
for(i=1;i<=n;i++)
{
 for(j=1;j<=m;j++)
 {
cin>>t;
switch(t)
{
 case '@':x=i;y=j;**p[j]=1;break;

 case '.':**p[j]=1;break;

 case '#':**p[j]=0;break;

}
 }
}
visited[x][y]=true;//标记走过的点
search(x,y);
printf("%d\n",sum);
 }
 return 0;
}

#include<iostream>

#include<cstring>
#include<cstdio>
using namespace std;
int n,k,Map[20][20],cnt;
bool visited[20],flag;
char c;
void search(int x,int y)
{
 int i,j;
 if(y==k) cnt++;//达到数量就增加方案数
 else
 {
for(i=x;i<n;i++)
{
 for(j=0;j<n;j++)
 {
if(Map[j]&&!visited[j])

{
 visited[j]=true;
 search(i+1,y+1);//能放则放
 visited[j]=false;
}
 }
}
 }
}
int **in()
{
 int i,j;
 while(true)
 {
scanf("%d%d",&n,&k);
if(n==-1&&k==-1) break;
memset(Map,0,sizeof(Map));
memset(visited,false,sizeof(visited));//初始化
cnt=0;
for(i=0;i<n;i++)
{
 for(j=0;j<n;j++)
 {
cin>>c;
if(c=='#') Map[j]=1;

else Map[j]=0;

 }
}
search(0,0);//搜索
printf("%d\n",cnt);
 }
 return 0;
}

#include<iostream>

#include<cstdio>
using namespace std;
int **in()
{
 int n,m;
 while(true)
 {
scanf("%d%d",&n,&m);
if(n==0&&m==0) break;//遇到0退出
if(n<m) swap(n,m);//保证n>m
if(n/m>=2)//如果n/m取整的值≥2先手必赢
{
 printf("win\n");
 continue;
}
int i=1,x;
while(n/m==1)//否则模拟两人的过程
{
 x=n;
 n=m;
 m=x%n;
 i++;
}
if(i%2==1) printf("win\n");
else printf("lose\n");
 }
 return 0;
}

#include<iostream>

#include<cstring>
#include<cstdio>
using namespace std;
int n,m,x,y,ans=0,mov[8][2]={{-2,1},{-2,-1},{-1,2},{-1,-2},{2,1},{2,-1},{1,2},{1,-2}};
bool **p[21][21];//这里的mov是马的移动数组
int search(int x,int y,int sum)
{
 if(sum==n*m)//满足条件
 {
ans++;
return 0;
 }
 int i,nx,ny;
 for(i=0;i<8;i++)
 {
nx=x+mov[1];

ny=y+mov[0];

if(**p[nx][ny]==0&&nx>=0&&nx<n&&ny>=0&&ny<m)
{
 **p[nx][ny]=true;
 search(nx,ny,sum+1);//寻找
 **p[nx][ny]=false;
}
 }
}
int **in()
{
 int i,n;
 scanf("%d",&n);
 for(i=1;i<=n;i++)
 {
scanf("%d%d%d%d",&n,&m,&x,&y);
ans=0;
memset(**p,false,sizeof(**p));
**p[x][y]=true;
search(x,y,1);
printf("%d\n",ans);
 }
 return 0;
}

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
string str[101],s;
int r[101],n,**xn;
bool check(string x,string y,int k)//检查是否能够拼接
{
 int i,l=x.size();
 for(i=0;i<k;i++) if(x[l-k+i]!=y) return false;

 return true;
}
void splicing(string &x,string y,int k)
//拼接函数,其中的&先不用管,只用知道用了它就可以直接更改到x本身而不是在函数中的x的值即可
{
 int i,l=y.length();
 for(i=k;i<l;i++) x+=y;

}
void search(string s)
{
 int i,j,l=s.size();
 **xn=**x(**xn,l);//取较大值
 for(i=1;i<=n;i++)
 {
if(r>=2) continue;

for(j=1;j<=str.size();j++)

{
 if(check(s,str,j))//查看是否能够拼接

 {
string t=s;
splicing(t,str,j);//拼接

if(t==s) continue;
r++;

search(t);//继续搜索
r--;

 }
}
 }
}
int **in()
{
 int i;
 scanf("%d",&n);
 for(i=1;i<=n;i++) cin>>str;

 cin>>s;//输入
 search(s);//搜索
 printf("%d\n",**xn);
 return 0;
}

#include<iostream>

#include<cstring>
#include<cstdio>
using namespace std;
int a[10100],sum[10100],n;
bool check(int x)//检测这些数字是否互质
{
 int i;
 for(i=2;i<x;i++)
 {
if(x%i==0)
{
 if(sum) return false;

 else sum++;

}
 }
 return true;
}
void search(int k,int x)//搜索
{
 int i;
 for(i=k;i<n;i++)
 {
if(check(a))

{
 a=-1;

 k++;
 search(k,a[k]);
}
 }
 return;
}
int **in()
{
 int i,ans=0;
 scanf("%d",&n);
 for(i=0;i<n;i++) scanf("%d",&a);

 for(i=0;i<n;i++)
 {
if(a!=-1)

{
 ans++;
 memset(sum,0,sizeof(sum));//初始化很重要
 search(i,a);//搜索

}
 }
 printf("%d\n",ans);
 return 0;
}

#include<iostream>

#include<cstdio>
using namespace std;
int search(int x,int y)//搜索
{
 if(x==0||y==1) return 1;
 if(x<y) return search(x,x);
 return search(x,y-1)+search(x-y,y);
}
int **in()
{
 int t,n,k;
 scanf("%d",&t);
 while(t--)
 {
scanf("%d%d",&n,&k);
printf("%d\n",search(n,k));
 }
 return 0;
}