为什么要剪枝？
与bfs相比，dfs不要求深度最小，而往往要遍历所有状态（如找到最优解、统计解个数），而在搜索时，状态数往往极多，故我们需要用剪枝优化来减少遍历的状态数来优化搜索，和bfs中去除重复状态一个道理
如何剪枝？
常见的两种思路：
1.可行性剪枝
如搜索路径中的01可行性判断、统计解个数时，取极端情况（极大或极小）来判断能否达到目标状态
eg:叠蛋糕问题、方程解个数问题
2.最优化剪枝
即提前判断当前状态能否遍历到比当前最优解还优的状态，也是取极端情况
3.二分剪枝
eg:给定n个节点的有向有环图，求长度为n的路径，满足其权值最接近x
（n≤10）
如果采用dfs，则复杂度为n的n次方，过大，故我们先搜索长度为n/2的路径权值和并存储，复杂度为n的n/2次方，存储f[i][j]为以i为终点，第j小的权值和，再搜索一次以m为开头的n/2的路径权值和为y，在f[m]中二分搜索最接近x-y的权值
4.迭代加深算法
若题目要求最小深度，而状态量过大无法表示时（如15！），可以从小到大枚举深度大小k，然后运用dfs判断k是否可行，辅以可行性剪枝
5.A（IDA）算法：估价函数/搜索顺序优化（最优性剪枝，可与迭代加深算法结合，若f(n)>k,则直接退出）
设f(n)=g(n)+h(n)
f(n)为途径n的估计最短距离
g(n)为到达n的最短距离
h(n)为n到达终点的估计最优距离（如曼哈顿距离）
我们取f(n)最小的状态进行dfs，dfs后对状态的f(n)进行更新，继续取最小的状态（相当于最优性剪枝）进行dfs直至找到目标状态，则此时即为最优解，可用堆来实现
证明：最短路径的估计f(n)<其实际f(n)
非最短路径的实际f(n)>最短路径的实际f(n)，故非最短路径的实际f(n)必大于最短路径的实际f(n),故一定是最优解先取到
其他场景中，若估计最优距离==实际最优距离，则效率最高（基本不可能，因为这样基本就不用搜索了啊）
估计最优距离>实际最优距离，搜索的状态少了，但不一定能得到最优解
PS：估价函数体现了搜索的方向性，即向着最可能最优解的方向，故可大大优化时间
bfs可看作特殊的估价函数