【算法】搜索技术

大部分搜索技术都是基于图进行搜索的，这里先列出几种图的简单表示方式

  • 邻接链表

  • 邻接矩阵

暴力搜索

搜索过程有两种常见的基础策略，分别是 DFS（深度优先搜索）和 BFS（广度优先搜索）

对于 DFS，深度优先，具体代码实现就要使用栈来实现，每次加入路径时，实现先进后出。对于 BFS，具体代码实现就要使用队列，先进先出的访问路径。

给一道例题，提供 BFS 和 DFS 的标程

标程例题

很简单的搜索题，这里没有卡时间空间，暴力搜索就可以了，具体代码实现时可以定义一个方向数组来方便搜索。

代码( BFS 和 DFS 的都在一起)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
int dir[4][2] = {
    {0,1},{0,-1},{1,0},{-1,0}
}
int Wx,Hy,num;
struct node{
    int x,y;
};
char room[23][23]
bool check(int x,int y){
    return (x<Wx && y<Hy && x>=0 && y>=0);
}

void bfs(int dx,int dy){
    num = 1;
    node start,next;
    queue<node> q;
    start.x = dx;
    start.y = dy;
    q.push(start);
    while(!q.empty()){
        start = q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int x = dx+dir[i][0];
            int y = dx+dir[i][1];
            if(check(x,y)||room[x][y]=='.'){
                next.x = x;
                next.y = y;
                q.push(next);
                room[x][y]='#';
                num++;
            }
        }
    }
}

void dfs(int dx,int dy){
    num = 1;
    node start,next;
    start.x = dx;
    start.y = dy;
    stack<node> st;
    st.push(start);
    while(!st.empty()){
        start = st.top();
        st.pop();
        for(int i=0;i<4;i++){
            int x = start.x + dir[i][0];
            int y = start.y + dir[i][1];
            next.x = x;
            next.y = y;
            if(check(x,y)&&room[x][y]=='.'){
                st.push(next);
                num++;
                room[x][y]='#';
            }
        }
    }
}

int main(){
    int dx,dy;
    while(cin>>Wx>>Hy){
        if(Wx==0||Hy==0){
            break;
        }
        for(int y=0;y<Hy;y++){
            for(int x=0;x<Wx;x++){
                cin>>char[x][y];
                if(char[x][y] == '@'){
                    dx = x;
                    dy = y;
                }
            }
        }
        num = 0;
        bfs(); //或者 dfs
        cout<<num<<endl;
    }
    return 0;
}

非标准搜索

有时搜索会碰到一些比较奇怪的走法，例题

这道题因为要记录所有点的最少步数，要用 BFS 去记录（要先进先出才能确保是最少的），然后因为是日子型走，所以方向数组有 8 种情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int map[410][410];
bool vis[410][410];
int ans[410][410];
int n,m;
int dx={2,1,1,2,-1,-2,-2,-1};
int dy={1,2,-2,-1,2,1,-1,-2};
struct Point{
    int x,y;
    Point(int xx,int yy):x(xx),y(yy){}
};
queue<Point> que;

bool check(int x,int y){
    return (x<n&&x>1&&y<m&&y>1);
}

void bfs(int x,int y){
    int sum=0;
    vis[x][y]=true;
    que.push(Point(x,y));
    while(!que.empty()){
        Point top = que.front();
        que.pop();
        sum = ans[top.x][top.y] + 1;
        for(int i=0;i<8;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(check(nx,ny)&&!vis[nx][ny]){
                vis[nx][ny]=true;
                que.push(Point(nx,ny));
                ans[nx][ny] = sum;
            }
        }
    }
}

