本文中的链接有的是题解有的是题目链接，已经搞混了...
一.DFS(深度优先搜索)
过于水略过。
二.BFS(广度优先搜索)
同上。
三.记忆化
记忆化搜索，就是我们的状态会重复利用，为了防止状态的重复计算耗费不必要的时间，我们可以把这个状态的结果记录下来，然后查询表中的结果就行了。
一般来所，记忆化搜索是和DP等价的。如果递推的DP不好写，可以考虑用记忆化搜索实现，但是因为是递归，所以常数略大。记忆化搜索有明显的优点，就是可以不用考虑状态在哪里终止，只用知道状态会终止就行了。
四.搜索剪枝
这是一门博大精深的学问， 通常用于解决搜索时间复杂度过高的问题。
原理就是在庞大的搜索树上剪去不可能对答案产生贡献的枝条。
搜索+剪枝的时间复杂度是$O(玄学)$，因为我们只能通过经验来估测剪枝效果。
所以考试打暴力的时候一定要多写剪枝，尤其是奇形怪状的玄学剪枝。
几道例题:
贪心出牌，出完顺子枚举出其他的尽可能出的多的牌的组合。
加上最优化剪枝，如果现在出了$ans-1$次没有出完就剪枝。
我当时用了$lowbit$优化常数，然后把整个棋盘分成上下两部分，如果上半部分空位比下半部分多，就从下半部开始搜索。这样就水过去了。
其实也可以按格搜索，优先搜可填的少的格。
还有$A^*$剪枝，如果剩下的格子都填9还比$ans$小的话就剪枝。
通常使用的剪枝技巧
1.最优性剪枝。
2.$A^*$剪枝。
3.改变搜索顺序，优先搜索扩展出的状态比较少的状态。
五.双向广搜
双向广搜就是从起点和终点开始搜索，每次各搜一层，如果相遇，则得出答案。
双向广搜可以使搜索树减少一半以上，大大优化了时间复杂度。
-
两个方向交替扩展
-
选择结点个数较少的那个方向先扩展．
1.poj3523 The Morning after Halloween
其实这题直接$bfs$就可过，但是为了追求效率，用双向广搜甚至可以减少一半的时间。
六.meet in the middle
这个和双向搜索有差别，思路是把问题折半，然后合并，减少一半的搜索层数。
经典例题NOI2001方程的解数
先搜前3个解，把结果用hash表存一下，然后搜后3个解，在hash表中查询个数。
这题太恶心了，用mapT飞，用hash表Mle，大力取模WA。
无药可救...
#include <iostream> #include <cstdio> #include <queue> #include <cstring> #include <map> #include <algorithm> #include <cstdlib> #include <cmath> using namespace std; #define reg register inline int read() { int res=0;char ch=getchar();bool fu=0; while(!isdigit(ch))fu|=(ch=='-'), ch=getchar(); while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar(); return fu?-res:res; } int n, m; int k[8], p[8]; int mi[155][155]; int ans; map <int, int> mp; void dfs1(int dep, int sum) { if (dep > n / 2) { mp[sum]++; return ; } for (reg int i = 1 ; i <= m ; i ++) dfs1(dep + 1, sum + k[dep] * mi[i][p[dep]]); } void dfs2(int dep, int sum) { if (dep > n) { ans += mp[-sum]; return ; } for (reg int i = 1 ; i <= m ; i ++) dfs2(dep + 1, sum + k[dep] * mi[i][p[dep]]); } int main() { n = read(), m = read(); for (reg int i = 1 ; i <= n ; i ++) k[i] = read(), p[i] = read(); for (reg int i = 0 ; i <= m ; i ++) { mi[i][0] = 1; for (reg int j = 1 ; j <= m ; j ++) mi[i][j] = mi[i][j - 1] * i; } dfs1(1, 0); dfs2(n / 2 + 1, 0); cout << ans << endl; return 0; }
七.迭代加深搜索(IDDFS)
某些题状态无限，bfs无法承受空间复杂度，可以限制dfs搜索的深度。
每次增加深度限制，每次可能对之前搜过的状态多次计算，但是由于状态每一层都扩展的十分多，所以相比于扩展一层，重复上面的状态的复杂度还是可以接受的。
可以逐步增加答案的分数的个数，然后可以限制住状态的无限扩展...其实我不会233（逃.
2.poj2248 Addition Chains (此题解访问人数已经突破100人啦！！)
和上面一样逐步扩展答案的个数，然后再加上一些十分有用的剪枝，才能A掉这题，详情见链接。
八.迭代加深A*(IDA*)
普通迭代加深搜索加入A*剪枝。
估价函数的一小点变动可能导致时间上的很大的差别，详情点进链接看看。
2.poj2286The Rotation Game
估价函数为8-中间出现次数最多的数字的个数。
九.随机化
过于玄学，略过。