OI中基础入门搜索算法浅谈

东北师大附中 l1ll5

OI 搜索

写在前面的话

1. 本来是有一个既成的课件的，但是划定的讲课范围和课件里的内容不是很匹配，索性整合了一个新的。原课件也会下发，大家可以参考一下。
2. OJ上的题目和划定的讲课范围也不是很匹配，以该课件内容为主。部分超出范围的题目有剩余时间可能稍做讲解。
3. 有问题可以随时举手提问，确保每个同学至少理解了主体思想。
4. 不了解各位的水平，所以内容可能会比较基础，请各位见谅。
5. 应光老师要求，所讲题目基本来自于OJ上的那些。
6. ID：l1ll5 联系方式 QQ：2817629709 有问题可以来D我

形而上

搜索算法：按照某种策略在确定的状态空间内寻找确定的目标的算法。
状态空间：即搜索空间，由多元组 $[N,A,S,T]$ 定义。
$N$ 表示状态组成的集合。
$A$ 表示连接 $N$ 中所有状态的 "弧" 的集合。
$S$ 为 $N$ 的一个非空子集，表示起始状态的集合。
$T$ 为 $T$ 的一个非空子集，表示目的状态的集合。

如何尽快从 $S$ 出发，经由 $A$ 抵达 $T$ ，是我们搜索的目的。
一般而言，"尽快"定义为通过尽可能少的 "弧" 。

在图的遍历中，$N$ 即为点集， $A$ 即为图中的边。

通常我们在思考搜索问题时，都会考虑一个图论模型。

非常基础的内容

DFS

全称为 Depth First Search，即深度优先搜索。
顾名思义，以深度为优先级进行搜索，先尽可能搜索深度更深的节点（对于一棵树的遍历而言），当没有更深的节点未被搜索时才向上回溯。

非常基础的一个算法，也是我们最常用搜索策略，相信大家都很了解。

BFS

全称为 Breadth First Search，即是宽度优先搜索，也叫广度优先搜索。
所谓的广度优先，就是由源点出发，尽可能向四周扩展，先处理同一批扩展到的节点。
有一个显然的性质，BFS 算法找到的路径是从起点开始的 最短 合法路径。即这条路所包含的边数最小。

一个形象的比喻：洪水蔓延，或者火势蔓延。

营救

给定一个01矩阵，1为障碍，给定起点和终点，问最少走几步才能到达。

非常的基础，可以用一个队列维护，每次将向四个方向扩展到的点推入队列末尾。
由 BFS 的性质可知第一次访问到终点时即最短路径。
实现时注意记录某个节点是否被访问过，不要重复访问即可。

剪枝

在我们的搜索状态树上，很可能存在一些状态，它们已经远劣于可能的最优解，且继续搜素下去也不会使得结果更优。
这时候我们可以断言，这些状态一定不包含我们想要的答案，我们便可以使用智慧的剪刀减去这些树上的枝桠。从而做到尽可能少的遍历无用状态，优化搜索速度的目的。

大多数的剪枝策略都是不稳定的，我们无法计算它们的剪枝效果。但也正因此，很难构造具有足够强度的数据可以应对一切类型的剪枝。故合理的剪枝策略有可能在比赛中骗到额外的分数。甚至有些题目会针对性的考察对搜索的合理剪枝。所以掌握剪枝技巧是很重要的。

只要我们不停下（指思考剪枝策略），前方的道路就会不断延伸！（指获得分数）

最常见的剪枝策略即最优性剪枝，其余如可行性剪枝等常用技巧大多可被视为最优性剪枝的一种特例。

最优性剪枝

当我们在求解一个最优化问题时，通常将初始答案设为一个极值，每次搜索到终点便尝试更新该值，如取max,min等。
最优性剪枝即当我们搜索到某一状态时，目前值已经大于/小于目前答案，且接下来只会使目前答案变大/变小，此时这个状态及其衍生出的所有状态均无法作为更新答案了，于是我们可以不考虑他们。
这就是最优性剪枝。

可行性剪枝即当目前状态一定无法抵达终点，即该状态根本不可行时，剪掉这个状态及其衍生状态。

记忆化剪枝

