搜索

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;
}

练习