搜索部分简介
搜索的思想按照在状态空间中尝试的顺序分为多种。搜索看起来简单，但是往往是很多复杂的题目中必不可少的模块。
深度优先搜索 (DFS)¶
主条目： DFS（搜索）
宽度优先搜索 (BFS)¶
主条目： BFS（搜索）
双向宽度优先搜索¶
主条目： 双向广搜
从状态图上起点和终点同时开始进行宽度优先搜索，如果发现相遇了，那么可以认为是获得了可行解。
A*搜索¶
主条目： A*
IDA*搜索¶
主条目： IDA*
剪枝¶
搜索往往是在庞大的解空间中尝试获得最优解，这时候剪枝就显得十分必要了。剪枝顾名思义，是运用已有的信息，尽早地确定一种方案是否可行，如果已经知道无法获得最优解就及时退回。这样的操作对于搜索树来说，就相当于是在搜索树上剪掉一些枝杈。
剪枝思路有很多种，大多需要对于具体问题来分析，在此简要介绍几种常见的剪枝思路。
极端法¶
考虑极端情况，如果最极端（最理想）的情况都无法满足，那么肯定实际情况搜出来的结果不会更优了。
调整法¶
通过对子树的比较剪掉重复子树和明显不是最有“前途”的子树。
数学方法¶
比如在图论中借助连通分量，数论中借助模方程的分析，借助不等式的放缩来估计下界等等。
meet-in-middle¶
也称折半搜索，主要思想是分治，通过将枚举量减少到原来的一半和特殊的合并技巧以使情况数减少到原来的 sqrt，复杂度也就开了个方，折半搜索也是一个很好的优化，往往能在 OI 竞赛中获得出人意料的效果（尤其在面对数据水的时候）
所谓 meet-in-middle , 就是让 DFS 的状态在中间的时候碰面。我们知道，如果一个暴力 dfs 有 K 个转移，那么它的时间复杂度（大多数情况）是 O(K^N) 的。那我们就想，当 N 到达一定程度时，TLE 会变成必然。
例题 Luogu P2962
我们正常想，如果这道题暴力 DFS 找开关灯的状态，时间复杂度就是 O(2^{n}) , 显然超时。不过，如果我们用 meet-in-middle 的话，时间复杂度将会变为 O(2^{n/2} \times 2) 而已。 meet-in-middle 就是让我们先找一半的状态，也就是 1 到 \mathrm{mid} 的状态，再找剩下的状态就可以了。我们把前半段的状态全部存储在 map 里面，然后在找后半段的状态的时候，先判断后半段是不是都合法，就可以判断上半段有没有配对的上半段使得整段合法。
经典题目¶
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用