搜索技巧
Function0816 · · 算法·理论
搜索技巧
剪枝
1.最优性剪枝
不会比之前更优，提前退出。（也可以从最优方案开始枚举）
2.可行性剪枝
- 一定不可行，提前退出（可能超过限制或不达目标）；
- 对数据进行预处理，使越可能不成立的越靠前；
- 对于同种使方案不成立的步骤，仅考虑一次，然后将同类全部排除。
\color{#E74C3C}折半搜索
逐个匹配的过程中，用二分查找，可以借助前一个的匹配范围进行排除。
\color{#E74C3C}记忆化搜索
dp^_^
迭代加深搜索
每次搜索限定最大深度，每一次只搜到一个固定深度，逐次加深。（一般适用于步骤越少越好的情况）
*应有一个变量记录此次搜索的最大深度
数学方式
简单地找一下通式