剪枝策略
- 调整搜索顺序（层次）
比如让体积大的先选，或者选择比较少的位置先枚举 - 排除等效冗余
发现两个搜索状态（子树）其实是等价的（比如\(A+B\)和\(B+A\)），只需要枚举其中一种即可 - 可行性剪枝
不行的状态直接\(skip\) - 最优性剪枝
现在的花费已经大于答案直接\(skip\)
A*的思路:现在的答花费+估计函数已经大于答案 直接\(skip\) - 记忆化
一个状态只做一次
迭代加深
优化dfs（当分支很多但答案在较浅位置浪费的枚举时间太多）
应用场景：搜索树的规模随着深度的增长急剧增长，但可以肯定答案在一个较浅的节点上
限制层数（深度），找不到再一步一步增加
双向搜索 (dfs和bfs都可以）
常常处理例如\(n=40\)的\(O(2^n)\)问题
把\(n\)砍一半
应用场景：有初态也有终态，从两端同时搜，在中间交汇组合答案
双端队列优化bfs 和 优先队列优化bfs
边权有0和1两种的用双端队列优化，1的加队尾，0的加队头
边权各种各样的用优先队列优化，有点类似于最短路dijkstra
A*
估计函数（不能大于未来实际代价）+优先队列bfs
每个状态只扩展一次
IDA*
迭代加深+A*（用dfs）