枚举与搜索教案.ppt

《枚举与搜索教案.ppt》由会员分享，可在线阅读，更多相关《枚举与搜索教案.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、枚举与搜索讲稿枚举与搜索讲稿长沙市雅礼中学长沙市雅礼中学 朱全民朱全民有关搜索的有关搜索的NOIP试题试题 神经网络神经网络(2003)-宽搜宽搜侦探推理侦探推理(2003)-枚举与优化枚举与优化传染病控制传染病控制(2003)-深搜与优化深搜与优化虫食算虫食算(2004)-深搜与优化深搜与优化火柴棒等式火柴棒等式(2008)-简单枚举简单枚举双栈排序双栈排序(2008)-二分图的搜索二分图的搜索 靶形数独靶形数独(2009)-深搜与优化深搜与优化 简单枚举法简单枚举法所谓枚举，即对可能的解集合一一列举。所谓枚举，即对可能的解集合一一列举。解题思路为：解题思路为：首先确定可能的解集合首先确定可

2、能的解集合抽象出解包含的参数，确定每个参数的数抽象出解包含的参数，确定每个参数的数据范围据范围对解的每个参数的数据范围采用循环语句对解的每个参数的数据范围采用循环语句一一枚举一一枚举 对每次枚举，根据题意给定的条件判定是对每次枚举，根据题意给定的条件判定是否解，是否是最优解。否解，是否是最优解。火柴棒等式 给你给你n根火柴棍，你可以拼出多少个形如根火柴棍，你可以拼出多少个形如“A+B=C”的等式？的等式？等式中的等式中的A、B、C是用火柴棍拼出的整数（若该数非零，是用火柴棍拼出的整数（若该数非零，则最高位不能是则最高位不能是0）。用火柴棍拼数字）。用火柴棍拼数字0-9的拼法如图所示：的拼法如图

3、所示：注意：注意：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根火柴组成数字：根火柴组成数字：1.不可能为不可能为10个个1；2.不可能不可能8个个1，1个个4；3.不可能为不可能为7个个1，2个个7或或1个个0

4、；4.5.C不会超过不会超过1000枚举答案枚举答案设设F(I)表示数为表示数为I时的火柴棍数时的火柴棍数FOR A=0 TO 1000 DO IF F(A)best then bestsum；这个算法枚举状态为这个算法枚举状态为O（n9）从减少重复计算入手从减少重复计算入手记记录录先先前前考考察察的的结结果果。在在统统计计长长方方体体2时时，只只要要将将长长方方体体1的的统统计计结结果果加上长方体加上长方体3就可以了，而不必按上述算法那样重新进行计算。就可以了，而不必按上述算法那样重新进行计算。考察过程改为考察过程改为 ：for xx1 to x2 do 计算长方体的体积计算长方体的体积 f

5、or yy1 to y2 do sumsum+mapx，y，z2；if sumbest then bestsum；调整最优解调整最优解由于利用了计算出的结果，整个算法的时间复杂度降为由于利用了计算出的结果，整个算法的时间复杂度降为O（n8）。）。3 3、提取恰当的信息、提取恰当的信息上上述述考考察察实实际际上上求求出出z z轴轴坐坐标标为为z z2 2的的平平面面中中矩矩形形（x1，y1，x2，y2）的的数数和和。我我们们将将这这个个数数和和记记为为value(a)value(a)value(A)=value(ABCD)+value(B)-value(BC)-value(A)=value(AB

6、CD)+value(B)-value(BC)-value(BD)value(BD)这这就就启启发发我我们们用用另另一一种种方方法法表表示示立立方方体体的的信信息息：设设recrecxx，y y，zz表表示示z z轴轴坐坐标标为为z z的的水水平平面面中中矩矩形形（1 1，1，x，y）的数和。）的数和。z z轴轴坐坐标标为为z z的的水水平平面面中中左左上上角角为为（x1，y1）、右右下下角角为为（x2，y2）的的矩矩阵阵的的数数和和为为recxrecx2 2，y y2 2，z+z+recrecxx1 1，y y1 1，z-recxz-recx2 2，y y1 1，z-recxz-recx1 1

