2014信息学奥林匹克夏令营-day7搜索算法的优化(林厚从).pdf

搜索算法的优化 常州市第一中学 林厚从 JSOI2014夏令营 14-7-7 对搜索的认识 搜索是万能的，只会搜索是万万不能的！ 搜索是需要优化的，一味地暴力搜索是不行的 ！ JSOI2014夏令营 14-7-7 《搜索算法的优化》目录 1 常规方法：预置常数、记忆化搜索 2 状态表示与状态压缩：压位、hash 3 深度优先：迭代加深、剪枝(分支定界) 4 宽度优先：双向宽搜、启发式搜索(A*) JSOI2014夏令营 14-7-7 一、常规方法 1、预置常数 和穷举、动态规划等算法的优化方法一样，在搜索之前预先计算好 一些常数表，在搜索过程中直接调用 (O(1))，以减少搜索过程中的重复 计算量，从而高搜索的效率。 JSOI2014夏令营 14-7-7 一、常规方法 例1、方格计数 [问题述] 对于一个n*n （n30）的回型方阵（如图为 一个7*7的回型方阵），从左上角走到右下角， 每步只可以向下或向右走，把走过的格子里的 数全部加起来，形成一条路径的和，如13 （背 景），18 （红色）等。 问题是，输入n，输出从左上角到右下角的 所有路径和为素数的个数。 JSOI2014夏令营 14-7-7 一、常规方法 [问题分析] 1、一共有多少条路径？ P = C(2n-2，n-1)，n30 2、路径 (状态)的表示：一条路径可以用一个01数组dir来存储，dir[i]=1表示向右、 dir[i]=0表示向下。 这样，第一条路径可以表示成 (长度为2n-2的01串)：111111000000 3、搜索 (穷举)：采用类似于“穷举二进制数”的方法，求出下一条路径。 4、每一条路径形成后，都要求和，再判断是否为素数，如何优化？ 因为：n30，所以只要预先生成1000以内的素数表Prime，查表判断即可。 JSOI2014夏令营 14-7-7 一、常规方法 [问题分析] 5、主要程序框架如下： 生成1000以内的素数表Prime； 初始化第一条路径； for i:=1 to P do //P为路径条数 begin 求出一条路径上的数之和T； if Prime(T) then S:=S+1； 生成下一条路径； end； JSOI2014夏令营 14-7-7 一、常规方法 2、记忆化搜索 搜索树往往是巨大的，带来的时间和空间复杂度都很高 ！但是，在 很多情况下，有可能很多结点表示的都是同一个状态，我们把这样的状 态叫做 “重叠子问题”，比如求fib数列的第n项。由于搜索算法本身性 质的制约，它不能把这些重叠子问题记录下来，只能不知疲倦地继续访 问下去，不断遇到和计算这些讨厌的重叠子问题。显然，如果能不把时 间放在处理重叠子问题上，算法的效率将发生一个质的飞跃。那么有没 有这样一种可以避免重复地处理重叠子问题的算法呢？这就是“动态规 划”。 JSOI2014夏令营