(资料图)

搜索

所谓搜索就是列举所有的可能，也是一种暴力的算法。根据搜索优先级，一般分为深度优先和广度优先。深度优先搜索（Depth First Search）：一条路走到底，走不通再回头。广/宽度优先搜索（Breadth First Search）：一层一层的搜索。

例题

• P1451 求细胞数量
• P1706 全排列问题
• P9241 飞机降落
• P1219 八皇后
• P1379 八数码

搜索剪枝

普通的搜索会搜到很多不必要的情况，那么可以想办法剪掉这部分，于是剪枝出现了。剪枝把不会产生答案的或者不必要的枝条剪掉。

剪枝原则

• 正确性：保证不丢失正解的结果；
• 准确性：尽量剪去多余枝条；
• 高效性：降低时间复杂度的同时，保证效率。

对于DFS，我们常见的有以下剪枝方法：

1. 可行性剪枝：当前结果不可行，就不再继续搜索。
2. 搜索顺序剪枝：确定一个较优的搜索顺序，例如求最小值，就从最小值先搜索，效率或许更为优秀。
3. 最优性剪枝：当前结果与已有结果相比，不是最优了，就不必继续搜索。
4. 排除等效冗余：当多个枝条具有完全相同的结果的时候，只选择一个即可。
5. 记忆化搜索(dp)：将当前位置的结果记录下来，以后再次搜索该位置结果的时候直接返回存储的结果
6. 奇偶性剪枝：提前确定奇数与偶数的情况下的不同状态，看能否提前处理。

例题

• P1434 [SHOI2002] 滑雪
• P1025 [NOIP2001 提高组] 数的划分
• P1120 小木棍
• P1433 吃奶酪