枚举与搜索教案

1、枚举与搜索讲稿1有关搜索的NOIP试题 神经网络(2003)-宽搜侦探推理(2003)-枚举与优化传染病控制(2003)-深搜与优化虫食算(2004)-深搜与优化火柴棒等式(2008)-简单枚举双栈排序 (2008)-二分图的搜索 靶形数独(2009)-深搜与优化 2简单枚举法所谓枚举，即对可能的解集合一一列举。解题思路为：首先确定可能的解集合抽象出解包含的参数，确定每个参数的数据范围对解的每个参数的数据范围采用循环语句一一枚举 对每次枚举，根据题意给定的条件判定是否解，是否是最优解。 3火柴棒等式 给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整

2、数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：注意：1. 加号与等号各自需要两根火柴棍2. 如果AB，则A+B=C与B+A=C视为不同的等式（A、B、C=0）3. n根火柴棍必须全部用上4分析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不会超过10005枚举答案设F(I)表示数为I时的火柴棍数FOR A=0 TO 1000 DO IF F(A)best then bestsum

3、；这个算法枚举状态为O（n9） 13从减少重复计算入手记录先前考察的结果。在统计长方体2时，只要将长方体1的统计结果加上长方体3就可以了，而不必按上述算法那样重新进行计算。考察过程改为 ： for xx1 to x2 do 计算长方体的体积 for yy1 to y2 do sumsum+mapx，y，z2； if sumbest then bestsum； 调整最优解由于利用了计算出的结果，整个算法的时间复杂度降为O（n8）。143、提取恰当的信息上述考察实际上求出z轴坐标为z2的平面中矩形（x1，y1，x2，y2）的数和。我们将这个数和记为value(a) value(A)=value(A

4、BCD)+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，z15Rec数组可以在输入数据的同时计算fillchar(rec，size(rec)，0)；rec数组初始化for z1 to n do 逐层输入信息 for x1 to n do 逐行输入z平面的信息for y1 to n do 逐列输入z平面上x

5、行的信息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，y2，z2； if sumbest then bestsum；时间复杂度降为

6、O（n6）。16如果长方体a的数和是负数，则长方体a的计算结果废弃，考察长方体b-a。因为长方体b的数和=长方体b-a的数和+长方体a的数和，由于长方体a的数和为负，长方体b-a的数和一定大于等于长方体b的数和。由此可见，在累计长方体数和的时候，只要由上而下地枚举长方体下底面的z轴坐标即可。设total(z)以z轴坐标为z的平面为下底面的长方体的最大数和17算法框架for x11 to n do 枚举所有可能的子平面for x21 to n dofor y11 to n dofor y21 to n do begin total0；以（x1,y1）为左上角、（x2,y2）为右下上角） for

7、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；这一改进使得考察的状态整数降为n518深度优先搜索深度优先搜索算法是搜索中的一种控制策略，但与枚举法不同的是，它是从初始状态出发，运用题目给出的条件、规则，按照深度优先的顺序扩展所有可能情况，当所有可能情况都探索过且都无法到达目标的时候，再回退到上一

8、个出发点，继续探索另一个可能情况，这种不断回头寻找目标的方法也称为“回溯法”。深度搜索是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。 19深度搜索算法的几个重要因素(1) 状态: 作为递归的值参。(2) 边界条件: 作为递归的结束条件，通常以深度结束。(3) 递归范围: 作为for循环的初值和终值。(4) 约束条件: 满足解的条件。(5) 最优性要求：满足最优解的条件。20深度搜索的基本框架procedure dfs(当前状态)；begin if 当前状态为边界 then begin if 当前状态为最佳目标状态 then 记下最优结果；exit；回溯 end； for i算符最

9、小值 to 算符最大值 do begin 算符i作用于当前状态，扩展出一个子状态； 标记子状态路径； if (子状态满足约束条件) and (子状态满足最优性要求)then dfs(子状态)； 恢复子状态路径； 回溯 end；end；21N皇后问题 在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置两个皇后），编程求解所有的摆放方法。22基本思想由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置可以进行试探；按行放置皇后，每一行放一皇后；对每一行所放置的皇后按列进行试探；若某个位置能放，则放，否则试放下一个位置若某一行没有任何一个位置可

