Creator's World

一些更加高级的搜索知识。

一、剪枝

1. 简介

剪枝是在普通的 DFS 上对于不需要计算的值（要么已经计算了，要么不用计算）就不去搜索。

2. 种类

• 记忆化搜索

• 最优性剪枝

• 可行性剪枝

3. 方法

• 极端法

  考虑极端情况，若最极端（理想）的情况都无法满足，那么肯定无法满足。

• 数学法

  建立不等式，确定上下界。

4. 例题

P1731 [NOI1999] 生日蛋糕

运用了最优性剪枝：用极端法，若剩下的蛋糕都放最小的，还是超过了，那么直接 return、可行性剪枝：还是极端法，若剩下的蛋糕都放最大的，还是没到，直接 return。

[P1074 [NOIP2009 提高组] 靶形数独](https://www.luogu.com.cn/problem/P1074

)

二、折半搜索（meet-in-the-middle）

1. 简介

折半搜索通过将整个搜索的过程分为两个部分，然后两个部分依次搜索，最后将两次搜索得到的答案序列合并，得到最终答案。

搜索的时间复杂度往往是指数级的，而折半搜索可以将指数除以 $2$，大大优化时间复杂度。例如一道题爆搜时间复杂度为 $O(2^n)$，那么折半搜索时间复杂度就为 $O(2^{n/2} + \text{合并操作的时间复杂度})$。

2. 条件

并不是什么搜索都可以折半的，需要满足以下条件。

• 一般需要知道总共走几步。

• 结束状态是什么。

• 前后决策互不影响。

3. 例题

P4799 [CEOI2015 Day2]世界冰球锦标赛

首先想到背包，一看数据范围 $M\leq 10^{18}$，显然过不了。而最简单的搜索时间复杂度为 $2^{40}$，也无法通过。

那么我们考虑是否可以折半搜索。我们知道要走几步（即 $N$）、知道结束状态是什么（总和不超过 $M$）、前后决策互不影响（前面选了哪几张和后面没有关系），那么我们可以折半搜索。

具体操作时，我们将整个序列分为两个序列，再依次搜索。对于第一次搜索的序列，我们记下搜索的值，存进 vector 中，对 vector 排序，然后在第二次搜索时二分查找一下统计答案。

P2962 [USACO09NOV]Lights G

三、A*

1. 简介

A* 搜索算法是对 BFS 的改进。定义起点 $s$，终点 $t$，从起点（初始状态）开始的距离函数 $g(x)$，到终点（最终状态）的距离函数 $h(x)$，以及每个点的估价函数 $f(x)=g(x)+h(x)$。

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

2. 例题

P1379 八数码难题

这道题有终点、有起点，估价函数 $h$ 可以定义为不应该在这个位置的数字个数。

四、迭代加深

1. 简介

迭代加深就是在普通的 DFS 之上限制了搜索的层数，以此来达到优化时间复杂度的效果。

2. 例题

UVA529 Addition Chains

就是普通的搜索之上加了个层数限制，因为本题要求长度最短，找到答案直接输出即可。

五、IDA*

例题

P2324 [SCOI2005]骑士精神

因为本题只有黑白两种颜色的棋子，最好的情况就是把黑白棋子对换，因此估价函数就是不在自己位置的棋子的个数（但像八数码这样的就不能直接这样做）。

[UVA12558 埃及分数 Egyptian Fractions (HARD version)(https://www.luogu.com.cn/problem/UVA12558)