7、，y y2 2，zzRecRec数组可以在输入数据的同时计算数组可以在输入数据的同时计算fillchar(recfillchar(rec，size(rec)size(rec)，0)0)；recrec数组初始化数组初始化 forforz1tondo逐层输入信息逐层输入信息forforx1tondo逐行输入逐行输入z平面的信息平面的信息forfory1tondo逐列输入逐列输入z平面上平面上x行的信息行的信息beginbegin read(mapx read(mapx，y y，z)z)；输入输入z z平面上（平面上（x,yx,y）中的数）中的数 if(x=1)and(y=1)if(x=1)and(

8、y=1)计算计算z z平面上以（平面上以（1 1，1 1）为左上角、（）为左上角、（x,yx,y）为右下角的矩形的数和）为右下角的矩形的数和 then rec1 then rec1，1 1，zzmap1map1，1 1，zz else if y=1 then recx else if y=1 then recx，y y，zzrecx-1recx-1，n n，z+mapxz+mapx，y y，zz else recx else recx，y y，zrecxzrecx，y-1y-1，z+mapxz+mapx，y y，zz；endend；forfor 这样，考察过程就可以改为这样，考察过程就可以改为

9、 sumsum+recxsumsum+recx2 2，y y2 2，z z2 2+recx+recx1 1，y y1 1，z z2 2-recx-recx2 2，y y1 1，z z2 2-recx-recx1 1，y y2 2，z z2 2；if sumbest then bestif sumbest then bestsumsum；时间复杂度降为时间复杂度降为O O（n n6 6）。）。如如果果长长方方体体a的的数数和和是是负负数数，则则长长方方体体a的的计计算算结结果果废废弃弃，考考察察长长方方体体b-a。因因为为长长方方体体b的的数数和和=长长方方体体b-a的的数数和和+长长方方体体a

10、的的数数和和，由由于于长长方方体体a的的数数和和为为负负，长长方方体体b-a的的数数和和一一定定大大于于等等于于长长方方体体b的的数数和和。由由此此可可见见，在在累累计计长长方方体体数数和和的的时时候候，只只要要由由上上而而下下地地枚枚举举长长方方体体下下底底面面的的z轴坐标即可。设轴坐标即可。设total(z)以以z轴轴坐坐标标为为z的的平平面面为为下下底底面面的的长长方体的最大数和方体的最大数和算法框架for x11 to n do 枚举所有可能的子平面枚举所有可能的子平面for x21 to n dofor y11 to n dofor y21 to n do begin total0；

11、以（以（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深度优先搜索深度优先搜索算法是搜索中的一种控制策略

12、，但深度优先搜索算法是搜索中的一种控制策略，但与枚举法不同的是，它是从初始状态出发，运用与枚举法不同的是，它是从初始状态出发，运用题目给出的条件、规则，按照题目给出的条件、规则，按照深度优先深度优先的顺序扩的顺序扩展所有可能情况，当所有可能情况都探索过且都展所有可能情况，当所有可能情况都探索过且都无法到达目标的时候，再回退到上一个出发点，无法到达目标的时候，再回退到上一个出发点，继续探索另一个可能情况，这种不断回头寻找目继续探索另一个可能情况，这种不断回头寻找目标的方法也称为标的方法也称为“回溯法回溯法”。深度搜索是求解特殊型计数题或较复杂的枚举题深度搜索是求解特殊型计数题或较复杂的枚举题中使

13、用频率最高的一种算法。中使用频率最高的一种算法。深度搜索算法的几个重要因素深度搜索算法的几个重要因素(1)状态状态:作为递归的值参。作为递归的值参。(2)边界条件边界条件:作为递归的结束条件，通常以作为递归的结束条件，通常以深度结束。深度结束。(3)递归范围递归范围:作为作为for循环的初值和终值。循环的初值和终值。(4)约束条件约束条件:满足解的条件。满足解的条件。(5)最优性要求：满足最优解的条件。最优性要求：满足最优解的条件。深度搜索的基本框架proceduredfs(当前状态当前状态)；beginif当前状态为边界当前状态为边界thenbeginif当前状态为最佳目标状态当前状态为最佳