10、放，则表示前面的皇后没放好，需要回溯。若n个皇后都放好了，则得到了一个解。23算法基本框架Procedure Try(i:integer)；搜索第i行皇后的位置var j:integer;begin if i=n+1 then 输出方案； for j:=1 to n do if 皇后能放在第i行第j列的位置 then begin 放置第i个皇后； 对放置皇后的位置进行标记； Try（i+1） 对放置皇后的位置释放标记； end;end;24边界条件设置怎样判断某列放置了皇后 a: array 1.MaxN of Boolean; 竖线被控制标记怎样判断某对角线上放置了皇后 b: array 2

11、.MaxN * 2 of Boolean; 左上到右下斜线被控制标记 c: array 1-MaxN . MaxN-1 of Boolean; 左下到右上斜线被控制标记25程序Procedure Try( i: integer)；var j:integer;begin if i=n+1 then print； for j:=1 to n do if aj and bi+j and ci-j then begin ai:=j; aj:=false; bi+j:=false; ci-j:=false; Try (i+1) aj:=true; bi+j:= true; ci-j:= true; en

12、d;end;26给出一个矩阵及一些国都名：o k d u b l i n dublina l p g o c e v tokyor a s m u s m b londono s l o n d o n romey i b l g l r c bonnk r z u r i c h pariso a i b x m u z oslot p q g l a m v lima要求从这个矩阵中找出这些国都名，并输出它们的起始位置及方向。寻找国都名 搜索的方向27算法思想将字符矩阵读入到二维数组，然后对每一个国都名进行搜索，首先需要在矩阵中找到国都名的第一个字符，然后沿八个方向进行搜索。直到找到国都名

13、为止。若在矩阵中没有找到，则输出相应的信息。在搜索过程时，类似八皇后问题，建立一个标志数组，标识已经搜索过的方向，在对八个方向搜索时，可以建立一个方向数组，使得程序更加简洁明了 Const Fx : Array1.8,1.2 Of Shortint 定义八个方向 =(0,1),(0,-1),(1,0),(-1,0),(1,-1),(-1,1),(1,1),(-1,-1); 28Procedure Work(T,X,Y:Integer);搜索路径，T为国都名的字符位置，X，Y为当前搜索的坐标Var I : Integer;Begin If T=Length(S)+1 Then begin 搜索完

14、，打印输出 Out; exit end; For I:=1 To 8 Do 八个方向进行搜索 Begin X:=X+FxI,1; Y:=Y+FxI,2; 坐标变化 If (AX,Y=ST)And(BX,Y) Then Begin W:=W+Chr(I+48); 记录路径 BX,Y:=False; 设置已经搜索 Work(T+1,X,Y); 继续搜索下一个 Delete(W,Length(W),1);恢复原路径 BX,Y:=True; 恢复标志 End; X:=X-FxI,1; Y:=Y-FxI,2; 返回后，坐标恢复 End;End;29构造字串生成长度为n的字串，其字符从26个英文字母的前p

15、(p26)个字母中选取，使得没有相邻的子序列相等。例如p=3，n=5时 a b c b a满足条件 a b c b c不满足条件输入：n，p输出：所有满足条件的字串30分析状态：待扩展的字母序号i。由于该变量的存储量太大，因此我们将s设为全局变量；边界条件：产生了一个满足条件的字串，即 i=n+1；搜索范围：从a开始的后p个字符； 约束条件：当前字串没有相邻子串相等的情况31procedure solve (i: integer)； var j, k: integer； t : longint ; begin if i=n+1 then 若产生了一个满足条件的字串，则输出 begin writ

