集训2023/03/19+03/26：搜索优化

· · 个人记录

一、剪枝

（理论上）非常简单，就是在搜索时直接排除不可能出现或不是最优的情况，从而提高程序执行效率。

1.1 拼接正方形

是搜索无疑了，先从简单的想起。

记 S = a_1 + a_2 + \cdots + a_m。

如果用朴素搜索的话，就是枚举每一根木棒在哪一条边里，时间复杂度有 O(4^m)，显然会超时。

于是考虑剪枝。由于题目的要求是拼接正方形，所以每一条边的长度都会等于 \frac{S}{4}，那么就可以剪掉某一条边大于 \frac{S}{4} 的情况，因为再往下搜索时，这条边不会再变短了。

1.2 P1559 运动员最佳匹配问题

首先想到暴力枚举每一个男的配哪一个女的，显然超时。

考虑优化。假设有两男 a, b 和两女 c, d，记 (a, c), (b, d) 配对时的贡献为 V_1，(a, d), (b, c) 配对时的贡献为 V_2。那么我们只需要考虑其中的一种情况：

至于怎么排除所有应该排除的配对：两两枚举，反正 1 \le n \le 20。

二、双端队列广搜

适用于有部分优先级的问题，比如说优先搜索带有某种属性的元素。

2.1 P4667 [BalticOI 2011 Day1]Switch the Lamp On

如果一组顶点直接有电线直连，则设这两个点之间的边权为 0，否则设为 1，于是这就变成了一个最短路问题。

但是普通广搜无法解决这个问题，因为它要求无边权。

思考普通广搜为什么要求无边权。我们发现，这是为了保证搜到每一个点时都是目前的最短路状态，从而保证算法的正确性。

而现在我们只有两种情况，就可以用双端队列。

三、双向搜索

3.1 最接近目标值的子序列和

暴搜 O(2^n) 必定超时，但是两个 O(2^{\frac{n}{2}}) 似乎可以（2 \times 2^{20} = 2^{21} = 2097152）。

于是我们想到，可以分别搜出前一半和后一半的结果，再把他们总结起来，得到整个问题的结果，思路有点像分治。

具体的实现方法，就是先把两边都搜完，最后拿个双指针扫一遍找最接近 k 的，完事。

3.2 迷宫最短路

双向广搜。

就像多起点一样，开始时把起点和终点都加入队列。

由于一个是从起点搜，一个是从终点搜，那么如果两边搜到了同一个点，就代表着找到最短路了。由于两端都在做正常广搜，正确性显然。

注意特判起点与终点重合的情况。

3.3 加快速度的原理

双向广搜，为什么可以加快程序速度？

我们其实可以把普通广搜想象成从起点不断增加半径往外画圆，直到画到终点为止：

而双向广搜，就是从起点和终点同时画圆，直到两边的圆出现交点为止：

这样，就只需要搜一半的距离（或者说 n \gets \frac{n}{2}），这对于路径搜索的问题意味着复杂度开了个根号。

四、启发式搜索

不影响算法正确性的剪枝就是启发式剪枝，用了启发式剪枝的搜索就是启发式搜索。

4.1 启发式剪枝 - P1120 小木棍

全排列枚举，但是加了优化。

  1. 原始的木棍由于长度相等，每根的长度都是长度之和的因数；
  2. 先选长的木棍，因为短木棍组合更灵活，而长木棍更多是“凑”长度的作用；
  3. 避免重复，令组中木棍长度单调递减，所有组的第一根木棍长度单调递减；
  4. 如果选了一根木棍，发现不行，那么就不要再选长度相等的木棍了，浪费时间；
  5. 如果凑数时剩余的长度刚好对应一根木棍，那就选它了，因为与其用几根较小的不如用长点的木棍，更灵活。

4.2 A*

如果是我们找最短路之类的枚举（至少暴力方法是枚举）问题时，我们会优先枚举更像是答案（或者看起来更像）的情况。

可惜计算机并不知道什么叫做“更像答案”，所以计算机干不了这事。

但是，如果我们能让计算机理解“更像答案”是什么，我们是不是就可以让计算机在处理问题的时候像我们一样“思考”了呢？

是的，我们确实可以。

我们建立一个函数 f(x) 作为情况 x 的估值函数（注意不是咕值），f(x) 的值越小，就代表着情况 x 越可能是答案。

令 f(x) = g(x) + h(x)，其中 g(x) 为已经搜到的终点为 x 时的答案，h(x) 为估计从 x 走到终点的最短长度。

比如说，如果 h(x) 是 x 到终点的曼哈顿距离，那计算机就会优先向终点所在的方向去搜索。

4.3 A* 的正确性

广搜的正确性是因为每次到达一个点时，如果存在更短的路线那就不会再次搜到了。但是，A* 的估值函数已经把广搜的正确性破坏的一点不剩。

令 d(x, y) 为 x 到 y 的实际最短路，则 h(x) \le d(x, ed)（显然）。

于是有 f(x) = g(x) + h(x) \le g(x) + d(x, ed)（即，估值小于等于实际长度）。

因为我们会向 f(x) 更小的位置搜，于是 f(ed) \le f(x) \le g(x) + d(x, ed)。

由于 ed 是终点，所以 f(ed) = g(ed)，于是 f(ed) 即为到 ed 的最短距离。

综上，只要满足 h(x) \le d(x, ed)，即可保证算法正确性。

4.4 A* - 迷宫最短路

将 h(x) 设为 x 到 ed 的距离，然后跑 A*。

五、迭代加深

我们的两种搜索方法（深搜与广搜），是各有优缺点的：

\small_\texttt{对比项}\\small^\texttt{算法} 深搜 广搜
时间 明显慢，因为要搜到底 快，因为是“广度”
空间 少，只存当前状态 明显多，要存搜到的每个状态

一般来说，那些没有“深度”的定义（或者很模糊）的问题，是不能用深搜解决的（因为会一直搜下去最后死递归）。但是，如果题目把广搜也给卡掉了（卡空间），那我们难道就做不了了吗？

显然是错误的，迭代加深搜索就专门解决这种问题。

我们人为限定一个深度 d，然后让深搜每次最多搜到深度 d，如果没有发现答案，那么就增加 d 的值，直到发现答案为止。

复杂度为 O(\sum\limits_{i=1}^{d}2^i)，可以近似的认为是 O(2^d)，和广搜相当。

5.1 P1763 埃及分数

枚举所需要的分数个数，然后往下搜。

有一个小优化，就是在往下搜分母的时候让它单调递减。