搜索

05-搜索 BFS, DFS, 二分, 回溯法 评论

1 DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int check(参数)
{
    if(满足条件)
        return 1;
    return 0;
}
 
void dfs(int step)
{
        判断边界
        {
            相应操作
        }
        尝试每一种可能
        {
               满足check条件
               标记
               继续下一步dfs(step+1)
               恢复初始状态（回溯的时候要用到）
        }
}

2 BFS

BFS使用队列，把每个还没有搜索到的点一次放入队列，然后再弹出队列的头部元素当做当前遍历点。当不需要确定当前遍历层数时：

1
2
3
4
5
6
queue.push(s)//压入起点，初始队列可能有多个起点
while queue 不空：
    cur = queue.pop()
    for 节点 in cur的所有相邻节点：
        if 该节点有效且未访问过：
            queue.push(该节点)

当需要确定遍历层数时，这里增加了level表示当前遍历到二叉树中的哪一层了，也可以理解为在一个图中，现在已经走了多少步了。size表示在开始遍历新的一层时，队列中有多少个元素，即有多少个点需要向前走一步。

1
2
3
4
5
6
7
8
9
10
11
queue.push(s)//压入起点
level = 0
while queue 不空：
    size = queue.size()
    while (size --) {
        cur = queue.pop()
        for 节点 in cur的所有相邻节点：
            if 该节点有效且未被访问过：
                queue.push(该节点)
    }
    level ++

3 二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 在[l, h)范围内查找值v(l>=0),返回下标,假设a数组已经按从⼩到⼤排序,失败返回-1
int bs(int a[], int l, int h, int v){
	int m;
	while (l < h){
		m = (l + h) >> 1;
		if (a[m] == v){
			return m;
		}
		if (a[m] < v){
			l = m + 1;
		}
		else{
			h = m;
		}
	}
	return -1;
}

4 双向搜索

起点是给出的，终点也是已知的，需要确定能否从起点到达终点，如果可以，需要多少步。

如果我们用常规的搜索方法，从起点开始往下搜，那得到的解答树可能非常庞大，这样漫无目的的搜索就像大海捞针。让我们切换一下思路，既然终点是已知的，我们何必让它闲着呢？我们完全可以分别从起点和终点出发，看它们能否相遇。

如果原本的解答树规模是 [公式] ，使用双向搜索后，规模立刻缩小到了约 [公式] ，当 [公式] 较大时优化非常可观。

双向搜索主要有两种，双向BFS和双向迭代加深。

4.1 双向BFS

与普通的BFS不同，双向BFS维护两个而不是一个队列，然后轮流拓展两个队列。同时，用数组（如果状态可以被表示为较小的整数）或哈希表记录当前的搜索情况，给从两个方向拓展的节点以不同的标记。当某点被两种标记同时标记时，搜索结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
queue<T> Q[3]; // T要替换为用来表示状态的类型，可能为int，string还有bitset等
bool found = false;
Q[1].push(st); // st为起始状态
Q[2].push(ed); // ed为终止状态
for (int d = 0; d < D + 2; ++d) // D为最大深度，最后答案为d-1
{
    int dir = (d & 1) + 1, sz = Q[dir].size(); // 记录一下当前的搜索方向，1为正向，2为反向
    for (int i = 0; i < sz; ++i)
    {
        auto x = Q[dir].front();
        Q[dir].pop();
        if (H[x] + dir == 3) // H是数组或哈希表，若H[x]+dir==3说明两个方向都搜到过这个点
            found = true;
        H[x] = dir;
        // 这里需要把当前状态能够转移到的新状态压入队列
    }
    if (found)
        // ...
}

4.2 双向迭代加深

迭代加深算法是那种，听名字非常高端，思想和实现却都很简单的算法。就是控制dfs的最大深度，如果深度超过最大深度就返回。某个深度搜完后没有得到答案便令最大深度+1，然后重新开始搜索。

这听起来好像效果跟广搜差不多啊？还重复搜索了很多次。但是，由于搜索的时间复杂度几乎完全由解答树的最后一层确定（看上面第一张图就能感悟到），所以它与BFS在时间上只有常数级别的差距，以此换来的优势是：空间占用很小，有时候方便剪枝、方便传参等。

双向迭代加深就是相应地，从两个方向迭代加深搜索。先从起点开始搜0层，再从终点开始搜0层，然后从起点开始搜1层……

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
int D;
bool found;
template <class T>
void dfs(T x, int d, int dir)
{
    if (H[x] + dir == 3)
        found = true;
    H[x] = dir;
    if (d == D)
        return;
    // 这里需要递归搜索当前状态能够转移到的新状态
}

// 在main函数中...
while (D <= MAXD / 2) // MAXD为题中要求的最大深度
{
    dfs(st, 0, 1); // st为起始状态
    if (found)
        // ...
        // 题中所给最大深度为奇数时这里要判断一下
    dfs(ed, 0, 2); // ed为终止状态
    if (found)
        // ...
    D++;
}

https://zhuanlan.zhihu.com/p/119349440

5 极大极小值搜索算法

简单的对抗搜索

评估函数的返回值直接设定成题目中的评估得分即可

在博弈树搜索时，先手返回能向下递归所得的最大值，后手反之返回最小值

