搜索

• 定义

  套用一下OI wiki上的定义，搜索，也就是对状态空间进行枚举，通过穷尽所有的可能来找到最优解，或者统计合法解的个数。
  不难看出，所谓搜索，本意上就是依靠自己对题目状态转移的理解进行枚举。

• Lead-inⅠ

  既然搜索本质是暴力，那我们为什么常用搜索而不常用暴力呢？
  以全排列问题为例，对于\(n=3\)时，我们可以显然地用三重循环解决问题，那当\(n=4\)时呢？我们大可以再加一个特判写一个四重循环，那么我一直加下去，一直加到\(n=100\)呢？这时候显然无法枚举。对于这种无法用简单的思路进行枚举时，我们就可以进行搜索。
  tips：或许你也可以这么理解，对于图和树，我们并不清楚他们的结构（至少在我们写代码时并不清楚），这种情况下枚举也是无法使用的。

• DFS

  
  让我们来康康这个图，如何解释DFS的思路呢？就是一条路走到底。
  DFS的搜索过程（现场画图演示罢）。
  让我们来深究一下其原理，我们搜索每一个节点时枚举这个节点通往的所有节点，然后选取第一个进行搜索。
  也就是说DFS形成了一个FILO（先进后出）结构，也就是栈。（至少tarjan理解返祖边时应该理解过dfs是栈的概念）。

• BFS

  BFS的思路是什么呢，就是我先走我先看到的节点。
  BFS的搜索过程（同理）。
  在BFS中，我们枚举枚举这个节点通往的所有节点并将其放到缓存里。
  这样形成了应该FIFO（先进先出），也就是队列。
  tips：DFS和BFS的代码实现不难，这里就不放了，OI wiki自取。

• 两者的区别

  DFS是一条路走到黑，BFS这是雨露均沾。
  显然，DFS可以更快地找到单个解（但是可以进行大量剪枝），BFS可以更快地找到全部解（最优解）。

• Lend-inⅡ

  按理说，对于大部分问题，其逻辑都可以转化为一个DAG。
  那么，对于一个有\(n\)个点，\(m\)条边的DAG，其复杂度达到了令人感叹的\(O(n^m)\)。
  这显然是十分夸张的，所以我们需要优化搜索。

• 不换汤也不换药的优化

  字面意思，这里是一些不换汤也不换药的优化。
  这东西可能有个更好的名字，叫防卡常技巧。
  这里就不细讲了，因为跟搜索算法的思路无关（但是你平时要是写搜索很难不碰见它），这是传送门。

• 换汤不换药的优化

  简单来讲，就是你不用重构你dfs或者bfs函数的优化。
  • 最优性剪枝
    如果当前状态下不可能出现最优解时，进行剪枝。（往往出现于当前的最优解比整体最优解劣时）
    一般的实现方式是考虑当前情况一直进行最优决策玉当前最优解的对比，剪去重复的情况或者推算出上下界。
  • 可行性优化
    如果当前状况违法时，剪枝。
  • 二分查找
    如果搜索函数中出现枚举找单点的代码，使用二分查找来优化，能优化一个\(log\)的复杂度。
  • 信仰剪枝
    如果执行时间逼近时限了，直接输出当前的最优解。（并不正确，只能让你的TLE多了几分AC的概率）

• 换汤换药的优化

• 折半搜索Meet in the middle

  将一整个搜索流程分为两部分，从初始状态和末状态同时开始搜索，两边相遇即为解。
  一般折半搜索可以将时间复杂度从\(O(n^m)\)降到\(O(n^{\frac{m}{2}})\).
  思路较好理解，这里就略过。

• 记忆化搜索

  顾名思义，将每个情况下的对应答案记录下来进行大量剪枝的搜索方式。
  相当玄妙，因为改完记忆化之后爆搜代码会变得很像DP的代码。
  同时，当你找到状态转移方程而不知道如何进行枚举时，也可以写记忆化搜索。
  记忆化搜索有两种方式：
  • 通过状态转移方程来写出记忆化搜索的代码
    好的讲解传送门。
  • 对暴搜的代码进行修改来写出记忆化搜索的代码
    现场讲罢。