搜索#

搜索就是对状态空间进行枚举来查找所有种可能来找到问题的最优解或可行解的个数。搜索一般时间或空间复杂度很高，所以有很多优化方法,如记忆化、减枝等。

注意#

不同的搜索题目大都不相同，DFS/BFS两种算法更像是方法，要理解它的思想并灵活运用，死套模板是没有用的。要根据不同的问题来选择更好的方法来解决。

一.DFS 深度优先搜索#

定义#

一种用于遍历或搜索树或图的算法（俗称 ~~不撞南墙不回头算法~~ ）。沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为 $O(!n)$ 。

适用#

主要用于搜索整个树或图，即求解所有解使用dfs较为合适。但是dfs的时间复杂度很高，费时，省空间。一般可以对dfs算法进行剪枝来降低时间复杂度。

基本思想#

1.找到一种可能的情况进行向前搜索。

2.如果搜索途中发现不可行，则回退一步，选择另外一种情况继续搜索。

3.重复以上步骤，直到搜完或找到最优解。

实现#

对于DFS的写法有很多种，最常见也是最好用的实现方式为递归算法。（递归相关知识link）

详细写法看模板代码注释。

模板#

1
bool visit[maxn];//标记数组，用来判断是否访问过
2
int a[maxn];
3

4
void dfs(int k) {
5
    if () {//递归出口
6
        print();//已经跑完那就输出吧(^_^)
7
        return;//记得结束循环，小心死循环
8
    } else {
9
        for (i in range(n)) {//遍历在这个位置可以搜索的所有情况
10
            if (!visit[i]) {//判断是否已经访问过，如果类似迷宫的题目建议单独写一个check
11
                visit[i] = 1;//先把当前点标记
12
                a[k + 1] = i;
13
                dfs(k + 1);//搜索下一种情况
14
                visit[i] = 0;//回溯后清除标记（如果不需要回溯可以不写）
15
            }
16
        }
17
    }
18
}

二.BFS宽度优先搜索#

定义#

是图上最基础、最重要的搜索算法之一。

所谓宽度优先。就是每次都尝试访问同一层的节点。如果同一层都访问完了，再访问下一层。

这样做的结果是，BFS 算法找到的路径是从起点开始的最短合法路径。换言之，这条路径所包含的边数最小。

在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。

基本思想#

用队列来存储每一个点，然后每个点都向下扩展 $N$ 个点，不断搜索，直到找到答案。这个过程有点像”一生二，二生四······”。使用这种方法可以很快找到最短的合法路径。这种方法时间复杂度较低，但是，bfs的空间复杂度相较来说较高。

Code#

1
void bfs() {
2
    queue<int> q1, q2;
3
    q1.push(1);
4
    q2.push(1);
5
    sum[1][1] = 1;
6
    while (!q1.empty()) {
7
        int x = q1.front();
8
        q1.pop();
9
        int y = q2.front();
10
        q2.pop();
11
        vis[x][y] = 1;
12
        for (int i = 0; i < 4; i++) {//遍历四个方向
13
            if (check(x + dx[i], y + dy[i])) {//pd
14
                sum[x + dx[i]][y + dy[i]] = sum[x][y] + 1;
15
                q1.push(x + dx[i]);
16
                q2.push(y + dy[i]);
17
                vis[x + dx[i]][y + dy[i]] = 1;
18
                if (x + dx[i] == R && y + dy[i] == C) {//bfs出口
19
                    return;
20
                }
21
            }
22
        }
23
    }
24
}

优化#

在带权有向图/带权树中，最小代价不一定是最短的路径。所以我们可以使用优先队列/双端队列来优化。