如果某种状态已经分出胜负或者平手，就说明该种状态就是博弈树中的叶子节点，需要计算评估得分进行返回

数据很小可以不用alpha-beta剪枝

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
#include<bits/stdc++.h>
#define rep(x,a,b) for(int x=(a);x<=(b);x++)
using namespace std;
const int maxn=4;
int a[maxn][maxn];//棋盘 
int check(){
    //计算评估分数，-2000代表还能继续进行棋局
    int x=0;
    rep(i,0,2)
        rep(j,0,2)
            x+=(a[i][j]==0);
    rep(i,0,2){//A或B获胜 
        if(a[i][0]==1&&a[i][1]==1&&a[i][2]==1) return x+1;
        if(a[i][0]==2&&a[i][1]==2&&a[i][2]==2) return -x-1;
        if(a[0][i]==1&&a[1][i]==1&&a[2][i]==1) return x+1;
        if(a[0][i]==2&&a[1][i]==2&&a[2][i]==2) return -x-1;
    }
    //A或B获胜 
    if(a[0][0]==1&&a[1][1]==1&&a[2][2]==1) return x+1;
    if(a[0][2]==1&&a[1][1]==1&&a[2][0]==1) return x+1;
    if(a[0][0]==2&&a[1][1]==2&&a[2][2]==2) return -x-1;
    if(a[0][2]==2&&a[1][1]==2&&a[2][0]==2) return -x-1;
    if(x==0) return 0;//平局 
    else return -2000;//棋局未结束 
}
int dfs(int dep){
    //dep=0代表先手，1代表后手
    int res=check();
    if(res!=-2000)//棋局结束 
		return res;//叶子节点返回
    int Res = dep==0 ? -1000:1000;
    rep(i,0,2)
        rep(j,0,2){
            if(!a[i][j]){
                a[i][j] = dep==0 ? 1:2;//打标签 
                if( dep==0 )//先手找最大
					Res = max(Res, dfs(dep^1));//按位异或实现01轮流下棋
                else//后手找最小
					Res = min(Res, dfs(dep^1));
                a[i][j] = 0;//去标签 
            }
        }
    return Res;
}
int main(){
	ios::sync_with_stdio(false);
    int T;//测试组数 
	cin>> T;
    while(T--){
        rep(i,0,2)//输入当前棋盘 
            rep(j,0,2)
                cin>> a[i][j];
        cout<< dfs(0)<< endl;
    }
    return 0;
}

使用用alpha-beta剪枝：

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
#include<bits/stdc++.h>
#define rep(x,a,b) for(int x=(a);x<=(b);x++)
using namespace std;
const int maxn=4;
int a[maxn][maxn];//棋盘 
int check(){
    //计算评估分数，-2000代表还能继续进行棋局
    int x=0;
    rep(i,0,2)
        rep(j,0,2)
            x+=(a[i][j]==0);
    rep(i,0,2){//A或B获胜 
        if(a[i][0]==1&&a[i][1]==1&&a[i][2]==1) return x+1;
        if(a[i][0]==2&&a[i][1]==2&&a[i][2]==2) return -x-1;
        if(a[0][i]==1&&a[1][i]==1&&a[2][i]==1) return x+1;
        if(a[0][i]==2&&a[1][i]==2&&a[2][i]==2) return -x-1;
    }
    //A或B获胜 
    if(a[0][0]==1&&a[1][1]==1&&a[2][2]==1) return x+1;
    if(a[0][2]==1&&a[1][1]==1&&a[2][0]==1) return x+1;
    if(a[0][0]==2&&a[1][1]==2&&a[2][2]==2) return -x-1;
    if(a[0][2]==2&&a[1][1]==2&&a[2][0]==2) return -x-1;
    if(x==0) return 0;//平局 
    else return -2000;//棋局未结束 
}
int dfs(int dep, int lval){
	//dep=0代表先手，1代表后手
    //lval表示如果父亲是先手就是父亲的alpha，否则是父亲的beta
    int res=check();
    if(res!=-2000)//棋局结束  
		return res;
    if(dep==0){
        int alpha=-1e9;//alpha表示先手能找到的最大值
        rep(i,0,2)
            rep(j,0,2)
                if(!a[i][j]){
                    a[i][j]=1;
                    alpha=max(alpha,dfs(dep^1,alpha));
                    a[i][j]=0;
                    if(alpha>lval) return alpha;
                    //如果先手能找到的最大值比后手父亲能找到的最小值还大，后手父亲就肯定不选当前的子树，直接返回进行剪枝
                }
        return alpha;
    }
    else{
        int beta=1e9;//beta表示后手能找到的最小值
        rep(i,0,2)
            rep(j,0,2)
                if(!a[i][j]){
                    a[i][j]=2;
                    beta=min(beta,dfs(dep^1,beta));
                    a[i][j]=0;
                    if(beta<lval) return beta;
                    //反之同理
                }
        return beta;
    }
}
int main(){
	ios::sync_with_stdio(false);
    int T;//测试组数 
	cin>> T;
    while(T--){
        rep(i,0,2)//输入当前棋盘 
            rep(j,0,2)
                cin>> a[i][j];
        cout<< dfs(0, 1e9)<< endl;
    }
    return 0;
}

练习

Dragon's BlogsAlgorithm

Life is painting a picture, not doing a sum.