14、目标状态then记下最优结果；记下最优结果；exit；回溯回溯end；fori算符最小值算符最小值to算符最大值算符最大值dobegin算符算符i作用于当前状态，扩展出一个子状态；作用于当前状态，扩展出一个子状态；标记标记子子状态路径；状态路径；if(子状态满足约束条件子状态满足约束条件)and(子状态满足最优性要求子状态满足最优性要求)thendfs(子状态子状态)；恢复子状态路径；恢复子状态路径；回溯回溯end；end；N皇后问题 在在N*N的棋盘上放置的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置两个皇后），编程

15、求解所有的摆放任一列和任一对角线上不能放置两个皇后），编程求解所有的摆放方法。方法。基本思想基本思想由于皇后的摆放位置不能通过某种公式来确定，因此由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置可以进行试探；对于每个皇后的摆放位置可以进行试探；按行放置皇后，每一行放一皇后；按行放置皇后，每一行放一皇后；对每一行所放置的皇后按列进行试探；对每一行所放置的皇后按列进行试探；若某个位置能放，则放，否则试放下一个位置若某个位置能放，则放，否则试放下一个位置若某一行没有任何一个位置可放，则表示前面的皇后若某一行没有任何一个位置可放，则表示前面的皇后没放好，需要回溯。没放好，需要回溯。

16、若若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 begin 放置第放置第i个皇后；个皇后；对放置皇后的位置进行标记；对放置皇后的位置进行标记；Try（i+1）对放置皇后的位置释放标记；对放置皇后的位置释放标记；end;end;边界条件设置边界条件设置怎样判断某列放置了皇后怎

17、样判断某列放置了皇后a:array1.MaxNofBoolean;竖线被控制标记竖线被控制标记怎样判断某对角线上放置了皇后怎样判断某对角线上放置了皇后b:array2.MaxN*2ofBoolean;左上到右下斜线被控制标记左上到右下斜线被控制标记c:array1-MaxN.MaxN-1ofBoolean;左下到右上斜线被控制标记左下到右上斜线被控制标记程序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:

18、=j;aj:=false;bi+j:=false;ci-j:=false;Try(i+1)aj:=true;bi+j:=true;ci-j:=true;end;end;给出一个矩阵及一些国都名：给出一个矩阵及一些国都名：okdublindublinalpgocevtokyorasmusmblondonoslondonromeyiblglrcbonnkrzurichparisoaibxmuzoslotpqglamvlima要要求求从从这这个个矩矩阵阵中中找找出出这这些些国国都都名名，并输出它们的起始位置及方向。并输出它们的起始位置及方向。寻找国都名 搜索的方向算法思想将将字字符符矩矩阵阵读读入入

19、到到二二维维数数组组，然然后后对对每每一一个个国国都都名名进进行行搜搜索索，首首先先需需要要在在矩矩阵阵中中找找到到国国都都名名的的第第一一个个字字符符，然然后后沿沿八八个个方方向向进进行行搜搜索索。直直到到找找到到国国都都名名为为止止。若若在在矩矩阵阵中中没没有找到，则输出相应的信息。有找到，则输出相应的信息。在搜索过程时，类似八皇后问题，建立一个标志数组，标在搜索过程时，类似八皇后问题，建立一个标志数组，标识已经搜索过的方向，在对八个方向搜索时，可以建立一识已经搜索过的方向，在对八个方向搜索时，可以建立一个方向数组，使得程序更加简洁明了个方向数组，使得程序更加简洁明了 ConstFx:Ar

20、ray1.8,1.2OfShortint定义八个方向定义八个方向=(0,1),(0,-1),(1,0),(-1,0),(1,-1),(-1,1),(1,1),(-1,-1);ProcedureWork(T,X,Y:Integer);搜索路径，搜索路径，T为国都名的字符位置，为国都名的字符位置，X，Y为当前搜索的坐标为当前搜索的坐标VarI:Integer;BeginIfT=Length(S)+1Thenbegin搜索完，打印输出搜索完，打印输出Out;exitend;ForI:=1To8Do八个方向进行搜索八个方向进行搜索BeginX:=X+FxI,1;Y:=Y+FxI,2;坐标变化坐标变化I

