能力提升综合题单Part3 搜索

## Part 3 搜索 > 搜索其实就是高级的枚举，很多题目都可以用搜索完成。就算不能，搜索也是骗分神器。 ### Part 3.1 深度优先搜索 > 深度优先搜索（DFS），即按照深度优先的顺序搜索的算法。 > > 深度优先搜索一般使用栈来实现。 - [P1219 八皇后](https://www.luogu.com.cn/problem/P1219) - [P1019 单词接龙](https://www.luogu.com.cn/problem/P1019) - [P5194 [USACO05DEC]Scales](https://www.luogu.com.cn/problem/P5194) - [P5440 【XR-2】奇迹](https://www.luogu.com.cn/problem/P5440) - [P1378 油滴扩展](https://www.luogu.com.cn/problem/P1378) ### Part 3.2 广度优先搜索 > 广度优先搜索（BFS），即优先扩展浅层节点，逐渐深入的搜索算法。 > > 广度优先搜索一般使用队列来实现。 - [P1162 填涂颜色](https://www.luogu.com.cn/problem/P1162) - [P1443 马的遍历](https://www.luogu.com.cn/problem/P1443) - [P3956 棋盘](https://www.luogu.com.cn/problem/P3956) - [P1032 字串变换](https://www.luogu.com.cn/problem/P1032) - [P1126 机器人搬重物](https://www.luogu.com.cn/problem/P1126) ### Part 3.3 记忆化搜索 > 通过将已经遍历的状态记录下来，从而减少重复的搜索量，这就是记忆化搜索。 > > 动态规划的时候，记忆化搜索也是一种高效简洁的实现方式。 - [P1514 引水入城](https://www.luogu.com.cn/problem/P1514) - [P1535 游荡的奶牛](https://www.luogu.com.cn/problem/P1535) - [P1434 [SHOI2002]滑雪](https://www.luogu.com.cn/problem/P1434) - [P3953 逛公园](https://www.luogu.com.cn/problem/P3953) ### Part 3.4 搜索的剪枝 > 对于一些不必要搜索的部分，我们可以避免访问这些状态，从而提高搜索效率。 - [P1120 小木棍 ［数据加强版］](https://www.luogu.com.cn/problem/P1120) - [P1312 Mayan游戏](https://www.luogu.com.cn/problem/P1312) - [P1074 靶形数独](https://www.luogu.com.cn/problem/P1074) ### Part 3.5 双向搜索 > 在搜索时，如果能从初态和终态出发，同时进行搜索，就可以减小搜索树的规模，提高时间效率。 - [P3067 [USACO12OPEN]Balanced Cow Subsets](https://www.luogu.com.cn/problem/P3067) - [P4799 [CEOI2015 Day2]世界冰球锦标赛](https://www.luogu.com.cn/problem/P4799) - [P5195 [USACO05DEC]Knights of Ni](https://www.luogu.com.cn/problem/P5195) ### Part 3.6 A\* > 在 BFS 中，如果能设计一个合理的估价函数，就可以更快扩展到最优解。这就是 A\*算法。 - [P1379 八数码难题](https://www.luogu.com.cn/problem/P1379) ### Part 3.7 IDA\* > 像 BFS 那样，每次只扩展一层节点，却采用 DFS 方式来遍历搜索树，这就是迭代加深搜索。 > > 再加上一个估价函数来减小搜索量，就是 IDA\*了。 - [P2324 [SCOI2005]骑士精神](https://www.luogu.com.cn/problem/P2324) - [P2534 [AHOI2012]铁盘整理](https://www.luogu.com.cn/problem/P2534) ### Part 3.8 DLX > 算法 X 是通过回溯法求解精确覆盖问题的算法，而删除列这一操作可以使用舞蹈链加速。 - [P4929 【模板】舞蹈链（DLX）](https://www.luogu.com.cn/problem/P4929) - [P4205 [NOI2005]智慧珠游戏](https://www.luogu.com.cn/problem/P4205)