搜索 学习笔记

目录

1. 最基础的搜索

   1.1 bfs

   1.2 dfs

2. 双向搜索

   2.1 双向广搜

   2.2 双向宽搜

   2.3 meet in the middle

3 搜索的优化

3.1 记忆化搜索

3.2 最优性剪枝

3.3 可行性剪枝

3.4 其他方法

4. 迭代加深搜索

5. Dancing Links

6. \(\alpha - \beta\) 剪枝

7. A/IDA

正文

1. 最基础的搜索

bfs/dfs 无需多言。bfs 瓶颈在于空间，dfs 瓶颈在于递归的时间。

2. 双向搜索

2.1 双向广搜/2.2 双向宽搜

从起点或终点同时进行搜索。

对于广搜，具体地说，给每个点带上从起点/终点转移而来的标记，同时丢进队列里面即可。

对于深搜，感觉好像没啥用。

2.3 meet in the middle

通常发现一个复杂度刚好是 \(O(a^b)\) 时，就可以把搜索分成两半合并，优化为 \(O(a^\frac b 2)\)。

例题1：

P2962

先做一半然后丢进 map，然后在做后一半的时候对前一半的方案进行计数。复杂度 \(O(2^\frac n 2)\)。

例题2：

一个 \(n\times n\) 的网格图，点有点权 \(\in(0,1)\)，求从地图左上走到地图右下经过的路径是回文串的方案数。\(n\le 20\)。

显然先从左上搜到 \((x,n-x)\)，然后从终点搜过去就行了。\(O(2^\frac n2 n)\)。

3. 搜索的优化

3.1 记忆化搜索

具体的，如果函数为 dfs(i,j,k) ，那么可以设 \(f_{i,j,k}\) 表示 \(dfs(i,j,k)\) 的答案，每次如果遍历过直接取答案，大大优化复杂度。

3.2 最优性剪枝

如果当前答案加上剩余的最优解（不考虑合法情况）都小于当前的最优解，则不继续搜索。

3.3 可行性剪枝

如果已经不合法，不进行搜索。

3.4 其他方法

调整法/讨论极端情况/数学方法。或许可以考虑改变搜索的状态。

4. 迭代加深搜索

限制迭代层数。但可能搜不出最优解。

5. Dancing Links

咕。

6. \(\alpha - \beta\) 剪枝

咕。在 ACM 中感觉很常见啊。

7. A*/IDA*

引自 oi-wiki 。

定义起点 s，终点 t，从起点（初始状态）开始的距离函数 \(g(x)\)，到终点（最终状态）的距离函数 \(h(x),h^{\ast}(x)\)，以及每个点的估价函数 \(f(x)=g(x)+h(x)\)。

A* 算法每次从优先队列中取出一个 f 最小的元素，然后更新相邻的状态。

如果 \(h\leq h*\)，则 A* 算法能找到最优解。

上述条件下，如果 h 满足三角形不等式，则 A* 算法不会将重复结点加入队列。

`IDA* 即为采用迭代加深的 A* 算法。