21、f(AX,Y=ST)And(BX,Y)ThenBeginW:=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;构造字串构造字串生成长度为生成长度为n的字串，其字符从的字串，其字符从26个英文字个英文字母的前母的前p(p26)个字母中选取，使得没有相个字母中选取，使得没有相邻的子序列相等。例如邻的子序列

22、相等。例如p=3，n=5时时 a b c b a满足条件满足条件 a b c b c不满足条件不满足条件输入：输入：n，p输出：所有满足条件的字串输出：所有满足条件的字串分析分析状态：待扩展的字母序号状态：待扩展的字母序号i。由于该变量的存储量太大，因此我们将由于该变量的存储量太大，因此我们将s设为设为全局变量；全局变量；边界条件：产生了一个满足条件的字串，即边界条件：产生了一个满足条件的字串，即 i=n+1；搜索范围：从搜索范围：从a开始的后开始的后p个字符；个字符；约束条件：当前字串没有相邻子串相等的情约束条件：当前字串没有相邻子串相等的情况况procedure solve(i:integ

23、er)；var j,k:integer；t:longint;begin if i=n+1 then 若产生了一个满足条件的字串，则输出若产生了一个满足条件的字串，则输出 begin writeln(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

24、solve(i+1)；若当前字串符合条件，则递归扩展下一个字母若当前字串符合条件，则递归扩展下一个字母 delete(s,length(s),1)恢复填前的字串恢复填前的字串 end;end;记忆化搜索记忆化搜索1.递归前对尚待搜索的信息进行预处理递归前对尚待搜索的信息进行预处理如果搜索对象是通过某种运算直接得出其结果的，那么搜索前一般需进行预处理通过相应运算将所有搜索对象的计算结果置入常量表，搜索过程中只要将当前搜索对象的结果值从常量表取出即可。2.记忆化搜索记忆化搜索如果解答树中存在一些性质相同的子树，那么，只要我们知道了其中一棵子树的性质，就可以根据这个信息，导出其它子树的性质。这就是自

25、顶向下记忆化搜索的基本思想。序关系计数序关系计数用用关关系系和和=将将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个数依序排列时有多少种关系。个数依序排列时有多少种关系。1、枚举所有序关系表达式、枚举所有序关系表达式由于类似于由于类似于a=b和和b=a的序关系表达式是的序关系表达式是等价的，为此，规定等号前面的大写字母在等价的，为此，规定等号前面的大写字母在ASCII表中的序号，必须比等号后面的字母序号表中的序号，必须比等号后

26、面的字母序号小。小。状态（状态（Step，First，Can）：其中）：其中Step表示当表示当前确定第前确定第Step个关系符号；个关系符号；First表示当前大写表示当前大写字母中最小字母的序号；字母中最小字母的序号；Can是一个集合，集合是一个集合，集合中的元素是还可以使用的大写字母序号中的元素是还可以使用的大写字母序号边界条件（边界条件（step=n）：即确定了最后关系符号）：即确定了最后关系符号搜索范围（搜索范围（Firstin）：枚举当前大写字母的序）：枚举当前大写字母的序号号约束条件（约束条件（i in Can）：序号为）：序号为i的大写字母可以的大写字母可以使用使用proced

27、ureCount(Step，First，Can)；从当前状态出发，递归计算序关系表达式数从当前状态出发，递归计算序关系表达式数beginifStep=nthenbegin若确定了最后一个关系符号，则输出统计结果若确定了最后一个关系符号，则输出统计结果foriFirsttondoifiinCanthenInc(Total)；Exit回溯回溯end；thenforiFirsttondo枚举当前的大写字母枚举当前的大写字母ifiinCanthenbegin序号为序号为i的大写字母可以使用的大写字母可以使用Count(Step+1，i+1，Can-i)；添等于号添等于号Count(Step+1，1，C

28、an-i)添小于号添小于号Endthenend；Count该算法的时间复杂度是该算法的时间复杂度是W(n!)2 2、粗略利用信息、粗略利用信息 若若已已经经确确定定了了前前k k个个数数，并并且且下下一一个个关关系系符符号号是是小小于于号号，这这时时所所能能产生的序关系数就是剩下的产生的序关系数就是剩下的n-kn-k个数所能产生的序关系数。个数所能产生的序关系数。设设i i个个数数共共有有FiFi种种不不同同的的序序关关系系，那那么么，由由上上面面的的讨讨论论可可知知，在在算算法法1 1中中，调调用用一一次次Count(Step+1Count(Step+1，1 1，Can-i)Can-i)之之

29、后后，TotalTotal的的增增量量应应该该是是Fn-StepFn-Step。这这个个值值可可以以在在第第一一次次调调用用Count(Step+1Count(Step+1，1 1，Can-Can-i)i)时时 求求 出出。而而 一一 旦旦 知知 道道 了了 Fn-StepFn-Step的的 值值，就就 可可 以以 用用TotalTotalTotal+Fn-Step Total+Fn-Step 代替调用代替调用Count(Step+1Count(Step+1，1 1，Can-i)Can-i)procedure Count(Stepprocedure Count(Step，FirstFirst，

30、Can)Can)；StepStep，FirstFirst，CanCan的含义同算法的含义同算法11 begin beginifStep=nthenbegin若确定了最后一个关系符号，若确定了最后一个关系符号，则输出统计结果则输出统计结果 for i for iFirst to n do if i in Can then Inc(Total)First to n do if i in Can then Inc(Total)；Exit Exit 回溯回溯 end end；thenthen for iFirst to n do for iFirst to n do 枚举当前的大写字母枚举当前的大写字

31、母 if i in Can if i in Can 序号为序号为i i的大写字母可以使用的大写字母可以使用 then beginthen begin Count(Step+1 Count(Step+1，i+1i+1，Can-i)Can-i)；添等于号添等于号 if Fn-Step=-1 if Fn-Step=-1 then begin then begin 第一次调用第一次调用 Fn-Step Fn-Step TotalTotal；Count(Step+1Count(Step+1，1 1，Can-i)Can-i)；添小于号添小于号 Fn-Step Fn-Step Total-Fn-Step F

32、n-Step=TotalTotal-Fn-Step Fn-Step=Total的增量的增量 end thenend thenelseTotalTotal+Fn-StepFn-Step已经求出已经求出 endthenend；count该算法实质上就是自顶向下记忆化方式的搜索，它的时间复杂度为该算法实质上就是自顶向下记忆化方式的搜索，它的时间复杂度为W(2W(2n n)。3 3、充分利用信息、充分利用信息在在搜搜索索的的过过程程中中，如如果果确确定定在在第第k个个大大写写字字母母之之后后添添加加第第一一个个小小于于号号，则则可得到下面两条信息：可得到下面两条信息：第第一一条条信信息息：前前k个个大

33、大写写字字母母都都是是用用等等号号连连接接的的。前前半半部部分分将将产产生生的的序序关关系数，就是系数，就是n个物体中取个物体中取k个的组合数个的组合数第二条信息：在此基础上继续搜索，将产生第二条信息：在此基础上继续搜索，将产生Fn-k个序关系表达式。个序关系表达式。这样，我们可以得到这样，我们可以得到Fn的递推关系式：的递推关系式：采用上述公式计算采用上述公式计算Fn的算法记为算法的算法记为算法3，它的时间复杂度是，它的时间复杂度是W(n2)。varvar Total Total ：CompComp；答案答案 F F ：array0.maxn of Comparray0.maxn of Co

34、mp；FiFi为为i i个数的序关系表达式个数个数的序关系表达式个数 i i，j j ：IntegerInteger；x x ：CompComp；beginbegin FillChar(F FillChar(F，Sizeof(F)Sizeof(F)，0)0)；FF初始化初始化 F0 1 F0 1；for i1 to n do beginfor i1 to n do begin递推递推F F数组数组 Fi 0 Fi 0；x1x1；for j1 to i do begin for j1 to i do begin 计算计算FiFi xx*(i-j+1)/j xx*(i-j+1)/j；Fi Fi+x

35、*Fi-jFi Fi+x*Fi-j Endfor Endfor end end；forfor writeln(Fn)writeln(Fn)；输出结果输出结果 end end；mainmain传染病控制传染病控制传染病的传播具有如下性质：传染病的传播具有如下性质：第第一一:它它的的传传播播途途径径是是树树型型的的，一一个个人人X X只只可可能能被被某某个个特特定定的的人人Y Y感感染染，只只要要Y Y不不得得病病，或或者者是是XYXY之之间间的的传传播播途途径径被被切切断，则断，则X X就不会得病。就不会得病。第第二二:这这种种疾疾病病的的传传播播有有周周期期性性，在在一一个个疾疾病病传传播播周

36、周期期之之内内，传染病将只会感染一代患者，而不会再传播给下一代。传染病将只会感染一代患者，而不会再传播给下一代。第第三三:在在一一个个疾疾病病传传播播周周期期内内，只只能能设设法法切切断断一一条条传传播播途途径径，而而没没有有被被控控制制的的传传播播途途径径就就会会引引起起更更多多的的易易感感人人群群被被感感染染（也也就就是是与与当当前前已已经经被被感感染染的的人人有有传传播播途途径径相相连连，且且连连接接途途径径没没有有被被切切断断的的人人群群）。当当不不可可能能有有健健康康人人被被感感染染时时，疾疾病病就就中中止止传传播播。所所以以，蓬蓬莱莱国国疾疾控控中中心心要要制制定定出出一一个个切切

37、断传播途径的顺序，以使尽量少的人被感染。断传播途径的顺序，以使尽量少的人被感染。你的程序要针对给定的树，找出合适的切断顺序你的程序要针对给定的树，找出合适的切断顺序。贪心我们首先来通过对样例数据和其它的一些比较简单的数据进我们首先来通过对样例数据和其它的一些比较简单的数据进行一些观察，很容易得到一种贪心的算法，对这种算法可做行一些观察，很容易得到一种贪心的算法，对这种算法可做如下的描述：如下的描述：1 1我们用我们用Sum(i)Sum(i)表示以表示以i i为根节点的子树上的节点总数。那么为根节点的子树上的节点总数。那么我们每次砍掉当前层中还未砍掉的节点里面使得我们每次砍掉当前层中还未砍掉的节

38、点里面使得Sum(i)Sum(i)取到取到最大值的那个节点；最大值的那个节点；2 2重复第重复第1 1步直到当前层中的节点为空。步直到当前层中的节点为空。一个反例随机化搜索1 1我们通过随机函数来选择即将被砍掉的节点，可以通过我们通过随机函数来选择即将被砍掉的节点，可以通过设置权值来使得算法更大可能地去选择设置权值来使得算法更大可能地去选择“看起来最优看起来最优”的的决策；决策；2 2重复第重复第1 1步直到当前层中的节点为空；步直到当前层中的节点为空；3 3对前两步执行多次并选取所得到的最优结果。对前两步执行多次并选取所得到的最优结果。这个算法被设计出来以后，就很难在构造出能使这个算法这个算

39、法被设计出来以后，就很难在构造出能使这个算法失败的数据了，因此在考场上能够设计出来这个算法就已失败的数据了，因此在考场上能够设计出来这个算法就已经很令人满意了，而事实也恰恰如此（这个算法可以通过经很令人满意了，而事实也恰恰如此（这个算法可以通过所有的测试数据）。所有的测试数据）。虫食算虫食算所谓虫食算，就是原先的算式中有一部分被虫子所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。的字母。BADC +CBDA DCCC 给出一个给出一个N进制的虫食算式，相同的字母代表相进制的虫食算式，相同的字母代表相同的数字，

40、不同的字母代表不同的数字。同的数字，不同的字母代表不同的数字。要求求出满足这个算式的唯一一组解，也就是字要求求出满足这个算式的唯一一组解，也就是字母和数字的一一对应关系母和数字的一一对应关系.解决方案解决方案1要求一一对应的关系，就可以枚举这些一要求一一对应的关系，就可以枚举这些一一对应的关系，找出符合的一项。这样，一对应的关系，找出符合的一项。这样，关系总数有关系总数有O(N!)个，最坏情况下必须枚举个，最坏情况下必须枚举所有的关系，并且加以判断，复杂度高达所有的关系，并且加以判断，复杂度高达O(N*N!)！优化大体上，从算式最后一位开始模拟运算情况，当可递推时大体上，从算式最后一位开始模拟

41、运算情况，当可递推时递推，不可递推则枚举。递推，不可递推则枚举。对于一竖列，先处理两个加数，当遇到的字母的值不确定对于一竖列，先处理两个加数，当遇到的字母的值不确定时，则枚举当前位（注意与前面的情况判重）；否则不作时，则枚举当前位（注意与前面的情况判重）；否则不作为处理和，当遇到的字母的值不确定时为处理和，当遇到的字母的值不确定时,可从加数部分确定可从加数部分确定的值来确定（注意与前面的情况判重和进位）；否则看加的值来确定（注意与前面的情况判重和进位）；否则看加数部分确定的值是否能得到和部分（注意进位）。引出矛数部分确定的值是否能得到和部分（注意进位）。引出矛盾就回溯。盾就回溯。例如它最后一位

42、的情况是例如它最后一位的情况是(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!)，但这种方法限制很多（相当于剪，但这种方法限制很多（相当于剪枝）。枝）。解决方案解决方案3两个两个M位数相加，可以按位相加，设第位数相加，可以按位相加，设第i位的进位位的进位xi=1,表

43、表示有进位，为示有进位，为xi表示没有进位。表示没有进位。BADC+CBDA DCCC 枚举每位是否进位，复杂度是枚举每位是否进位，复杂度是O(2n),(因为首位不可能进位，因为首位不可能进位，无须枚举无须枚举)。然后，用高斯消元法来解方程，复杂度是。然后，用高斯消元法来解方程，复杂度是O(n3)。总复杂度是。总复杂度是O(2n*n3)。优化在解决方案在解决方案3的基础上，我们可以对进位的枚举剪枝。的基础上，我们可以对进位的枚举剪枝。观察这个竖列：观察这个竖列：A+B=C，若无进位则有，若无进位则有A=C且且BC且且B=C.若能推导出若能推导出A=A（A,B为任何不相等字母），为任何不相等字母

44、），则当前的枚举不可行。可用递归枚举，从后向前枚举，则当前的枚举不可行。可用递归枚举，从后向前枚举，处理一个竖列时则用上述处理一个竖列时则用上述2个不等式，看是否矛盾。数个不等式，看是否矛盾。数据结构用邻接矩阵。（规定据结构用邻接矩阵。（规定A=B，在有向图中有边，在有向图中有边）。）。若加进不等式若加进不等式A=B，要加入所有，要加入所有x(x=A)=y(B=y)，枚举，枚举x,y，用，用O(n2)的时间。再判断是否有的时间。再判断是否有x=y.靶形数独靶形数独输入输入9*9的数，其中一些是空格，要求完成的数，其中一些是空格，要求完成 靶形数独，使得得到分数最大。靶形数独，使得得到分数最大。

45、搜索搜索剪枝剪枝首先是搜索顺序的控制首先是搜索顺序的控制.我们总是选择当前选择余地我们总是选择当前选择余地最小的格子进行搜索最小的格子进行搜索.如果有两个格子的选择范围一如果有两个格子的选择范围一样大样大,那么优先搜索尽量靠里的格子那么优先搜索尽量靠里的格子.这样可以使得搜这样可以使得搜索树的上端枝条尽量少索树的上端枝条尽量少,显著地减少了搜索树的节点显著地减少了搜索树的节点数数.优先搜索靠里的格子是为了尽快得到一个得分较优先搜索靠里的格子是为了尽快得到一个得分较高的解高的解,提高最优性剪枝的效率提高最优性剪枝的效率最优性剪枝最优性剪枝:设当前还没有填入的数字总和为设当前还没有填入的数字总和为

46、sum,当当前的得分为前的得分为cur,最优得分为最优得分为best,如果如果sum*10+cur=best,那么已经没有继续搜索的必要了那么已经没有继续搜索的必要了,剪枝剪枝.使用位运算来进行集合操作使用位运算来进行集合操作:计算选择范围大小计算选择范围大小,判断判断数字数字k能否放入能否放入(i,j).可以显著减小算法的常数可以显著减小算法的常数.宽度优先搜索宽度优先搜索算法也是搜索中的一种控制策略，宽度优先搜索算法也是搜索中的一种控制策略，它不像深度优先搜索那样一直往前搜索，直到找它不像深度优先搜索那样一直往前搜索，直到找到答案位置。到答案位置。宽度优先搜索是对每一步都扩展出所有可能的状

47、宽度优先搜索是对每一步都扩展出所有可能的状态，逐层往下搜索。态，逐层往下搜索。对于一般图而言，它从某个未被访问的顶点对于一般图而言，它从某个未被访问的顶点v出发出发,依次访问依次访问v的各个未曾访问过的邻接点的各个未曾访问过的邻接点,直到所有直到所有已被访问的邻接点都被访问到已被访问的邻接点都被访问到.要实现宽度优先，必须借助对列存放扩展的节点。要实现宽度优先，必须借助对列存放扩展的节点。宽度优先搜索算法框架procedure bfs(v);Init_queue(q);Visite(v);vistedv:=true;Insert_queue(q,w)；While not empty(q)do

48、取出队首元素取出队首元素 vFor 对所有对所有v扩展出来的元素扩展出来的元素wif not visitedw then visite(w);visitedw:=true;Insert_queue(q,w)delete_queue(q,v);街道赛跑街道赛跑下图给出了一个沿街道赛跑的路线。图中有许多点，给下图给出了一个沿街道赛跑的路线。图中有许多点，给以标号以标号0，1，N(此图中此图中N=9)，点之间可以用含箭，点之间可以用含箭头的线相连。标号为头的线相连。标号为0的点是起点；标号为的点是起点；标号为N的点为终点。的点为终点。含箭头的线表示单向通行的街道。运动员沿箭头所指方含箭头的线表示单向

49、通行的街道。运动员沿箭头所指方向从一个点跑向另一个点；在每一个点上，运动员可以向从一个点跑向另一个点；在每一个点上，运动员可以选择任何一个箭头选择任何一个箭头(向外的向外的)继续向前跑。继续向前跑。一个完整路线具有如下特点：一个完整路线具有如下特点：1路线中每一点都可从出发点到达；路线中每一点都可从出发点到达；2路线中每一点都可到达终点；路线中每一点都可到达终点；3终点处没有向外的箭头。终点处没有向外的箭头。运动员要到达终点，但不要求路线运动员要到达终点，但不要求路线(图图)中的每一点都经过。中的每一点都经过。但是路线但是路线(图图)中的某些点是必经之点。上图的例子中，必经中的某些点是必经之点

50、。上图的例子中，必经之点是：之点是：0，3，6，9。任务任务A:题目给出一个完整路线（图），请编程找出所有必题目给出一个完整路线（图），请编程找出所有必经之点。请注意，输出必经之点时，应不包括起点和终点。经之点。请注意，输出必经之点时，应不包括起点和终点。任务任务B:假定赛跑必须在相邻的假定赛跑必须在相邻的2天来举行。因此，要把原来天来举行。因此，要把原来给定的完整路线（图）分成两个子路线（图）。第给定的完整路线（图）分成两个子路线（图）。第1天从点天从点0出发，结束于出发，结束于“分裂点分裂点”。第。第2天从天从“分裂点分裂点”出发，结出发，结束于点束于点N。题目给出一个完整路线（图）题目给