概述

搜索算法

搜索算法大致可以分为以下几类：

• DFS 深度优先搜索
• BFS 广度优先搜索
• 迭代加深搜索
• A*搜索
• IDA* 启发式迭代加深搜索
• meet in the middle 折半搜索
• 双向 DFS
• 双向 BFS
• Dancing Links 舞蹈链

Dancing Links 算法是省选内容，在此不进行说明。

剪枝技巧

剪枝是搜索题常用的优化方式，有时能大幅提升程序运行效率，常见剪枝技巧如下：

• 可行性剪枝
• 最优性剪枝
• 排序剪枝（优化搜索顺序）
• 搜索位置剪枝（记录上一层搜索到的位置，下一层接着搜，不重新来）
• 逆向操作剪枝（两个相反的操作避免重复做）
• 重复剪枝（vis数组）
• 层数剪枝（必须证明到某一层时一定不优）
• 枚举剪枝（只利用上一层新加的数来和前面的数组合，避免重复搜上一层搜过的）

以下是常见的玄学剪枝技巧，考场上用来搏更高分的，按数据大小分段来解决，不保证正确性：

• 搜索次数剪枝（cnt>1e7,cout<<ans），本质是最优性剪枝

注意事项

注意事项：

• 迭代加深等搜索算法不见得总是比普通的 DFS 和 BFS 快，还是要根据具体情形判断。
• 搜索题的常数必须小到极致，可以使用 unordered_map 或二分等思路优化。