int main(){
    int x,y,n,m;
    cin>>n>>m>>x>>y;
    memset(ans,-1,sizeof(ans));
    bfs(x,y);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<ans[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

这里要注意的是 memset， memset 是不能乱用的，通常只有以下几种赋值方式：

搜索进阶

搜索状态优化

先给一道例题：

看似是一个很简单的搜索，但其实别有洞天，注意这里的卡常(HDU)，无论是内存还是时间都卡的很死，对于八数码问题，我们将棋盘展开成一维数组 012345678 ，其中 0 代表空格，然后我们将每次移动后产生的数组存入队列或者栈中实现 BFS 或者 DFS 来进行搜索，如果不做任何优化，复杂度就是指数级别

这里可以先做一个剪枝，因为有些状态是重复了的，可以用 STL 容器 set 来进行去重，但是去重后还是会 TLE，因为set 容器内部是由红黑树实现的，他的插入复杂度都是$O(logn)$ 。

再去思考能否使用哈希去实现，哈希实现映射的复杂度是$O(1)$，但是在计算哈希值的时候，复杂度是$O(m)$，$m$ 为字符串长度，直接使用哈希还是会超时的，无论是自定义的哈希还是 unordered_set容器

解决方案是使用打表法，先提前把所有映射值给打出来，就节约了先前构建映射的计算过程，但是除了时间复杂度，这道题还是会考空间复杂度，让我们对哈希的空间复杂度再做分析。

一共 9 个字符串，总共 $9!=362880$ 种状态，存取这么多个 int 数组需要

$$ 362880 \times 4/1024/1024 \approx 1.38M $$

但是这是完全没有碎片情况下的存取空间（完全连续），哈希值的计算并不是连续的，他有很大的随机性，题目给的空间限制大约为 $30M$，差值为 $30$ 倍的容错值不保证能够通过所有案例，这里使用一种康托展开，来获取完全连续的存取空间。

康托展开通过获取全排列的方式，连续填充数组，如下表，康托值代表第几小的排列

康托展开的计算通式为

$$ f(\sigma) = \sum_{i=1}^{n} a_i \cdot (n-i)! $$

其中：

  • $\sigma$ 是一个长度为 $n$ 的排列。
  • $a_i$ 是在 $\sigma$ 的第 $i$ 个位置上的数字右边比它小的数字的个数。

如：计算 2143 在 {1,2,3,4} 的康托值

$$Cantor=1 \times 3!+0 \times 2!+1 \times 1! + 0=7$$

在这道题中，使用康托展开来存取映射关系，就可以保证是一个完全连续的内存空间进行存取，空间占用率能够达到 $1.38M$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<iostream>
#include<queue>
#include<string>
using namespace std;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
string d = "durl";
//节点
struct node{
    string state;
    int cantor;
    int pos;
    node(string ss,int cc,int pp){
        state=ss;cantor=cc;pos=pp;
    }
};
//用来记录路径的
struct path{
    int from; //上一个状态的cantor 值
    char dir; //上一个状态过来的方向
}pa[362888];

//用来判断边界
bool legal(int x,int y){
    if(x>=0&&x<=2&&y>=0&&y<=2){
        return true;
    }
    return false;
}

int visited[362888] = {0};
//把阶乘的结果打表
int factory[]={1,1,2,6,24,120,720,5040,40320,362880};

int getContor(string str){
    int res=0;
    for(int i=0;i<9;i++){
        int cnt=0;
        for(int j=i+1;j<9;j++){
            if(str[i]>str[j]){
                cnt++;
            }
        }
        res += cnt*factory[9-i-1];
    }
    return res;
}

void bfs(string init){
    queue<node> q;
    int num = getContor(init);
    q.push(node(init,num,8));
    visited[num]=1;
    // 终止条件
    pa[num].from=-1;
    while(!q.empty()){
        node top = q.front();
        q.pop();
        // 计算 x 点的x,y 坐标
        int x = top.pos/3;
        int y = top.pos%3;
        for(int i=0;i<4;i++){
            int xx = x + dir[i][0];
            int yy = y + dir[i][1];
            if(!legal(xx,yy))
                continue;
            int new_pos = xx*3 + yy;
            string next_state = top.state;
            swap(next_state[top.pos],next_state[new_pos]);
            num = getContor(next_state);
            if(visited[num])
                continue;
            q.push(node(next_state,num,new_pos));
            visited[num]=1;
            pa[num].from = top.cantor;
            pa[num].dir = d[i];
        }
    }
}

int main(){
    //打表提前计算映射
    bfs("12345678x");
    string tmp;
    while(getline(cin,tmp)){
        string puzzle;
        for(int i=0;i<tmp.size();i++){
            //注意过滤空格
            if(tmp[i]!=' '){
                puzzle.push_back(tmp[i]);
            }
        }
        int num = getContor(puzzle);
        if(visited[num]==0){
            cout<<"unsolvable"<<endl;
            continue;
        }
        while(true){
            if(pa[num].from==-1){
                break;
            }
            cout<<pa[num].dir;
            num = pa[num].from;
        }
        cout<<endl;
    }
    return 0;
}

双向bfs

双向 bfs 顾名思义就是分别从开头和结尾进行两个方向的 bfs，当出现交集的时候，停止 bfs，代表找到路径。bfs 循环在两个队列都为非空的时候才会进行。

为了避免双向 bfs 退化成单向 bfs，要引入一些搜索策略，每次选择元素较少的队列进行 bfs，交替逐层搜索。

例题

双向 bfs 标程，直接给代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int,int> P;
int r,c,ans;
queue<P> q1,q2;
int dis[45][45],vst[45][45] = {0}; //dis 记录走了多少步，vst 记录是谁访问这个节点
int dx = {1,0,-1,0};
int dy = {0,1,0,-1};
char m[45][45];

void dbfs(){
    bool flag;
    q1.push(P(1,1)), dis[1][1]=1, vst[1][1]=1;
    q2.push(P(r,c)), dis[r][c]=1, vst[r][c]=2;
    while(!q1.empty()&&!q2.empty()){
        int x0,y0;
        if(q1.size()>q2.size()){
            x0 = q2.front().first;
            y0 = q2.front().second;
            q2.pop();
            flag=0;
        }
        else{
            x0 = q1.front().first;
            y0 = q1.front().second;
            q1.pop();
            flag=1;
        }
        for(int i=0;i<4;i++){
            int nx = x0 + dx[i];
            int ny = y0 + dy[i];
            if(nx>=1&&nx<=r&&ny>=1&&ny<=c&&map[nx][ny]=='.'){
                if(!dis[nx][ny]){
                    dis[nx][ny]=dis[x0][y0]+1;
                    vst[nx][ny]=vst[x0][y0];
                    if(flag) q1.push(P(nx,ny));
                    else q2.push(P(nx,ny));
                }
                else{
                    // 如果相遇了
                    if(vst[nx][ny]+vst[x0][y0]==3)
                        ans = dis[nx][ny] + dis[x0][y0];
                        return;
                }
            }
        }
    }
}

int main(){
    cin>>r>>c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>m[i][j];
        }
    }
    dbfs();
    cout<<ans<<endl;
    return 0;
}

