枚举与搜索

枚举与搜索长沙市第一中学曹利国第一部分枚举策略枚举策略的基本思想枚举法，又称穷举法，指在一个有穷的可能的解的集合中，一一枚举出集合中的每一个元素，用题目给定的检验条件来判断该元素是否符合条件，若满足条件，则该元素即为问题的一个解；否则，该元素就不是该问题的解。枚举策略的基本思想枚举方法也是一种搜索算法，即对问题的所有可能解的状态集合进行一次扫描或遍历。在具体的程序实现过程中，可以通过循环和条件判断语句来完成。枚举法常用于解决“是否存在”或“有多少种可能”等类型的问题。虽然枚举法本质上属于搜索策略，但是它与回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：⑴可预先确定每个状态的元素个数n；⑵状态元素a1，a2，…，an的可能值为一个连续的值域。设ai1—状态元素ai的最小值；aik—状态元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k，ai1≤ai≤aik，……，an1≤an≤ankfora1←a11toa1kdofoa2←a21toa2kdo……………………forai←ai1toaikdo……………………foran←an1toankdoif状态(a1，…，ai，…，an)满足检验条件then输出问题的解；枚举策略的基本思想枚举法的特点是算法比较简单，在用枚举法设计算法时，重点注意优化，减少运算工作量。将与问题有关的知识条理化、完备化、系统化，从中找出规律，减少枚举量。枚举算法的应用例题1：二进制数的分类若将一个正整数转化为二进制数后，1的个数多于0的个数的这类数称为A类数，否则称为B类数。例如：（13）10=（1101）2，13为A类数；（10）10=（1010）210为B类数；（24）10=（11000）224为B类数；程序要求：求出1～1000之中（包括1与1000），全部A、B两类数的个数。此题是一道统计类题目。解决统计问题的一个常用方法是枚举法：逐一枚举所有情况，同时进行统计，枚举结束时，统计也完成，得到结果。具体对本题而言，采用枚举法的正确性与可行性是显然的，而本题的数据规模又仅为1～1000，所以采用逐一枚举方法进行统计的时间复杂度是完全可以接受的。分析例题2：模式识别的“中心”问题题目大意：实数矩阵由m行n列组成(1=m，n=100)，现给定实数矩阵，求其中心，若有多个“中心”，给出任意一个“中心”即可。中心(i，j)是使第i行上边元素(不包括第i行)的总和与第i行下边元素(不包括第i行)的总和之差的绝对值最小，而且第j列左边元素(不包括第j列)的总和与第j列右边元素(不包括第j列)的总和之差的绝对值最小。枚举算法的应用求矩阵的中心，即确定矩阵中心的行和列坐标，考虑到矩阵的对性，行坐标和列坐标的求法是类同的。下面是求矩阵中心行坐标的算法。求行坐标采用枚举法，枚举出所有可能的行坐标line，计算出line行上边元素和与下边元素和之差的绝对值difference，difference最小的行即为中心所在行。分析枚举过程可以描述为：min:=+∞;forline:=1tomdobegin求出line行上、下元素绝对值之差difference;ifmindifferencethenbeginmin:=difference;保存line作为矩阵中心所在行；end；end；枚举算法的应用例题3：围巾裁剪（NOI98）将一个边长为n(n=100)的大的正三角形均匀的分成n*n的小三角形，某些小三角形已经损坏。求出2个面积最大的（即包含小三角形个数最多的）2个子正三角形，要求这两个子正三角形中没有损坏的小三角形。枚举算法的应用三角形的分割必定将沿着其分割线分割。由于n〈=100，将每个分割线枚举一次，最多只有100*3条，所以可以考虑用枚举求解。枚举出分割线以后，我们当前最重要的任务就是如何求出上下2个三角形的最大子三角形。我们又可以使用枚举，以每一个点最为一次顶点，向下扩展，求出其可以扩展的最大面积。为了减少枚举次数，我们可以考虑将其值先计算并保存下来。分析定义变量：lup[I，j]表示以第I行j列的正放着的小三角形为上顶点的最大可扩展的面积。ldown[I，j]表示以第I行j列的倒放着的小三角形为下顶点的最大可扩展的面积。Up[I，j]表示第I行j列的正放着的小三角形是否损坏。down[I，j]表示以第I行j列的倒放着的小三角形是否损坏。分析容易得出lup，ldown[I，j]的递推式：min{lup[I+1,j],lup[I+1,j+1]}+1[down[I+1,j]=true]lup[I,j]:=1[down[I+1,j]=false]0[up[I,j]=false]边界：lup[n，I]：=1min{ldown[I-1,j],ldown[I-1,j-1]}+1[up[I-1,j]=true]ldown[I,j]:=1[up[I-1,j]=false]0[down[I,j]=false]求出了lup，ldown后，算法的设计就不难了。分析另外，还需要注意的一点是关于三角形60度的旋转。对于正放着的三角形：xx：=n-y+1yy：=x-（n-xx）对于倒放着的三角形：xx：=n-y+1yy：=x-1-（n-xx）分析例题4：圆桌骑士（IOI98）在一个8*8的棋盘上，有一个国王和若干个武士。其中，国王走一字步，骑士走马步。若国王与骑士相会在同一点上，国王可以选择让骑士背他走。求一个点，使所有的骑士和国王相距在这个点上的所走的步数最少。枚举算法的应用此题可从3个方面考虑：分治、枚举、数学方法。由于无法将这个问题划分为各自独立的小问题来解决，分治显然是不行的。又因武士和国王位置的不固定性和其走法的差异，推导不出一个数学公式。因此考虑使用枚举，需要枚举的三个要点：1、最后的汇聚点。2、国王与背他的骑士的汇聚点。3、国王与背他的骑士。分析国王最多只会与一个骑士结合，因为骑士的最终目标也是最终汇聚点，一旦国王与某个骑士汇合后，即马上可与其结合，剩下的只需要将所有的骑士汇合就可以了。更没有必要在中途中有将国王托付给其他的骑士。分析这样我们估算一下时间为O（8*8*8*8*63）=O（36*10^4）完全可以承受。另外，我们需要预先将2点之间走马字步的距离计算出来。可以使用Floyd或是Bfs。算法流程：dis[x1，y1，x2，y2]--（x1，y1）（x2，y2）之间的距离。ForI：=1to8do{枚举汇合点}Forj：=1to8dobeginAll：=所有骑士到这一点的和；Best:=min(best,all+国王到汇聚点的步数)Forx：=1to8do{枚举武士国王的相会点}Fory：=1to8dobeginForkk：=1tokdo{枚举与国王结合的武士}Ifdis[knight[kk].x,knight[kk].y,x,y]minthenbeginMin:=dis[knight[kk].x,knight[kk].y,x,y];Mink:=kk;End;End；Now:=all-mink武士走到汇合点的距离+mink武士走到汇聚点的距离+国王走到汇聚点的距离+从汇聚点到汇合点的距离；Best：=min（best，now）End；枚举方法的优化枚举算法的时间复杂度：状态总数*单个状态的耗时主要优化方法：⑴减少状态总数⑵降低单个状态的考察代价优化过程从以下几个方面考虑：⑴枚举对象的选取⑵枚举方法的确定⑶采用局部枚举或引进其他算法巧妙填数将1～9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三位数是第一行的两倍,第三行的三位数是第一行的三倍,应怎样填数。如图192384576分析本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合问题条件的即为解。因此可以采用枚举法。但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。枚举方法的优化例题5：设有下列的算式：208-------------□□)□□□□□□-------------□□□□□□-------------1要求：求出□中的数字，并打印出完整的算式。分析此题找不到很好的方法，于是考虑枚举法。本题中，待填数字的空格共有14个，每个格子中都可填0..9这10个数字。若对14个格子都进行0..9十个数字逐一枚举，枚举量是1014，不可能在指定的时间内得出结果。优化方法：减少枚举量，找出适当的元素进行枚举。分析由数学知识知道，在除法中只要知道被除数、除数、商和余数中的任意三部分就可以求得第四部分。本题已知商和余数，只要知道被除数或除数，整个算式也就确定下来了。而被除数和除数，分别是4位数和2位数。我们只需枚举除数。枚举量降为102=100，这个时间复杂度是完全可以承受的。枚举方法的优化例题6：方格填数问题。如图所示形状的八个方格中填入1-8这八个数字，使得相邻的和对角线上的数字之差不为1，编程求解所有的填法方案和总数。B1B2B3B4B5B6B7B8将1至8填入到B1至B8中，总共有8！＝40320种填法。该问题的枚举总量为8！个。由于B3和B6这两个方格与其相邻的格子共有6个，放入这两个格子中的数，必须和六个数不连续，这样的两个数只有1和8。B1，B3，B6，B8这四个格子中仅仅有两种可能放法，即：2，8，1，7和7，1，8，2。挖掘出这一隐含条件之后，B2，B4，B5，B7四个格子中的数就只能从3，4，5，6这四个数中进行选择，整个问题的枚举总量将变得只有2＊4！＝48种，从而大大地减少了枚举量，提高枚举效率。分析小结枚举方法是最简单的一种解题策略，也是最容易想到的一种方法，利用枚举法解题需要枚举出问题的解的所有状态，其致命的弱点便在于枚举量太大，从而导致算法效率十分低下。因此，在利用枚举法解题时，尽可能地减少枚举量，提高枚举效率。通过对问题的分析，挖掘出问题的隐含条件，尽可能排除那些明显不可能属于问题的解的状态，就是一个行之有效的办法。典型枚举试题1、Ioi98-3晚会彩灯布置2、CTSC97-2海岛3、Ioi93-1项链4、Ioi94-4时钟问题5、Noi93-1最长公共子串第二部分搜索算法搜索算法的基本思想搜索是计算机解题中常用的方法，它实质上是枚举法的应用。由于它相当于枚举法，所以其效率是相当地低。因此，为了提高搜索的效率，人们想出了很多剪枝的方法，如分枝定界，启发式搜索等等。在竞赛中，我们不仅要熟练掌握这些方法，而且要因地制宜地运用一些技巧，以提高搜索的效率。定义：FunctionExpendNode(Situation:Tsituation;ExpendWayNo:Integer):TSituation;表示对给出的节点状态Sitution采用第ExpendWayNo种扩展规则进行扩展，并且返回扩展后的状态。基本搜索算法一【回溯算法】回溯算法是采用了一种“走不通就掉头”思想作为其控制结构，用先根遍历的方法来构造解答树，可用于找所有解以及最优解。回溯算法对空间的消耗较少，当其与分枝定界法一起使用时，对于所求解在解答树中层次较深的问题有较好的效果。但应避免在后继节点可能与前继节点相同的问题中使用，以免产生循环。基本搜索算法一【回溯算法】TypeNode(节点类型)＝RecordSitutation:TSituation（当前节点状态）;Way-NO:Integer（已使用过的扩展规则的数目）;End基本搜索算法一【回溯算法】[递归算法]ProcedureBackTrack(Situation:TSituation;deepth:Integer);Vari:Integer;BeginIfdeepthMaxthen(空间达到极限,跳出本过程);IfSituation=Targetthen(找到目标);ForI:=1toTotalExpendMethoddoBeginBackTrack(Expe