16、eln (s)； inc( t )；exit 回溯 end； for k1 to p do 搜索每一个可填字母 begin ss+chr(64 + k )；j1；检查当前字串是否符合条件 while (j=i div 2) and (copy(s,length(s)-j+1,j)copy(s,length(s)-2*j+1,j) do inc (j)； if ji div 2 then solve(i+1)； 若当前字串符合条件，则递归扩展下一个字母 delete( s, length (s), 1 ) 恢复填前的字串 end;end;32记忆化搜索1. 递归前对尚待搜索的信息进行预处理 如果

17、搜索对象是通过某种运算直接得出其结果的，那么搜索前一般需进行预处理通过相应运算将所有搜索对象的计算结果置入常量表，搜索过程中只要将当前搜索对象的结果值从常量表取出即可。2.记忆化搜索如果解答树中存在一些性质相同的子树，那么，只要我们知道了其中一棵子树的性质，就可以根据这个信息，导出其它子树的性质。这就是自顶向下记忆化搜索的基本思想。33序关系计数用关系和=将3个数a、b和c依次排列有13种不同的关系：abc， ab=c， acb， a=bc， a=b=c， a=cb， bac， ba=c， bca， b=ca， cab， ca=b， cba。输入n输出n个数依序排列时有多少种关系。341 、枚

18、举所有序关系表达式由于类似于a=b和b=a的序关系表达式是等价的，为此，规定等号前面的大写字母在ASCII表中的序号，必须比等号后面的字母序号小。状态（Step，First，Can）：其中Step表示当前确定第Step个关系符号；First表示当前大写字母中最小字母的序号；Can是一个集合，集合中的元素是还可以使用的大写字母序号边界条件（step=n）：即确定了最后关系符号搜索范围（Firstin）：枚举当前大写字母的序号约束条件（i in Can）：序号为i的大写字母可以使用35procedure Count(Step，First，Can)； 从当前状态出发，递归计算序关系表达式数 begi

19、n if Step=n then begin 若确定了最后一个关系符号，则输出统计结果 for iFirst to n do if i in Can then Inc(Total)； Exit 回溯 end；then for iFirst to n do 枚举当前的大写字母 if i in Can then begin 序号为i的大写字母可以使用 Count(Step+1，i+1，Can-i)； 添等于号 Count(Step+1，1，Can-i) 添小于号 Endthen end； Count该算法的时间复杂度是W(n!)362、粗略利用信息 若已经确定了前k个数，并且下一个关系符号是小于号

20、，这时所能产生的序关系数就是剩下的n-k个数所能产生的序关系数。设i个数共有Fi种不同的序关系，那么，由上面的讨论可知，在算法1中，调用一次Count(Step+1，1，Can-i)之后，Total的增量应该是Fn-Step。这个值可以在第一次调用Count(Step+1，1，Can-i)时求出。而一旦知道了Fn-Step的值，就可以用TotalTotal+Fn-Step 代替调用Count(Step+1，1，Can-i) 37procedure Count(Step，First，Can)； Step，First，Can的含义同算法1 begin if Step=n then begin 若确

21、定了最后一个关系符号，则输出统计结果 for iFirst to n do if i in Can then Inc(Total)；Exit 回溯 end；then for iFirst to n do 枚举当前的大写字母if i in Can 序号为i的大写字母可以使用then begin Count(Step+1，i+1，Can-i)；添等于号 if Fn-Step=-1 then begin 第一次调用 Fn-Step Total；Count(Step+1，1，Can-i)； 添小于号 Fn-Step Total-Fn-Step Fn-Step=Total的增量end thenelse

22、TotalTotal+Fn-Step Fn-Step已经求出 endthen end；count该算法实质上就是自顶向下记忆化方式的搜索，它的时间复杂度为W(2n)。 383、充分利用信息在搜索的过程中，如果确定在第k个大写字母之后添加第一个小于号，则可得到下面两条信息：第一条信息：前k个大写字母都是用等号连接的。前半部分将产生的序关系数，就是n个物体中取k个的组合数第二条信息：在此基础上继续搜索，将产生Fn-k个序关系表达式。这样，我们可以得到Fn 的递推关系式：采用上述公式计算Fn的算法记为算法3，它的时间复杂度是W(n2)。39var Total ：Comp；答案 F ：array0.m

23、axn of Comp；Fi为i个数的序关系表达式个数 i，j ：Integer； x ：Comp； begin FillChar(F，Sizeof(F)，0)；F初始化 F0 1； for i1 to n do begin递推F数组 Fi 0；x1； for j1 to i do begin 计算Fi xx*(i-j+1)/j；Fi Fi+x*Fi-j Endfor end；for writeln(Fn)； 输出结果 end；main40传染病控制传染病的传播具有如下性质：第一:它的传播途径是树型的，一个人X只可能被某个特定的人Y感染，只要Y不得病，或者是XY之间的传播途径被切断，则X就不会

24、得病。第二:这种疾病的传播有周期性，在一个疾病传播周期之内，传染病将只会感染一代患者，而不会再传播给下一代。第三:在一个疾病传播周期内，只能设法切断一条传播途径，而没有被控制的传播途径就会引起更多的易感人群被感染（也就是与当前已经被感染的人有传播途径相连，且连接途径没有被切断的人群）。当不可能有健康人被感染时，疾病就中止传播。所以，蓬莱国疾控中心要制定出一个切断传播途径的顺序，以使尽量少的人被感染。你的程序要针对给定的树，找出合适的切断顺序 。41贪心我们首先来通过对样例数据和其它的一些比较简单的数据进行一些观察，很容易得到一种贪心的算法，对这种算法可做如下的描述：1我们用Sum(i)表示以i

25、为根节点的子树上的节点总数。那么我们每次砍掉当前层中还未砍掉的节点里面使得Sum(i)取到最大值的那个节点；2重复第1步直到当前层中的节点为空。 一个反例42随机化搜索1我们通过随机函数来选择即将被砍掉的节点，可以通过设置权值来使得算法更大可能地去选择“看起来最优”的决策；2重复第1步直到当前层中的节点为空；3对前两步执行多次并选取所得到的最优结果。这个算法被设计出来以后，就很难在构造出能使这个算法失败的数据了，因此在考场上能够设计出来这个算法就已经很令人满意了，而事实也恰恰如此（这个算法可以通过所有的测试数据）。43虫食算所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数

26、字来判定被啃掉的字母。 BADC + CBDA DCCC 给出一个N进制的虫食算式，相同的字母代表相同的数字，不同的字母代表不同的数字。要求求出满足这个算式的唯一一组解，也就是字母和数字的一一对应关系. 44解决方案1要求一一对应的关系，就可以枚举这些一一对应的关系，找出符合的一项。这样，关系总数有O(N!)个，最坏情况下必须枚举所有的关系，并且加以判断，复杂度高达O(N*N!)！45优化大体上，从算式最后一位开始模拟运算情况，当可递推时递推，不可递推则枚举。对于一竖列，先处理两个加数，当遇到的字母的值不确定时，则枚举当前位（注意与前面的情况判重）；否则不作为处理和，当遇到的字母的值不确定时,

27、可从加数部分确定的值来确定（注意与前面的情况判重和进位）；否则看加数部分确定的值是否能得到和部分（注意进位）。引出矛盾就回溯。例如它最后一位的情况是(D+E) mod N=A, 对于最后一位只要枚举D,E的情况；A 则可以由D,E的值递推而来。对于倒数2位, (E+C+最后一位进位) mod N=A ；E的值可以用前面的结果；枚举C；判断A是否为(D+C+最后一位进位) mod N虽然复杂度还是O(N!)，但这种方法限制很多（相当于剪枝）。 46解决方案3两个M位数相加，可以按位相加，设第i位的进位xi=1,表示有进位，为xi表示没有进位。 BADC+ CBDA DCCC 枚举每位是否进位，复

28、杂度是O(2n), (因为首位不可能进位，无须枚举)。然后，用高斯消元法来解方程，复杂度是O(n3) 。总复杂度是O(2n*n3) 。47优化在解决方案3的基础上，我们可以对进位的枚举剪枝。观察这个竖列：A+B=C，若无进位则有A=C且BC且B=C.若能推导出A=A （A,B为任何不相等字母），则当前的枚举不可行。可用递归枚举，从后向前枚举，处理一个竖列时则用上述2个不等式，看是否矛盾。数据结构用邻接矩阵。（规定A=B，在有向图中有边）。若加进不等式A=B ，要加入所有x(x=A) =y(B=y)，枚举x,y，用O(n2)的时间。再判断是否有x=y.48靶形数独输入9*9的数，其中一些是空格，

29、要求完成 靶形数独，使得得到分数最大。49搜索剪枝首先是搜索顺序的控制. 我们总是选择当前选择余地最小的格子进行搜索. 如果有两个格子的选择范围一样大, 那么优先搜索尽量靠里的格子. 这样可以使得搜索树的上端枝条尽量少, 显著地减少了搜索树的节点数. 优先搜索靠里的格子是为了尽快得到一个得分较高的解, 提高最优性剪枝的效率最优性剪枝: 设当前还没有填入的数字总和为sum, 当前的得分为cur, 最优得分为best, 如果sum*10+cur=best, 那么已经没有继续搜索的必要了, 剪枝.使用位运算来进行集合操作: 计算选择范围大小, 判断数字k能否放入(i, j). 可以显著减小算法的常数

30、.50宽度优先搜索宽度优先搜索算法也是搜索中的一种控制策略，它不像深度优先搜索那样一直往前搜索，直到找到答案位置。宽度优先搜索是对每一步都扩展出所有可能的状态，逐层往下搜索。对于一般图而言，它从某个未被访问的顶点v出发,依次访问v的各个未曾访问过的邻接点,直到所有已被访问的邻接点都被访问到.要实现宽度优先，必须借助对列存放扩展的节点。 51宽度优先搜索算法框架procedure bfs(v);Init_queue(q); Visite(v); vistedv:=true; Insert_queue(q,w)；While not empty(q) do 取出队首元素 vFor 对所有v扩展出来的

31、元素wif not visitedw then visite(w);visitedw:=true; Insert_queue(q,w) delete_queue(q,v);52街道赛跑下图给出了一个沿街道赛跑的路线。图中有许多点，给以标号0，1，N(此图中N=9)，点之间可以用含箭头的线相连。标号为0的点是起点；标号为N的点为终点。含箭头的线表示单向通行的街道。运动员沿箭头所指方向从一个点跑向另一个点；在每一个点上，运动员可以选择任何一个箭头(向外的)继续向前跑。53一个完整路线具有如下特点： 1路线中每一点都可从出发点到达； 2路线中每一点都可到达终点； 3终点处没有向外的箭头。 运动员要到

32、达终点，但不要求路线(图)中的每一点都经过。但是路线(图)中的某些点是必经之点。上图的例子中，必经之点是：0，3，6，9。 任务A: 题目给出一个完整路线（图），请编程找出所有必经之点。请注意，输出必经之点时，应不包括起点和终点。任务B: 假定赛跑必须在相邻的2天来举行。因此，要把原来给定的完整路线（图）分成两个子路线（图）。第1天从点0出发，结束于“分裂点”。第2天从“分裂点”出发，结束于点N。 题目给出一个完整路线（图）C，请编程输出所有可能的“分裂点”（任务B）。“分裂点”S一定不是起点或终点。C可被S分成两个完整的子路线：这两个子路线没有公共的箭头线，并且S是这两个子路线的唯一公共点。

33、在上的例子中，仅点3是“分裂点”。54输入数据：输入数据描述一个完整路线（最多50个点，最多100个箭头），共n1行。前面n行描述箭头的终点，其中第i行中的每一个数字表示从点i（1in）出发的每一个箭头的终点，以2作为该行的结束。最后一行（第n+1行）中有一个数字1，表示输入结束。输出数据：输出两行数据，第1行表示必经点（子任务A）首先是必经点的总数，其后是必经点的标号，标号的顺序无关紧要。第2行表示“分裂点”：首先是分裂点的总数，其后是分裂点的标号，标号出现的先后顺序无关紧要（子任务B）。55分析必经点:是指运动员从起点0出发，沿箭头方向跑，无论走哪条路线，都经由该点到达终点N。所有这些点组

34、成必经点的集合。反之，在完整路线中去除必经点集合中的任一个点，无论运动员选择哪条路线跑，都不可能从起点0跑至终点N。分裂点: 某点是必经点； 在完整路线中去除这个必经点后，由起点出发的运动员无论如何也不会跑到由这个必经点出发的任一箭头的终点； 完整路线中去除这个必经点后的所有点，分成两个互为独立的集合: 可从出发点0到达。这些点组成子路径1； 无法从出发点0到达。这些点组成子路径2； 两个集合中的点之间，无任何箭头相连；56思路从点0开始，按逐层搜索的方法对删除当前判别点后的路线重复进行访问，直至找不到可访问的点为止。广度搜索的结果，将路线上的所有点(除当前判别点外)分为两个集合： 宽度优先搜

35、索中访问到的点，即从出发点0可达的点集合，设这些点到达标志； 宽度优先搜索中未访问过的点，即不可从出发点0到达的点集合。这些点设未到达标志；若终点N在第二个集合中，则当前判别点是必经点，然后再判别两个集合是否互为独立。若与必经点相连的所有点都在第二个集合中，且两个集合中的点之间无任何箭头相连，则这个必经点亦是分裂点。 57输入完整路线的相邻矩阵data1;For i1 to n-1 do /顺序设点1、点2，点N1为当前判别点 begin datadata1; /删除顶点i，构建新图的相邻矩阵data； for j1 to n do begin datai,j0; dataj,i0 end; BFS(0)； /宽