搜索算法中的剪枝是什么?常见剪枝策略有哪些?
哪些公司问过
答案要点
- 定义:搜索中提前排除不可能产生合法解或更优解的分支,减少搜索空间
- 可行性剪枝:当前状态已违反约束(如和已超过目标)就回退
- 最优性剪枝:当前代价加剩余下界已不优于已知最优解,分支限界即此思路
- 去重剪枝:排序后跳过同一层的重复元素,避免产生重复解
- 典型应用:回溯、Alpha-Beta 剪枝;决策树的预剪枝和后剪枝用于防止过拟合
易错点
- 剪枝条件写错,把可行解剪掉导致结果不完整
- 把剪枝和记忆化混为一谈:剪枝是不展开分支,记忆化是缓存子问题结果
- 以为剪枝一定能降低最坏时间复杂度,多数情况只改善实际运行表现
面试官常见追问
- Alpha-Beta 剪枝的原理是什么?
- 决策树的预剪枝和后剪枝有什么区别?
- 全排列 II 中怎么做去重剪枝?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。