深搜算是接触时间最长的搜索算法之一,但是由于平时遇到的题目不多,反而学的不算扎实。这类算法的难点在于状态的记录、检索、剪枝优化。尤其是把问题的发展想明白,常犯的错误是“重叠”,没有弄明白状态的“层次”和“分支”,造成重复遍历若干覆盖同一状态的搜索树,使得搜索的复杂度大规模增长。本篇就总结两道不错的入门复习题和应该学会的综合题。
CODEVS4228 小猫爬山
题意
有n只小猫要坐缆车下山,每辆缆车最大承重为w,租用费用为1元/辆。现在给出每只猫的重量Ci,问把n只猫都送下山最少花多少钱?1 ≤ n ≤ 18,1 ≤ Ci ≤ w ≤ 1e8。
思路
本题需要记录的状态有当前正在处理第几只猫now,目前已经租用了几辆车cnt,每辆缆车上当前搭载的重量之和cab。在考虑每一只猫时:
1、优先考虑能否将猫放到已经租用的缆车上,如果可以,就以cab+Ci为下一状态继续递归搜索;
2、遍历完所有缆车后考虑再租一辆新车载这只猫,cnt++;
3、每一个状态向下搜索后,记得回溯还原“案发现场”以便搜索下一种可能状态;
4、注意剪枝优化,最大成本为给每只猫租一辆车,所以每当搜索到结束状态就更新最小成本;相应的,每当发现当前成本已经超过记录的最小成本,就可以立刻回溯了。
代码
1 | int n, w, a[N], c[N]; |
POJ 2676/3074 Sudoku
【题意】
给出一个9x9的数独游戏,完成填写该数独,要求图中每行、每列、每个3x3的九宫格内数字1~9恰好出现一次。POJ3074数据更难。
【思路】
百度了一下数独游戏发现解决该问题的算法博大精深,最近是没时间学了,有很多优化复杂度的框架,这里就使用通过代码的常规思路总结一下。
数独问题的搜索框架很简单,在每个状态下,找出一个还没有填的位置,检查还有哪些数字可以填,用这些合法的数字继续往下递归即可。
这里容易犯开头说的重复错误,即在每个状态下,只找一个位置进行状态的递归,不能枚举所有可填数字的位置向下递归,否则会造成重复遍历若干棵覆盖同一状态空间的搜索树,使得复杂度过大。
此外,为了降低搜索规模,程序应该像人类玩数独一样,从可能性最小的位置开始尝试:也就是在每个状态下,从所有空位置里可填数字可能性最少的位置考虑作为分支。
状态的保存如果用三维数组会在记录、检索、更新上花费太多时间,我们考虑使用一个9位二进制数来保存当前位置可以填的数字,使用位运算降低复杂度。
具体的说,对于每个位置,将它所在的行、列、九宫格的3个二进制数进行按位与运算即可获得能填哪些数,然后使用lowbit()运算可以将数字取出;
当一个位置填上一个数,将该位置的3个二进制数相应的位数改为0,即可更新状态,回溯时改为1还原现场;
【代码】
1 | int row[N], col[N], g[5][5]; //3个二进制数 |
嘻嘻。