二进制状压bfs

二进制状压适用于带状态的搜索过程，来节约存储状态所带来的内存开销，使用以下常见的二进制操作来变更状态

例题：

这道题需要携带钥匙进行搜索，这个携带的钥匙就是搜索过程中的状态，钥匙有a~j一共 10 把钥匙，这里 10 把钥匙可以用一个由 0 和 1 组成的 int 数来表示，0表示没拿这把钥匙，1 表示拿了这把钥匙，然后如果捡到了钥匙，使用二进制操作 x|(1<<(k-1)) 把他变成 1 即可。

这里注意还有时间限制，时间限制为 t，就代表我们的搜索层数不能超过 t 层。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int n,m,t;
char mp[25][25];
bool vis[25][25][1<<11];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
struct node{
    int x,y,key,Time;
    node(){};
    node(int xx,int yy,int kk,int tt){
        x=xx;y=yy;key=kk;Time=tt;
    }
};
queue<node> q;

int bfs(int stx,int sty){
    q.push(node(stx,sty,0,0));
    node now;
    int x,y,key;
    vis[stx][sty][0] = true;
    while(!q.empty()){
        now = q.front();
        q.pop();
        if(now.Time>=t)
            return -1;
        if(mp[now.x][now.y] == '^'){
            return now.Time;
        }
        for(int i=0;i<4;i++){
            x = now.x+dir[i][0];
            y = now.y+dir[i][1];
            key = 0;
            if(x>=0&&x<=n-1&&y>=0&&y<=m-1&&mp[x][y]!='*'&&!vis[x][y][now.key]){
                if(mp[x][y]>='a'&&mp[x][y]<='j'){
                    // 这里用二进制操作将对应的元素变成 1
                    key |= (1<<(mp[x][y]-'a'));
                }
                else if(mp[x][y]>='A'&& mp[x][y]<='J'){
                    // 这里用二进制操作定位对应的元素,判断他是否为1,如果不是 1 就 continue
                    if(!(now.key&(1<<(mp[x][y]-'A')))){
                        continue;
                    }
                }
                q.push(node(x,y,now.key|key,now.Time+1));
                vis[x][y][now.key]=true;
            }
        }
    }
    return -1;
}

int main(){
    int ans,stx,sty;
    while(cin>>n>>m>>t){
        // 记得初始化
        memset(vis,0,sizeof(vis));
        while(!q.empty()){
            q.pop();
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>mp[i][j];
                if(mp[i][j]=='@'){
                    stx = i;
                    sty = j;
                }
            }
        }
        ans = bfs(stx,sty);
        cout<<ans<<endl;
    }
    return 0;
}