其实这个策略更接近于DP的一个优化，大意就是对于经过的状态记录一个确定的结果，此后每次经过该状态直接调用该结果即可，在此不多叙述。

特殊的搜索策略

$A^*$

我们可以发现，最优性剪枝策略是一定正确的，但是它一个明显的问题是没有充分利用已知的信息。
这是什么意思呢，比如我们现在求解一个最小化费用问题。目前的最小费用为 $ans$ , 我们抉择是否要剪掉的状态的费用为 $now$ ，从该状态搜索到终点状态的最小费用为 $min$，考虑到我们通常不知道 $min$ 的确切值，最优性剪枝即当 $ans\leq now$ 执行。

显然，如果我们可以"加强"最优性剪枝，即将执行条件改为 $ans\leq now+min$ 时执行。我们就不会遍历到几乎所有无用状态，问题的解决便轻而易举。

因为无法确定 $min$ ，只能干脆忽略掉它吗？这是我们的突破口。

我们可以通过某种策略估计一个值 $Min$ ，这样，最优性剪枝的执行条件就变成了 $ans\leq now+Min$ 时执行。
为了保证不会剪掉有用的状态，我们必须满足 $min \leq Min$。
当 $min$ 和 $Min$ 越接近，我们的剪枝策略就越强，优化效果就越好。

这个通过估值剪枝的策略，我们称为 $A^*$ 算法

$IDS$

即 Iterative Deepening Depth-First Search ，迭代加深搜索。

通俗的说，这个搜索策略是一种 DFS 和 BFS 的结合。更明确一些：迭代加深是一种每次限制搜索深度的 深度优先搜索。

它的本质还是深度优先搜索，只不过在搜索的同时带上了一个深度 $d$ ，当达到设定的深度 $d$ 时就返回，一般用于找最优解。如果一次搜索没有找到合法的解，就让设定的深度增加 ，重新从根开始。

既然是为了找最优解，为什么不用 BFS 呢？
我们知道 BFS 的基础是一个队列，我们需要同时存储许多状态，这就使得 BFS 对空间的开销较大。迭代加深策略类似一种用 DFS 实现的 BFS 。在付出可接受的时间开销后节约了空间。
我们可以发现，每次重新从根出发时，之前的状态必须重新搜索一次，这带来了额外的时间开销。
不过我们之所以说这个时间开销是可接受的，是因为当搜索树的分支比较多时，每增加一层的搜索复杂度会出现指数级爆炸式增长，这时前面重复进行的部分所带来的复杂度几乎可以忽略，这也就是为什么迭代加深是可以近似看成 BFS 的。

$IDA^*$

综合运用 $IDS$ 和 $A^*$ 算法，就酱。

Meet-in-the-Middle

又名双向搜索，折半搜索等。
具体思想是搜索时从两侧同时出发，相遇时统计答案。

一个例子：

$n$ 件物品 ，第 $i$ 件物品的重量是 $a_i$ ，问选择重量不超过 $W$ 的物品的方案数。

$n\leq 40 , a_i,W \leq 10^9$

直接爆搜是否选择是 $O(2^n)$ 的，无法接受。
把所有物品分为前一半和后一半，分别搜索出所有结果，排序。
双指针统计答案即可。 复杂度 $O(n2^{\frac {n}{2}})$
优化很明显。

如果多一维限制怎么办，即物品多一个价格，总价格不能低于 $V$

很简单，用一个数据结构维护即可（如树状数组）

练习

NOIP2015斗地主

题目大意：给你一副牌，问最少打几次能全打出去。

首先一个容易发现的特性是如果不考虑顺子，出牌方案就与牌的大小无关了，只需要记录单张，对子，三张和四张以及王的数量(带对子不能带双王)，通过dp或记忆化搜索求出当前状态最小出牌张数即可。
先把所有顺子的出发dfs一下即可。

显然可以应用最优性剪枝：即如果已经搜索过一个只需要 $ans$ 次就可以打出的方案，那么如果现在已经出了 $ans-1$ 次都没有打完牌，那么就没有必要搜下去了，剪掉即可。

埃及分数

