搜索笔记分享

常规
1

前言

搜索分成两类: BFS, DFS.
很多人不知道应该怎么选择两种方法， 我的一般方法是：看到“最短”“最小”等字眼时选用BFS， 看到“路径数”或数据范围较小的“暴力”题时用DFS。

原理剖析

BFS

无需多言， 原理图解释一切：

image
image1774×893 35.5 KB

可以看到， BFS按层遍历节点， 因此最先找到的点 一定是最短路径上的点 (可以理解为像水一样从全部路径流下来， 水流速相同， 用时最短找到的点就是最短路径的终点) 故BFS有时可以用来求最优解
上伪代码：

bfs(s) {
  q = new queue()
  q.push(s), visited[s] = true
  while (!q.empty()) {
    u = q.pop()
    for each edge(u, v) {
      if (!visited[v]) {
        q.push(v)
        visited[v] = true
      }
    }
  }
}

DFS

上图！

1478×984 393 KB

啊不是
image
DFS 最显著的特征在于其 递归调用自身 。同时与 BFS 类似，DFS 会对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以确保 每个点仅访问一次 。
模板：

void dfs(int u) {
  vis[u] = 1;
  for (int i = head[u]; i; i = e[i].x) {
    if (!vis[e[i].t]) {
      dfs(v);
    }
  }
}

关于剪枝

若不是模板题， 暴搜一般都会超时。 因此我们会用到剪枝的思想， 旨在减少算法的时间复杂度。
但是需要注意的是， 剪枝搜索一般 不会是题目的正解 ， 仍然可能会有部分数据TLE甚至暴零。
剪枝有几种主流思想：

  1. 可行性剪枝：
    若可以证明当前状态已经 不满足要求 ， 则可以跳过当前状态。
    if (!check()) return;
  2. 最优性剪枝：
    若当前的状态可以被证明 劣于已经得出的最优状态 ， 则跳过当前状态。
    if (step > minn) return;
  3. 奇偶剪枝：
    类似于把图进行如棋盘的黑白染色， 若起点和终点所在的格子为异色， 则走的步数一定为奇数步， 否则为偶数步， 即 起点终点的横纵坐标之和与步数的奇偶性相同 。
    if (sx + sy + ex + ey + t & 1) return;
  4. 记忆化搜索：
    相同状态下可以得出的答案一定相同， 可以通过标记数组避免重复递归：
    if (!vis[condition]) dfs(condition);

关于注意点

  1. 搜索题码量不会太小， 一定先构思好想好在下手（被人已经无数次被写错变量名的问题折磨了）
  2. 标记数组的定义和步数统计的方法一定要严谨，思路错了再大改真的好痛苦的啊！！
  3. 调试中找出的错误要记下，别再重复犯错了！
4 个赞