本文同步发布于:学习笔记:快速精通基本搜索
在我写这个学习笔记的时候,我默认读者已经熟练掌握 C++ 的基础操作,知道基础的递归,有普及的思维能力,一定程度上能阅读他人代码并且有初中的数学理解能力。
从算法思想的角度来说,递归就是把大问题分成一个个子问题进行解决,而子问题和母问题具有相似性,所有可以通过递归调用自己进行解决。他与动态规划的区别在于——这些子问题具有可加性,也就是说,他们共同组成了整体的解。这样听来,递归似乎和分治算法很相似。
「例题」P1706 全排列问题:给定一个 $n$,输出 $1,2,3,\cdots n$ 的全排列。
我们考虑递归求解,每次循环从 $1\sim n$ 选数,选好了一个就填充下一个格子,然后把这个数拿出来,换一个数填。这样的思路让我们能够不重复不遗漏的遍历所有的情况。这里给出参考代码:
#include<bits/stdc++.h>
using namespace std;
int n,vis[100],ans[100];
void print(){
//输出已经选择好的排列
for(int i=1;i<=n;i++)
printf("%5d",ans[i]);
puts("");
}void search(int k){
//搜索到了第 k 格
if(k==n){//满了,输出
print();
return;
}for(int i=1;i<=n;i++){//循环作选择
if(!vis[i]){//如果没用过
vis[i]=1;ans[k+1]=i;//用它
search(k+1);//填充下一个格子
vis[i]=0;//把他拿出来,换一个填
}
}
}int main(){
cin>>n;
search(0);//从 0 开始搜索
return 0;
}
递归搜索所有的可能情况是暴力的基础形式,而这种形式的大多数情况,是 DFS 深度优先搜索。
康托展开 一种特殊的哈希函数。
比如我们要判断 $2143$ 是 $\{1,2,3,4\}$ 中第几大的排列,我们可以考虑以下排列的和:
那么这样一个过程怎么归纳成公式呢?我们把他们加起来,答案是 $7$,也就是在这个排列之前有 $7$ 个排列,也就是说这是排名为 $8$ 的全排列,那么我们把巨大的一个范围的全排列映射到了一个小范围,就可以用传统 $vis$ 数组解决了。
我们把一个集合产生的全排列按字典序排序,则第 $X$ 个排列的计算公式如下:
$$X=a_n(n-1)!+a_{n-1}(n-2)!+\cdots+a_i(i-1)!+\cdots a_2\times 1!+a_1\times 0!$$
$$X=\sum\limits_{i=1}^{n}a_i(i-1)!$$
当然也有逆康托展开,给定集合和排名,算出对应的排列,方法类似。
DFS (Depth First Search),常常用于遍历树或图,而往往也可以代指利用递归来实现暴力枚举。图论意义上的 DFS 基本思想是「一条路走到底」,并且在走的过程中将走过的结点做好标记,确保每个点仅访问一次,并且在「走不通」时可以返回,继续尝试下一条路径。
广义上,使用递归调用自身实现的、每个状态仅访问一次的遍历,就可以成为深度优先搜索。在递归遍历一个问题所有的可能解(此时的复杂度往往是指数级别的)、搜索所有满足题意情况时,DFS 的复杂度较高,而对于遍历一个给定的图,他的复杂度并不会难以想象(除非在遍历的过程中有特定的任务,必须多次访问同一节点,譬如最短路)。
特别地,对于一个图的深度优先遍历步骤如下:
这样一个实现简单,思路清晰的步骤使得 DFS 被广泛地使用,尽管时间复杂度较高(当遍历某些问题解答树时),但是可以「有序且完整」地遍历所有可能的情况,不容易出错。
「例题」:P1596 [USACO10OCT]Lake Counting S
题目大意:存在一个地图,由
W
和.
组成,求由W
组成的连通块数量,一个方块和周围八个方块均连通。
此题是经典的搜索应用,由于数据范围极小,我们可以考虑一个一个格子 DFS,然后对于查出来的连通块去重,再计算总量……这样看来,似乎代码实现很麻烦,并且还是慢了点。
所以一个不错的想法诞生了:染色。
这一题当中,染色的核心思想就是将走过的格子进行一种标记,这种标记使得我们后面不会再遍历同样的一个连通块,既可以省去去重计数的过程,连 $vis$ 数组都省了。具体的办法就是在走到一个格子之后,就把他染成正常地面的颜色(更改为 .
字符)。
这样,我们的搜索就只做了染色这一件事,但是依然能完成任务,下面给出带注释的参考代码:
#include<bits/stdc++.h>
using namespace std;
//用方向数组决定往哪一个方向走
const int dx[]={1, 1, 1, 0, 0,-1,-1,-1};
const int dy[]={1, 0,-1, 1,-1,-1, 1, 0};
char a[105][105];
int ans,n,m;
//check 函数:判断某个地点是否可以走
bool check(int x,int y){
return (x>=0&&y>=0&&x<=n&&y<m&&a[x][y]=='W');
}void dfs(int x,int y){
//染色:把走过的地方渲染成和普通地面一样
a[x][y]='.';
for(int i=0;i<8;i++){
int xx=x+dx[i],yy=y+dy[i];
//确定方向后判断能不能走
if(check(xx,yy))dfs(xx,yy);//递归调用搜索
}return;//不返回在一些题目可能会出事
}int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
scanf("%s",a[i]);//避免换行问题,整行读入
for(int i=0;i<=n;i++){
for(int j=0;j<m;j++){
if(a[i][j]=='W'){
//是一个之前没有走过的水潭,进行染色
dfs(i,j);
ans++;//可以走的地方多了一处
}
}
}printf("%d",ans);
return 0;
}
DFS 不仅能搜索一个图,还能搜索一些状态,譬如「是否选择」,这道题就是一个典型应用。对于「是否选择」形成的结果树进行深度优先遍历,找到所有的结果。对于每一个可能的结果(指数级数量的结果)进行判断。这里给出参考代码:
#include<bits/stdc++.h>
using namespace std;
int a[20],n,k;//依照题目所设
bool isp(int x){//是否是素数
if(x<=1)return 0;
if(x==2)return 1;
for(int i=2;i*i<=x;i++){
if(x%i==0)return 0;
}return 1;
}int f(int cho,int sum,int st,int ed){
//cho剩余的 k,sum累加和,st和ed为选取范围
//递归生成组合,循环累计
if(!cho)return isp(sum);
int s=0;
for(int i=st;i<=ed;i++){
s+=f(cho-1,sum+a[i],i+1,ed);
}return s;
}int main(){
cin>>n>>k;//输入
for(int i=1;i<=n;i++)cin>>a[i];
cout<<f(k,0,1,n);//调用
}
广度优先搜索,是一种效率上不错,程序也容易理解的算法。
假设现在我们在某一个状态(可能是某个格子,某个结点,某个情况),而接下来我们要搜索与之相关的所有情况,如何保证搜索顺序?这需要用到队列(queue,FIFO 先进先出表),将所有需要搜索的状态压进队列中。这样,我们只要一个 while
循环就可以按顺序遍历所有的情况了。
实现上,给出 C++ 风格的伪代码:
void BFS(){
定义队列 q;
while(队不空){
取出队头状态 x;
q 队头出队;
处理 x;
for(...){
将 x 的相关状态入队;
}
}
}
「例题」:P1443 马的遍历
题目大意:有一个 $n\times m$ 的棋盘 $(1<n,m\le 400)$,在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步?
我们发现数据范围大,如果用 DFS 可能会重复搜索到同一个方块很多遍(第一次到达的可能不是最优解),而且也不是很容易确定什么时候应该回溯,怎么办呢?
这种题目是 BFS 的典型应用,因为按照顺序向外广度遍历,第一次遇到格子就是最优的解(想一想,为什么),所以我们可以很方便地从起始点开始向外进行 BFS——你可以看做一个从起始节点向外扩散的过程,比如一滴墨水滴在清水中,向外进行流动(从二维的视角看,第一次扩散到的时候走的就是最近的路)。
每次入队的时候(而不是走到的时候)把入队的格子需要走的步数标记为“当前步数” $+1$,具体的实现参考代码:
#include<bits/stdc++.h>
using namespace std;
//方向数组
const int dx[]={2,-2, 2,-2,-1, 1,-1, 1};
const int dy[]={1, 1,-1,-1, 2, 2,-2,-2};
int n,m,x,y,mp[405][405];
struct grid{
//用于存储格子
int x,y;
};
bool check(int x,int y){
return (x>=1&&x<=n&&y>=1&&y<=m&&mp[x][y]==-1);
}void bfs(){
queue<grid>q;//开一个队列
q.push((grid){x,y});//把第一个格子压进去
while(!q.empty()){//没有遍历完
//取出当前要处理的格子
int xx=q.front().x,yy=q.front().y;
q.pop();//当前状态要处理了,不留在“待处理”中了
for(int i=0;i<8;i++){//所有方向
int xxx=xx+dx[i],yyy=yy+dy[i];
if(check(xxx,yyy)){//如果能走
q.push((grid){xxx,yyy});//放到“待处理”之中
mp[xxx][yyy]=mp[xx][yy]+1;//要处理到这里,就要多一步了
}
}
}return;
}int main(){
cin>>n>>m>>x>>y;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!(i==x&&j==y))mp[i][j]=-1;
}
}bfs();
for(int i=1;i<=n;i++){//输出
for(int j=1;j<=m;j++){
printf("%-5d",mp[i][j]);
}puts("");//换行
}return 0;
}
还有另外一道很简单的题目 P1451 求细胞数量,可以用类似于 DFS 篇的染色方法通过,当然用简单 BFS 也可以,参考代码:
#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int m,n,cnt,vis[1001][1001]={0};
char p[1001][1001];
struct grid{
int x,y;
};
queue<struct grid> q;
void BFS(){
cnt++;
while(!q.empty()){
int x=q.front().x;
int y=q.front().y;
vis[x][y]=1;
q.pop();
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(yy<m&&xx<n&&xx>=0&&yy>=0){
if(!vis[xx][yy]&&p[xx][yy]!='0'){
q.push({xx,yy});
}
}
}
}return;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++)for(int j=0;j<m;j++){
char c;
cin>>c;
if(c=='0')p[i][j]='0';
else p[i][j]='1';
}
for(int i=0;i<n;i++)for(int j=0;j<m;j++){
if(vis[i][j]==0&&p[i][j]!='0'){
q.push({i,j});
BFS();
}
}cout<<cnt<<endl;
return 0;
}
你可以试一试 P1135 奇怪的电梯,这是一道不错的搜索练手题,有特殊条件的搜索可以看看 P3956 [NOIP2017 普及组] 棋盘。
棋盘一题的代码,我是远古时代写的,可能不是很容易理解,但是还是贴上来:
#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int m,n,p[101][101];
int f[101][101];//记录最小花费
struct grid{
int x,y;
int cost,col;
bool mag;
};
void init(){
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
p[i][j]=-1;
f[i][j]=INF;
}
}
}queue<grid>q;
void BFS(){
while(!q.empty()){
//访问队头元素
int x=q.front().x,y=q.front().y;
int cs=q.front().cost,co=q.front().col;
bool ma=q.front().mag;
if(x==m&&y==m)f[m][m]=min(cs,f[m][m]);
if(cs>=f[x][y]){
q.pop();
continue;
}f[x][y]=cs;q.pop();
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(yy<=m&&xx<=m&&xx>0&&yy>0){
if(p[xx][yy]!=-1){
if(co==p[xx][yy]){
grid t={xx,yy,cs,co,true};
q.push(t);
}else{
grid t={xx,yy,cs+1,p[xx][yy],true};
q.push(t);
}
}else if(ma){
grid t={xx,yy,cs+2,co,false};
q.push(t);
}
}
}
}return;
}int main(){
cin>>m>>n;
init();
for(int i=0;i<n;i++){
int x,y,c;
cin>>x>>y>>c;
p[x][y]=c;
}q.push((grid){1,1,0,p[1][1],true});
BFS();
if(f[m][m]==INF)puts("-1");
else cout<<f[m][m]<<endl;
return 0;
}
记忆化搜索实际上是递归来实现的,但是递归的过程中有许多的结果是被反复计算的,这样会大大降低算法的执行效率。
记忆化搜索:
而记忆化搜索是在递归的过程中,将已经计算出来的结果保存起来,当之后的计算用到的时候直接取出结果,避免重复运算,因此极大的提高了算法的效率。我们可以把记忆化搜索看做是动态规划(虽然他本来就是)。
剪枝:
当目前状态和题意不符,并且由于题目可以推出,往后的所有情况和题意都不符,那么就可以进行剪枝,直接把这种情况及后续的所有情况判断不可行,直接返回。
当几个子树具有完全相同的效果的时候,只选择其中一个搜索。
在我们用搜索方法解决最优化问题的时候的一种常用剪枝。当搜索还未结束时,记录的状态已经比当前保存的最优解更劣,那么此方案一定无效,停止搜索并回溯即可。
普遍来讲,搜索的顺序是不固定的,对一个问题来说,算法可以进入搜索树的任意的一个子节点。
但假如我们要搜索一个最小值,而非要从最大值存在的那个节点开搜,就可能存在搜索到最后才出解。我们从最小的节点开搜很可能马上就出解。这就是顺序剪枝的一个应用。一般来讲,有单调性存在的搜索问题可以和贪心思想结合,进行顺序剪枝。
我们有时候会遇到一种问题,起点和终点是已知的,需要确定从起点到终点需要多少步。这时候,如果仅仅从起点进行搜索(以 BFS 为例),那么搜索树是巨大的,对于一个 $m$ 叉的搜索树,有 $m^n$ 中可能性。
但是,如果我们从起点和终点一起搜索呢?
这样的话,搜索的可能性一下子降到了 $2\times m^{n\div 2}$,相当于直接开方,复杂度的优化极其优秀。具体到算法上,有两种类型:双向 BFS 和双向迭代加深,这里主要介绍双向 BFS。
至于迭代加深和相关的搜索,会在之后的章节和大家探讨。
与朴素的 BFS 不同,双向广搜同时维护两个队列,轮流(或者说依次)入队。由于实现多线程不是很现实,单线程的交替也能起到类似的效果,每次拓展我们都可以用 hash 的思想对搜索的结果进行标记,当一个状态被两个队列的搜索过程标记时,就可以结束搜索、得出结果。
双向 BFS 可以使用的条件是知道起点和终点,并且双向移动不会影响答案,譬如 「例题」HDU 1401 Solitaire。这是一个双向搜索的标准题型,考虑分别从起点和终点进行搜索,各自走 $4$ 步,如果有交点则说明可以到达,由于这道题细节巨多,所以给出参考代码(参考代码是同学编写、依照标程修改风格、LOJ 格式化后压行的结果):
#include <bits/stdc++.h>
using namespace std;
struct grid {
int x, y;
bool check() {return (x < 8 && x >= 0 && y >= 0 && y < 8);}
};
struct node {
grid p[4];
int step;
} s, e;
char vis[8][8][8][8][8][8][8][8];
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
int mat[10][10];
bool cmp(grid a, grid b) { //排序
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}void make_map(node a) { //标记4个点的位置
mat[a.p[0].x][a.p[0].y] = 1;
mat[a.p[1].x][a.p[1].y] = 1;
mat[a.p[2].x][a.p[2].y] = 1;
mat[a.p[3].x][a.p[3].y] = 1;
}int judge(grid a) {
return (mat[a.x][a.y]);
}void make_vis(node a, char w){ //标记状态
vis[a.p[0].x][a.p[0].y][a.p[1].x][a.p[1].y][a.p[2].x][a.p[2].y][a.p[3].x][a.p[3].y] = w;
}char get_vis(node a) { //获得状态
return vis[a.p[0].x][a.p[0].y][a.p[1].x][a.p[1].y][a.p[2].x][a.p[2].y][a.p[3].x][a.p[3].y];
}bool bfs() {
node u, v;
memset(vis, 0, sizeof(vis));
make_vis(s, '1');make_vis(e, '2');
s.step = 0;e.step = 0;
queue<node>q, t;
q.push(s);t.push(e);
while (!q.empty() || !t.empty()) {
if (!q.empty()) {
u = q.front();q.pop();
memset(mat, 0, sizeof(mat));
make_map(u);
if (u.step >= 4)continue;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
v = u;v.step++;
v.p[j].x += dx[i],v.p[j].y += dy[i];
if (!v.p[j].check())continue;
if (judge(v.p[j])) { //跳步
v.p[j].x += dx[i],v.p[j].y += dy[i];
if (!v.p[j].check())continue;
}sort(v.p, v.p + 4, cmp);
if (get_vis(v) == '1')continue;
else if (get_vis(v) == '2')return 1;//可以到达终点
make_vis(v, '1');
q.push(v);
}
}
}if (!t.empty()) {
u = t.front();t.pop();
memset(mat, 0, sizeof(mat));
make_map(u);
if (u.step >= 4)continue;
if (get_vis(u) == '1')return 1;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
v = u;v.step++;
v.p[j].x += dx[i],v.p[j].y += dy[i];
if (!v.p[j].check())continue;
if (judge(v.p[j])) {
v.p[j].x += dx[i],v.p[j].y += dy[i];
if (!v.p[j].check())continue;
}sort(v.p, v.p + 4, cmp);
if (get_vis(v) == '1')return 1;
else if (get_vis(v) == '2')continue;
make_vis(v, '2');
t.push(v);
}
}
}
}return 0;
}int main() {
while (~scanf("%d%d", &s.p[0].x, &s.p[0].y)) {
for (int i = 1; i < 4; i++)scanf("%d%d", &s.p[i].x, &s.p[i].y);
for (int i = 0; i < 4; i++)scanf("%d%d", &e.p[i].x, &e.p[i].y);
for (int i = 0; i < 4; i++) {
s.p[i].x--;s.p[i].y--;
e.p[i].x--;e.p[i].y--;
}sort(s.p, s.p + 4, cmp);
sort(e.p, e.p + 4, cmp);
bfs() ? puts("YES") : puts("NO");
}return 0;
}
有这样的一种搜索树,它几乎无限宽也几乎无限深,对于这种情况怎么办呢?单纯的 DFS 可能会陷入无限的递归无法得出结果,BFS 的话队列空间是无法承受的,而你不知道具体的终点所在所以也不能用双向 BFS,这时候我们可以采用迭代加深搜索:IDDFS。
是的,这是一种以 BFS 为核心思想,以 DFS 为实现手段的算法,具体过程如下:
在每一层的迭代看起来特别像 BFS,而实现则是用 DFS。这种算法的前提是必须有解,再进一步,我们确定最优解在浅层的时候,应该使用 IDDFS。
剪枝可以使用乐观估计函数,估计从当前深度到找到最终的解「至少」还需要多少步,或者距离找到最终的解还需要扩展多少层,如果超过了设定的最大深度,就不可能再当前深度找到解了,可以退出这一轮搜索。
关于例题的内容,洛谷似乎没有足够板子的练迭代加深搜索的题目,那就看看这个吧 hzaukotete:搜索进阶-迭代加深搜索。
我们会发现,单纯的 BFS 要找到一个目的地,几乎要走遍所有的结点,比如从 $(1,1)\to (n,n)$ 类型的题目。而启发式搜索很好的解决了这种「盲目」引起的问题,换言之,启发式搜索引入了一个「方向感」的概念。
我们知道有一种搜索叫做 GFS(真的有吗),全程是 Greedy First Search 即贪心最优搜索,只前往当前距离终点最优的节点,这样子在开阔的图中可以很快获得答案(因为贪心搜索的收敛速度很快),但是往往不能得到正确答案,在特殊情况下甚至不能得到答案,譬如:
...........
.########..
........#..
S.......#.E
........#..
.########..
...........
显然,对于这种图,从 $s$ 出发的贪心搜索会卡在这个凹槽之中不能出来。那怎么解决呢?只要使用正确的估价函数,我们就可以避免这种误区——估价函数是 A* 算法的核心。引入一个概念叫做曼哈顿距离,具体请见 Heartlessly 的博客 - 常用距离算法详解.
设 $x$ 是现在的状态,那么 $f(x)$ 就是他的评估函数,存在:
$$f(x)=g(x)+h(x)$$
其中 $g(x)$ 是从起点到当前状态的代价(譬如走过的步数),而 $h(x)$ 则是预估的到终点的代价。可以发现,$h(x)$ 决定了 A* 算法的优劣,我们需要一种不能漏掉最优解的 $h(x)$。同时,存在两条重要的性质:
这样我们可以避开很多不必要搜到的点,大大优化我们的搜索过程。
将 A* 套入迭代加深的思想,就是 IDA*,这两种算法解决的问题较难(说人话就是作者菜),这里有例题但没有代码。
IDA* 例题:P2324 [SCOI2005]骑士精神
发现“在 $15$ 步以内”这一限制条件,绝佳的迭代加深。而估价函数则考虑“每次空白格子和黑白棋子交换,最优的情况就是每次都把黑白棋子移动到目标格子。”进行一些优化可以通过此题,具体参考题解区。
这就是基础搜索的内容了。
感谢阅读,写的挺累的,那我就求个赞吧。
开发者:Federico2903 & Murasame & quanac-lcx