在古埃及，人们使用单位分数的和(形如 $\frac {1}{a}$的, a是自然数)表示一切有理数。 如：$\frac {2}{3}=\frac {1}{2}+\frac {1}{6}$，但不允许 $\frac {2}{3}=\frac {1}{3}+\frac {1}{3}$，因为加数中有相同的。 对于一个分数 $\frac {a}{b}$，表示方法有很多种，但是哪种最好呢？ 首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。 如：$\frac {19}{45}=\frac {1}{3}+\frac {1}{12}+\frac {1}{180}$
$\frac {19}{45}=\frac {1}{3}+\frac {1}{15}+\frac {1}{45}$
$\frac {19}{45}=\frac {1}{4}+\frac {1}{6}+\frac {1}{180}$
$\frac {19}{45}=\frac {1}{5}+\frac {1}{6}+\frac {1}{18}$
最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。给出$a,b (0 < a <b<1000)$ ，编程计算最好的表达方式。

想到最大的分母最小还要层数尽可能的少，那么我们发现广搜好像可以解决这个问题，但是仔细一想，如果单单限制层数的话，状态数量过于多，广搜需要很大的空间来存储状态，所以这道题并不适合广搜。
深搜的话我们可以用一些剪枝，但是我们还是没有办法判断什么时候停止搜索，因为小的数可能无限叠加。
怎么办呢？
迭代加深搜索可以综合深搜和广搜，解决这个问题！

我们如果给深搜规定一个层数限制的话，如果当前枚举到的分数乘以剩下层数还比剩下的分数要小的话，那么这个状态就可以跳出来了！
这样我们的搜索就不会无限进行下去。
我们从1开始枚举层数，一个一个搜，第一次搜到的可行解就是答案。

NOI 2001 方程的解数

直接搜索是 $150^6$ 的，所以很明显的 Meet-in-the-Middle 思路。
hash存储前一半的值，查询时直接查询相反数的个数累计答案。

The Rotation Game

给出这样一个东西，每次可以横着或竖着沿一个方向拽动一条，问最少几次操作可以使中间的八个格数字相同。

最优化问题，且难以直接搜索，考虑迭代加深搜索。
用操作数作为深度限制，但是仅仅这样还是过不了的。
考虑利用 $A^*$ 继续剪枝。

观察到题目的特点：每次移动最多只能增加中间格子中的一个数字。即每次移动都是移出一个数字再移入一个数字，那么如果中间 $8$ 个格子中最多的数字有n个，那么一定要至少 $8-n$ 次操作才可能到达目标状态。
加上这个剪枝后的 $IDA^*$ 策略就能过了。

K短路

一个很经典的 $A^*$ 问题，描述如下：

一个 $n$ 点 , $m$ 边的有向图，边有边权，给出起点和终点，求起点到终点的第K短路长度。

一个朴素的想法是按照当前距离为关键字，按照从小到大的顺序搜索，即从已经走过的距离最小的状态开始扩展状态。这样就可以保证第一次搜索到终止节点时的路一定是最短路，以后每次访问终点时的距离一定是不递减的。
这样访问到 K 次即可。

但是有一个问题，前面只走了几条路的方案因为权值很小，我们从这样的状态上扩张出了大量的无用状态，导致整个程序的时间复杂度变成了指数级。

如何解决呢？ 利用 $A^*$ 的思想优化即可。

大家想想如何选择恰当的估价函数？

只需求出目前状态到终点的最短路即可，具体实现即边反向建图的单源最短路。

需要注意的是，这么做的复杂度是无法保证的，当 $n,k$ 较大时可以轻松卡掉，有想法的同学可以思考一下怎么卡。

真正的 K 短路算法可以在 $O(nlog_n + m + klog_k)$ 的复杂度内解决该问题。具体做法需要选手掌握可持久化数据结构，且有一定难度，在此不提及。
有意思考的同学可以自行上网搜索或者联系我提供学习资料。

写在后面的话

到这里规定的内容就基本结束了，搜索部分我想不到太多例子，如果到这里还有较充足的时间，将视情况选讲下述部分内容。若未讲授则可作为课后习题。

[SCOI2005] 骑士精神
[Tjoi2014] 拼图
[HNOI2002] 彩票

随机化算法与实战技巧