搜索
搜索算法是对状态空间进行枚举的方法，通过穷尽所有可能来找到最优解或统计合法解的个数。搜索是许多高级算法的基础，也是获取部分分数的重要手段。
章节目录
基础搜索
进阶搜索
搜索技巧
| 专题 | 说明 |
|---|---|
| 回溯法 | 试探与回退的搜索框架 |
| [Dancing Links](https://leetcode.com/problems/Dancing Links/) | 精确覆盖问题的高效算法 |
| [Alpha-Beta 剪枝](https://leetcode.com/problems/Alpha–Beta 剪枝/) | 博弈树搜索优化 |
| 搜索优化 | 剪枝、记忆化等技巧 |
搜索算法对比
| 算法 | 完备性 | 最优性 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|---|
| DFS | 有限图完备 | 否 | ||
| BFS | 完备 | 单位代价最优 | ||
| 迭代加深 | 完备 | 单位代价最优 | ||
| A* | 完备 | 最优（一致启发式） | 指数级 | 指数级 |
| IDA* | 完备 | 最优 | 指数级 |
其中 为分支因子， 为解的深度， 为最大深度
搜索优化策略
flowchart TD A[搜索优化] --> B[减小搜索空间] A --> C[改变搜索顺序] A --> D[剪枝策略] B --> B1[状态压缩] B --> B2[等价状态合并] C --> C1[最优性剪枝] C --> C2[启发式排序] D --> D1[可行性剪枝] D --> D2[最优性剪枝] D --> D3[记忆化]