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 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 ]; bool found = false ;Q[1 ].push(st); Q[2 ].push(ed); for (int d = 0 ; d < D + 2 ; ++d) { int dir = (d & 1 ) + 1 , sz = Q[dir].size (); for (int i = 0 ; i < sz; ++i) { auto x = Q[dir].front(); Q[dir].pop(); if (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 ; } while (D <= MAXD / 2 ) { dfs(st, 0 , 1 ); if (found) dfs(ed, 0 , 2 ); 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 () { int x=0 ; rep(i,0 ,2 ) rep(j,0 ,2 ) x+=(a[i][j]==0 ); rep(i,0 ,2 ){ 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 ; } 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 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 )); 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 () { int x=0 ; rep(i,0 ,2 ) rep(j,0 ,2 ) x+=(a[i][j]==0 ); rep(i,0 ,2 ){ 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 ; } 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) { int res=check(); if (res!=-2000 ) return res; if (dep==0 ){ int alpha=-1e9 ; 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 ; 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 ; }
练习
Life is painting a picture, not doing a sum.