搜索：
一种基础的算法。
考察常见于NOIP
但是高级的搜索算法可能还会在省选出现。
50%以上的暴力都可以用搜索直接枚举来写。
但是，当数据规模不是很大的时候，搜索也可能成为正解。
（比如剪枝PK状压dp）
在搜索的基础上，可以衍生出最短路，而dp本质上，也是搜索的剪枝。
一、基础搜索算法
DFS：
最基本的搜索。用递归实现。
顾名思义，深度优先搜索的特点就是从一个位置直接搜下去，直到搜到末尾或者中途return
先扩展出深度。
dfs图中遍历的状态会形成一棵搜索树。（如果搜成了一般图，那就说明剪枝不到位了）
一般认为，dfs的复杂度就是“搜索树的大小 乘上 每一个状态 下的复杂度”
自我感觉，dfs的更多时候，用途不在于搜索，而在于对结构的遍历。
用途：
1.50%的暴力，2^n,n!的枚举。
2.容斥。
3.遍历。
dfs遍历一棵树（可能爆栈），（求dfs序，树形dp等）
因为dfs会搜完一棵子树再回溯，所以利用这个性质，dfn，dfn2，以及tarjan都可以成立。
利用递归的性质，从儿子回溯后，对这一层的检查与更新，也是经常用到的。
4.配合BFS，寻找联通块
BFS：
最基本的遍历图的方法。一般用于搜索。
顾名思义，广度优先搜索，就是先扩展整个图的层数。
会从一个起点（多个起点）开始，不断把周围一层遍历，
即，遍历的状态的层数总是连续的一段。
用途：
1.边权为1的最短路。
这个其实是值得注意的，BFS的最短路是O(n+m)的，是所有的最短路中最快的。（有时那SPFA或者dij跑边权为1的最短路，就浪费了~~~）
当然，必须边权是1。
2.分层图：
利用BFS的分层图的性质，可以有层次地遍历一个结构。
AC自动机的fail树的构建：由于分层图，而fail[i]一定长度比i小，即层的编号小，所以必然已经遍历，没有后效性。
DINIC算法，在分层图上跑增广路。可以保证复杂度。
问题：
1.DFS的劣势明显，会进入一个搜索子树，遍历完这棵搜索树之后才会回溯。
如果这棵搜索树对答案不能产生影响，那么会大大降低效率。
更糟糕的，如果一棵子树非常庞大（指数级增长），则直接TLE地飞起。
2.BFS的劣势明显，由于要广度优先搜索，所以会遍历完整个一层才会遍历下一层。
如果一层很多，也会爆炸。
而且，必须记录所有当前在队列里状态的状态信息。
如果状态增多，搜索树较大，空间和时间都没有办法保证。
对于这些bug，机智的人们创建了新的优化方法。
二、剪枝
剪枝，顾名思义，就是在dfs或者bfs中，把一棵搜索子树直接砍去，不进行遍历。
来达到复杂度的保证。
其实剪枝范围可以很广，A*，IDA*，甚至dp，我认为都可以叫剪枝。
而且剪枝也不一定用于搜索。
当然，一般情况下的剪枝，就是指用dfs搜索中的剪枝。
1.最优性剪枝。
最常见。最基本的，对于单增取min，单减取max，都可以稳定减去一些复杂度。
配合估价函数，对未来最少花费进行预估，通常可以大大增加效率。
2.可行性剪枝。
对于状态搜索下去是否能合法的剪枝。
剪枝最重要的还是分析题目的性质。
例题：NOIP2004 虫食算
原文：https://www.cnblogs.com/Miracevin/p/9780027.html