【学习笔记】搜索
1. 爆搜
显然，就是暴力算法。（当然也是所有 OIer 初学时就会了解到的东西）
2. 剪枝
（1）最优性剪枝
定义很简单，也很常用。就是指的如果当前答案比我们当前的最优解更劣，且不会变得更优，那么就是不行的。
（2）可行性剪枝（上下界剪枝）
如题，如果说，当前状态不合题意，那么此时这个答案就“废”了，我们就不必搜索。
（3）记忆化
如果我们要搜索答案，并且这个答案唯一，那么我们可以把这个答案记录下来，然后以后每次访问直接得到这个答案即可。
（4）排除冗余状态
如果我们不需要求解，只需要遍历，那么这个答案就没必要。我们就可以打个标记，如果遍历过，那么就不再遍历。
（5）优化搜索顺序
如果说，对于某个东西，我们需要使它更优，那么，我们可以按照从优到劣的顺序来搜索，这样第一次搜到的答案就是最优的，就不需要继续搜索。
（6）随机化贪心
如果搜索状态过多，并且你想不到除了爆搜之外的其他解法，但是暴力过不了，那么我们可以确定评测机可以搜索的次数，如果超过了这个次数，那就不搜了，这样就可以用正确性保证时间。
如果某个点遍历得太多，那么我们也可以确定每个点的遍历次数来求出答案，时间复杂度是线性。
3.双向搜索
众所周知，搜索的复杂度是指数级的，当然指的是理论复杂度，实际会跑不满稍微快一点。
所以，在已知初始状态和最终状态的情况下，我们可以同时从这两个状态开始搜索，那么搜索树的规模应该会减半，就可以把时间复杂度的指数优化到原来的一半。
4.广搜变形
首先，我们要了解一下广搜的队列实现原理：保证队列具有单调性，这样第一次查找到的答案就是最优解（其实就是运用了最优性剪枝）。
但是，如果边权不唯一，插入到队尾的数就没有了单调性，我们分两种情况讨论：
（1）0/1 边权
如果此时队列中的队首答案如果是
（2）所有边权
那么我们不只有两个边权了，为了保证单调性，我们可以实现一个满足单调性的数据结构——优先队列（priority_queue）。注意，这里会使时间复杂度多了一个
还需提醒的是，这里不能使用单调队列，因为它会删除一些状态，可能会把一些有解的情况判定成无解。
5.迭代加深
有一类特殊的搜索：求答案的最小值。
这里存在一个最优性剪枝，但是不能优化整体的复杂度，此时可以考虑迭代加深。
首先，我们要理解这个词的意思：深，就是指搜索深度，也就是答案；迭代加，就是在使搜索深度越来越大。
也就是说，我们可以控制一个深度，每次搜索，如果有解，那么这个深度就是最小深度，也就是最优解。
注意常数问题，所以说剪枝不可减免。
6.A*
A* 是一个非常奇妙的算法，它的主旨在于