算法笔记：系统的回顾搜索算法

Aw顿顿 · 2021-02-19 23:26:19 · 个人记录

搜索专项复习：未来的暴力打满

本文同步发布于：学习笔记：快速精通基本搜索

配套训练题单：【搜索】暴力专项训练

在我写这个学习笔记的时候，我默认读者已经熟练掌握 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\} 中第几大的排列，我们可以考虑以下排列的和：

• 首位小于 2 的排列：1\times 3!=6。
• 首位为 2 第二位小于 1 的排列：0\times 2!=0。
• 前两位为 21 第三位小于 4 的排列：1\times 1!=1。
• 前三位为 214 第四位小于 3 的排列：0\times 0!=0。

那么这样一个过程怎么归纳成公式呢？我们把他们加起来，答案是 7，也就是在这个排列之前有 7 个排列，也就是说这是排名为 8 的全排列，那么我们把巨大的一个范围的全排列映射到了一个小范围，就可以用传统 vis 数组解决了。

我们把一个集合产生的全排列按字典序排序，则第 X 个排列的计算公式如下：

当然也有逆康托展开，给定集合和排名，算出对应的排列，方法类似。

DFS 深度优先搜索

DFS (Depth First Search)，常常用于遍历树或图，而往往也可以代指利用递归来实现暴力枚举。图论意义上的 DFS 基本思想是「一条路走到底」，并且在走的过程中将走过的结点做好标记，确保每个点仅访问一次，并且在「走不通」时可以返回，继续尝试下一条路径。

广义上，使用递归调用自身实现的、每个状态仅访问一次的遍历，就可以成为深度优先搜索。在递归遍历一个问题所有的可能解（此时的复杂度往往是指数级别的）、搜索所有满足题意情况时，DFS 的复杂度较高，而对于遍历一个给定的图，他的复杂度并不会难以想象（除非在遍历的过程中有特定的任务，必须多次访问同一节点，譬如最短路）。

特别地，对于一个图的深度优先遍历步骤如下：

• 确定起点 V_0，进行标记。
• 对于其出边，标记为「已经走过」并递归遍历该节点，之后标记归零。
• 遍历下一节点。

这样一个实现简单，思路清晰的步骤使得 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;
}

「例题」：P1036 [NOIP2002 普及组] 选数

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);//调用
}

BFS 广度优先搜索

广度优先搜索，是一种效率上不错，程序也容易理解的算法。

假设现在我们在某一个状态（可能是某个格子，某个结点，某个情况），而接下来我们要搜索与之相关的所有情况，如何保证搜索顺序？这需要用到队列（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 为实现手段的算法，具体过程如下：

• 设定深度为 1，如果深搜到答案则结束。
• 如果没搜到答案，更改深度为 2，搜索前两层。
• 如果没搜到答案，更改深度为 3，重复此过程。

在每一层的迭代看起来特别像 BFS，而实现则是用 DFS。这种算法的前提是必须有解，再进一步，我们确定最优解在浅层的时候，应该使用 IDDFS。

剪枝可以使用乐观估计函数，估计从当前深度到找到最终的解「至少」还需要多少步，或者距离找到最终的解还需要扩展多少层，如果超过了设定的最大深度，就不可能再当前深度找到解了，可以退出这一轮搜索。

关于例题的内容，洛谷似乎没有足够板子的练迭代加深搜索的题目，那就看看这个吧 hzaukotete：搜索进阶-迭代加深搜索。

A* 启发式搜索和 IDA* 迭代加深启发式搜索

我们会发现，单纯的 BFS 要找到一个目的地，几乎要走遍所有的结点，比如从 (1,1)\to (n,n) 类型的题目。而启发式搜索很好的解决了这种「盲目」引起的问题，换言之，启发式搜索引入了一个「方向感」的概念。

我们知道有一种搜索叫做 GFS（真的有吗），全程是 Greedy First Search 即贪心最优搜索，只前往当前距离终点最优的节点，这样子在开阔的图中可以很快获得答案（因为贪心搜索的收敛速度很快），但是往往不能得到正确答案，在特殊情况下甚至不能得到答案，譬如：

...........
.########..
........#..
S.......#.E
........#..
.########..
...........

显然，对于这种图，从 s 出发的贪心搜索会卡在这个凹槽之中不能出来。那怎么解决呢？只要使用正确的估价函数，我们就可以避免这种误区——估价函数是 A* 算法的核心。引入一个概念叫做曼哈顿距离，具体请见 Heartlessly 的博客 - 常用距离算法详解.

设 x 是现在的状态，那么 f(x) 就是他的评估函数，存在：

其中 g(x) 是从起点到当前状态的代价（譬如走过的步数），而 h(x) 则是预估的到终点的代价。可以发现，h(x) 决定了 A* 算法的优劣，我们需要一种不能漏掉最优解的 h(x)。同时，存在两条重要的性质：

• 若 h(x)=0 那么该算法就是朴素 BFS。
• 若 g(x)=0 那么该算法就是朴素贪心搜索。

这样我们可以避开很多不必要搜到的点，大大优化我们的搜索过程。

将 A* 套入迭代加深的思想，就是 IDA*，这两种算法解决的问题较难（说人话就是作者菜），这里有例题但没有代码。

IDA* 例题：P2324 [SCOI2005]骑士精神

发现“在 15 步以内”这一限制条件，绝佳的迭代加深。而估价函数则考虑“每次空白格子和黑白棋子交换，最优的情况就是每次都把黑白棋子移动到目标格子。”进行一些优化可以通过此题，具体参考题解区。

后话

这就是基础搜索的内容了。

感谢阅读，写的挺累的，那我就求个赞吧。