夏令营7.31总结

搜索优化

今天又去上大班课，然后又把我热死了。

为什么要优化

在比赛中，搜索一般用于取得部分分，而且大部分时候无法通过都是因为超时。

但是，搜索还是很多高级算法的基础。所以，搜索还是很重要的。

三种优化

剪枝

遇到一些显然不合法/不是最优解的答案时直接返回。

当然，剪枝的缺点（？）就是很难分析剪枝后的算法的时间复杂度，所以也很难预测分数。所以，剪枝其实和卡常一样，也是比较适合在骗分的时候使用。

这里用例题帮助理解。

八皇后

暴力：通过DFS枚举所有的$C^n_{n^2}$种可能性，再对于每一种可能性都进行判断。但是时间显然会直接爆炸。

剪枝：

• 剪枝1：由于每行，每列都只能放一个棋子，所以可以进行搜索，保证每行只放一个旗子，且放的列不重合。但是依然又$n!$种情况，还是无法通过$n=13$的情况。
• 剪枝2：在剪枝1的基础上增加一个判断对角线：
  • 假设用$i$表示格子的行，j表示格子的列，那么对于每一条从左上到右下的对角线上的所有旗子，应该满足$i-j$相同或$i+j$相同。所以只要开两个数组记录即可。
  • 时间复杂度…不想算了，但是肯定可以过。
• 其实这题的最好方式是直接打表。同dfs的暴力枚举，打表一下即可直接通过。

总结

剪枝方法千千万，好的剪枝省一半（时间）。

如果无法准确估计剪枝后的时间复杂度，那么最好多加几个。

剪枝，可以少加，可以不加，但是如果要加，那么请一定一定要确保剪枝的正确性。否则丢失了暴力分，反而就得不偿失了。

大部分的题目的剪枝技巧其实都是差不多的。

启发式搜素

启发式搜索其实就是一种高级的剪枝，核心思路就是剪枝是一个简单的判断，启发式搜索则是对当前的状态进行判断（通过估价函数），从而降低时间复杂度。

采药

这题的正解是DP，但是可以考虑使用dfs。

普通的估价函数过于乐观，无法有效减少枚举量。

所以考虑一个更加合理的估价函数$h(i)$：对于所有的药材按照$\frac{w_i}{t_i}$从大到小排序，尽量选择靠前的药材，如果剩余的$T<t_i$则假设获得了$T\times\frac{w_i}{t_i}$的价值。

合理之处：保证了估价函数一定优于实际代价，且最贴合。

总结

如果把一些题目题意拆开理解就比较简单，但是题面其实特别长，要读好几遍才能完全理解。

迭代加深搜索

这种搜索方法其实像是$\text{dfs}+\text{bfs}=\text{dbfs}(?)$。

过程：假定一个初始为0的递归上界$D$，且从起始状态开始搜索的过程。于普通搜索的不同之处在于：一旦到达了上界，就不再往下搜索。搜索结束后：

• 找到结果：终止；
• 否则$D++$，重新搜索。

优点：

• 对于DFS：时间复杂度较低（在所有解深度不大时）
• 对于BFS：空间复杂度较低（只要保留搜索树上一条链的情况）

结尾

其实原本是要加上例题的，但是后来发现今天的时间比较紧张，就没写例题了。但是其实这个搜索剪枝的知识点还是很有用的。