《noi导刊枚举与搜索》由会员分享，可在线阅读，更多相关《noi导刊枚举与搜索（66页珍藏版）》请在金锄头文库上搜索。
1、枚举与搜索讲稿 长沙市雅礼中学 朱全民,有关搜索的NOIP试题,神经网络(2003)-宽搜 侦探推理(2003)-枚举与优化 传染病控制(2003)-深搜与优化 虫食算(2004)-深搜与优化 火柴棒等式(2008)-简单枚举 双栈排序 (2008)-二分图的搜索 靶形数独(2009)-深搜与优化,简单枚举法,所谓枚举，即对可能的解集合一一列举。 解题思路为： 首先确定可能的解集合 抽象出解包含的参数，确定每个参数的数据范围 对解的每个参数的数据范围采用循环语句一一枚举 对每次枚举，根据题意给定的条件判定是否解，是否是最优解。,火柴棒等式,给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等
2、式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：,注意： 1. 加号与等号各自需要两根火柴棍 2. 如果AB，则A+B=C与B+A=C视为不同的等式（A、B、C=0） 3. n根火柴棍必须全部用上,分析,09的数字所用的火柴数：6,2,5,5,4,5,6,3,7,6 对于N=24，去掉+，=，实际上数字只有20根火柴。 首先考虑解集合，因为最多为20根火柴组成数字： 不可能为10个1； 不可能8个1，1个4； 不可能为7个1，2个7或1个0； C不会超过1000,枚举答案,设F(I)表示数为I时的火柴棍数 FOR A=0 TO 1
3、000 DO IF F(A)N-4 THEN FOR B=1000-A DO IF F(A)+F(B)+F(A+B)=N-4 THEN 输出；,侦探推理,证词中出现的其他话，都不列入逻辑推理的内容。 明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真话。 现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！ 要求： 判断谁是罪犯？,分析,这道题的关键点是“如何能够快速正确实现出来” ，事实上这道题对编码能力的要求要大于对算法本身的要求。由于这道题的数据范围并不是很大，但需要进行“字符串处理”这种比较麻烦的工作，因此在比赛时就可以采用效率低一些的枚举算法来
4、换取编码上的简单。 推荐的算法分为两步： 1预处理每个人的每一句话，并把它们分类处理； 2枚举罪犯和当前星期几，找出所有可能发生的情况。 下面我们来逐步细化一下每一步的算法，对于第一步，我们希望的是把一些杂乱的不好处理的“字符串信息”转化为相对比较好处理的信息。为此，我们可以通过把“信息”进行分类的方法使得对于每一类信息，更加方便的处理（即我们可以用一个或者几个变量来表示），由题目描述可以发现语句可分为三类：,分析,1指明i是否是罪犯的语句； 2指明今天是星期d的语句； 3没有意义的语句(不符合格式要求)。 我们必须要说明的是任何不符合格式要求的语句都将被划分到第三类中去，这样在处理每个语句的
5、时候就必须要考虑该语句是否符合格式要求，通过以上的处理，我们对于每一个语句用几个变量就可以表示了。 对于第二步的细化，我们在枚举完罪犯和当前星期几之后，就可以比较方便的判断每一句话的真伪了，这样我们再根据每个人所说的话把人进行分类。 1没说任何一句有意义的话； 2只说真话； 3只说假话； 4既说真话也说假话。,分析,需要注意的是，对于第一类人我们既可以把他当成说真话的，也可以把他当成说假话的，而如果第四类人存在的话，那么从他本身就可以推出矛盾了。 最后，如果对于罪犯i存在一个d使得当前情况是可能的，我们就说i就是可能的罪犯。 时间效率 O(MP|Day|) （其中Day=Sunday，Mond
6、ay, Tuesday, Wednesday, Thursday, Friday, Saturday）,优化,我们可以发现在对罪犯和当前星期几进行“双重枚举”时，进行了很多重复的操作，于是我们想到，能不能不枚举是当前星期几？这样我们把这类语句与判断罪犯的语句分离，可以先由判断罪犯的语句中确定一部分人肯定说真话，一部分人肯定说假话，剩下的一部分人就要根据他所说的当前星期几的语句来判断了，首先我们假设所有人判断星期的语句不自相矛盾，这样每个人将在判断这类问题里面至多有一个答案，我们便可以统计判断当前是星期d的总人数，于是改进后的算法对于每一个可能的罪犯，先用O(p)的时间处理所有的话，再用O(|D
7、ay|)的时间枚举星期几。这样，改进后算法的复杂度就是O(m(p+|Day|)。 那么我们可不可以再进一步，把算法优化到线性？这里面可以比较明确地告诉大家，是可以做到的，具体的算法类似于上面的按照语句的种类分离语句，只是分离得更细，处理得更复杂，在这里就不做赘述，留给大家思考。,现有一个棱长为n的立方体，可以分成n3个1*1*1的单位立方体。每个单位立方体都有一个整数值。n3个单位立方体的数和不会超过longint范围。现在要求在这个立方体找到一个包含完整单位立方体的长方体，使得该长方体内所有单位立方体的数和最大。 输入： n(1n20)；n个n*n的数字矩阵，每个数字矩阵代表一层，每个数字代
8、表一个单位立方体的整数值，-999单位立方体的整数值999 输出：长方体的数和,立方体问题,“简单”枚举过程,1、枚举所有可能的平面 for x11 to n do for x21 to n do for y11 to n do for y21 to n do for z11 to n do for z21 to n do 考察状态（x1，y1，z1，x2，y2，z2）； 2、考察状态（x1，y1，z1，x2，y2，z2）过程如下 sum0； for xx1 to x2 do 计算长方体的体积 for yy1 to y2 do for zz1 to z2 do sumsum+mapx，y，z；
9、 调整最优解 if sumbest then bestsum； 这个算法枚举状态为O（n9）,从减少重复计算入手,记录先前考察的结果。在统计长方体2时，只要将长方体1的统计结果加上长方体3就可以了，而不必按上述算法那样重新进行计算。 考察过程改为 ： for xx1 to x2 do 计算长方体的体积 for yy1 to y2 do sumsum+mapx，y，z2； if sumbest then bestsum； 调整最优解 由于利用了计算出的结果，整个算法的时间复杂度降为O（n8）。,3、提取恰当的信息 上述考察实际上求出z轴坐标为z2的平面中矩形（x1，y1，x2，y2）的数和。我们
10、将这个数和记为value(a) value(A)=value(ABCD)+value(B)-value(BC)-value(BD) 这就启发我们用另一种方法表示立方体的信息：设recx，y，z表示z轴坐标为z的水平面中矩形（1，1，x，y）的数和。 z轴坐标为z的水平面中左上角为（x1，y1）、右下角为（x2，y2）的矩阵的数和为recx2，y2，z+ recx1，y1，z-recx2，y1，z-recx1，y2，z,Rec数组可以在输入数据的同时计算 fillchar(rec，size(rec)，0)；rec数组初始化 for z1 to n do 逐层输入信息 for x1 to n do
11、 逐行输入z平面的信息 for y1 to n do 逐列输入z平面上x行的信息 begin read(mapx，y，z)； 输入z平面上（x,y）中的数 if (x=1)and(y=1) 计算z平面上以（1，1）为左上角、（x,y）为右下角的矩形的数和 then rec1，1，zmap1，1，z else if y=1 then recx，y，zrecx-1，n，z+mapx，y，z else recx，y，zrecx，y-1，z+mapx，y，z； end；for 这样，考察过程就可以改为 sumsum+recx2，y2，z2+recx1，y1，z2-recx2，y1，z2-recx1，y
12、2，z2； if sumbest then bestsum； 时间复杂度降为O（n6）。,如果长方体a的数和是负数，则长方体a的计算结果废弃，考察长方体b-a。因为长方体b的数和=长方体b-a的数和+长方体a的数和，由于长方体a的数和为负，长方体b-a的数和一定大于等于长方体b的数和。由此可见，在累计长方体数和的时候，只要由上而下地枚举长方体下底面的z轴坐标即可。设 total(z)以z轴坐标为z的平面为下底面的长方体的最大数和,算法框架,for x11 to n do 枚举所有可能的子平面 for x21 to n do for y11 to n do for y21 to n do beg
13、in total0；以（x1,y1）为左上角、（x2,y2）为右下上角） for z1 to n do 枚举长方体b下底面的z轴坐标 begin totalmax total，0 + recx2，y2，z + recx1-1，y1-1，z - recx2，y1-1，z - recx-1-1，y2，z； 计算以z为下底面的长方体b的最大数和 if total best then besttotal； 调整最优解 end； end； 这一改进使得考察的状态整数降为n5,深度优先搜索,深度优先搜索算法是搜索中的一种控制策略，但与枚举法不同的是，它是从初始状态出发，运用题目给出的条件、规则，按照深度优
14、先的顺序扩展所有可能情况，当所有可能情况都探索过且都无法到达目标的时候，再回退到上一个出发点，继续探索另一个可能情况，这种不断回头寻找目标的方法也称为“回溯法”。 深度搜索是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。,深度搜索算法的几个重要因素,(1) 状态: 作为递归的值参。 (2) 边界条件: 作为递归的结束条件，通常以深度结束。 (3) 递归范围: 作为for循环的初值和终值。 (4) 约束条件: 满足解的条件。 (5) 最优性要求：满足最优解的条件。,深度搜索的基本框架,procedure dfs(当前状态)； begin if 当前状态为边界 then begin i
15、f 当前状态为最佳目标状态 then 记下最优结果；exit；回溯 end； for i算符最小值 to 算符最大值 do begin 算符i作用于当前状态，扩展出一个子状态； 标记子状态路径； if (子状态满足约束条件) and (子状态满足最优性要求)then dfs(子状态)； 恢复子状态路径； 回溯 end； end；,N皇后问题,在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置两个皇后），编程求解所有的摆放方法。,基本思想,由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置可以进行试探； 按行放置皇后，每一行放一皇后； 对每一行所放置的皇后按列进行试探； 若某个位置能放，则放，否则试放下一个位置 若某一行没有任何一个位置可放，则表示前面的皇后没放好，需要回溯。 若n个皇后都放好了，则得到了一个解。,算法基本框架,Procedure Try(i:integer)； 搜索第i行皇后的位置 var j:integer; begin if i=n+1 then 输出方案； for j:=1 to n do if 皇后能放在第i行第j列的位置 then be
