搜索从入门到入土
2022/10/1听清北，被暴捶了，听不懂，于是来补搜索……QwQ
本来该开始听的时候还觉得挺简单的，但是一到讲题的时候，就很突然啊¿😇😇😇¿，呜呜呜懵逼了¿
于是，有了这篇狗屌学习笔记🤕🤕🤕
入门
==定义==DFS
- 深度优先搜索算法（DFS）
BFS
- 广度优先搜索算法（缩写为BFS）
看了上面的定义我们知道搜索(尤其DFS)多是来两个或多个选择决策的 结合记忆化搜索加各种剪枝优化，还有各种搜索模式，启发式，双向搜索……总之搜索是很有趣的很博大精深的。
入门级实现
DFS一般用递归实现。
1.传参
首先，写DFS的时候我们要先把题目看清（这样好知道我们应该向函数里面传什么值）： - 所求的值 - 当前所在的状态 - 参数，会对下一轮递归产生影响的参数
在这里给道好题(考信息提取&传参数的P1731 [NOI1999] 生日蛋糕
//点链接，题面等会加
2.边界&循环主体
先上伪代码3： 1
2
3
4
5
6
7
8
9
10
11
12void dfs(){
/*1.递归边界
常见的递归边界有：
01.坐标越界
02.搜索到了极限
03.出现重复搜索，或者不是最优的搜索
*/
/*
2.递归调用的主体，进行决策选择和状态转移，这里一般会用for循环，或者是直接调用两个dfs即可。
*/
}
以上伪代码已经说列的比较全了 上题其实就是很适合来练手这个就很适合(简直就是典中典啊)
等下我先来给大家切一个哈…… （emmm………………）看来是切失败了QwQ
（误）
再进一步
优化剪枝
切上题的同学们可能发现了，因为暴搜的复杂度过高，想要过这道题还需要优化，这个优化就叫做剪枝（（（当然优化不止这一种
最常用的剪枝有三种，记忆化搜索、最优性剪枝、可行性剪枝 :
| 记忆化搜索 | 最优性剪枝 | 可行性剪枝 |
|---|---|---|
| 开一个vis[]来记录重复的结果 | 比之前的最优值要差的话，主动放弃递归 | 与题意不符的停止递归 你也可以理解为把不能到达终止节点的剪掉 |
最优性剪枝: 如果$ f(P)+(p) >
ans$,就回溯(其中f(p)为当前答案,exp(p)为期望答案(一般设置为零,毕竟难算QwQ))
其他优化方式 :
- 排除等效冗余
- 启发式
- 迭代加深
- 随机调整
- 状态表示
- 双向搜索
- etc. (博大精深啊……
虽然完全用不到的的说
虽然优化的种类千千万,但是并不要求我们都要掌握,考场上考的也很有限,去做有把握的优化。 就像 剪枝 也是有平衡点的,过多的低效的剪枝反而增加运算量。要是减错了那更加得不偿失了,尤其是考场更要慎之又慎!
高校进阶🤡
题单(大综合):
| 题目列表 | 题目连接 | 推荐程度 | 理由&备注 |
|---|---|---|---|
| 棋盘问题 | POJ | ✨✨✨ | 很好的入门题 |
| NOI1999生日蛋糕 | luogu | ✨✨✨✨ | 典中典中典·必刷 |
| Eight(八数码) | POJ
|
✨✨✨ | 必刷·思维·打表反向搜 |
| 小木棍 | luogu | ✨✨✨ | 多种剪枝·排除等效冗余 |
提示: 开始打不出正解剪枝也不要紧,先把暴力打出来
你就想小木棍就算你只打了(纯)暴力,也能那个20分。总之不要害怕,慢慢来……
搜索的结合
这两天做到一道题: 邮票采集,是一道很好的题 可以用这道题来练习DP和搜索的结合！(注意关系的传递)