day3搜索-曹利国-noip培训

,搜索算法,搜索算法的基本思想,搜索是计算机解题中常用的方法，它实质上是枚举法的应用。由于它相当于枚举法，所以其效率是相当地低。因此，为了提高搜索的效率，人们想出了很多剪枝的方法，如分枝定界，启发式搜索等等。在竞赛中，我们不仅要熟练掌握这些方法，而且要因地制宜地运用一些技巧，以提高搜索的效率。定义：FunctionExpendNode(Situation:Tsituation;ExpendWayNo:Integer):TSituation;表示对给出的节点状态Sitution采用第ExpendWayNo种扩展规则进行扩展，并且返回扩展后的状态。,基本搜索算法一【回溯算法】,回溯算法是采用了一种“走不通就掉头”思想作为其控制结构，用先根遍历的方法来构造解答树，可用于找所有解以及最优解。回溯算法对空间的消耗较少，当其与分枝定界法一起使用时，对于所求解在解答树中层次较深的问题有较好的效果。但应避免在后继节点可能与前继节点相同的问题中使用，以免产生循环。,基本搜索算法一【回溯算法】,Node(节点类型)RecordSitutation:TSituation（当前节点状态）;Way-NO:Integer（已使用过的扩展规则的数目）;End,基本搜索算法一【回溯算法】,递归算法ProcedureBackTrack(Situation:TSituation;deepth:Integer);Vari:Integer;BeginIfdeepthMaxthen(空间达到极限,跳出本过程);IfSituation=Targetthen(找到目标);ForI:=1toTotalExpendMethoddoBeginBackTrack(ExpendNode(Situation,I),deepth+1);End-For;End;,构造字串生成长度为n的字串，其字符从26个英文字母的前p(p26)个字母中选取，使得没有相邻的子序列相等。例如p=3，n=5时abcba满足条件abcbc不满足条件输入：n，p输出：所有满足条件的字串,分析,状态：待扩展的字母序号at。实际上字串s亦参与了递归运算，但是由于该变量的存储量太大，因此我们将s设为全局变量；边界条件和目标状态：产生了一个满足条件的字串，即at=n+1；搜索范围：第at位置可填的字母集a.chr(ord(a)+p-1)；约束条件：当前字串没有相邻子串相等的情况varn，p：integer；字串长度和可选字母的个数tl：longint；满足条件的字串数ed：char；可选字母集中的最大字母s：string；满足条件的字串,proceduresolve(at：integer)；递归扩展第at个字母varch：char；i：integer；beginifat=n+1若产生了一个满足条件的字串，则输出，满足条件的字串数+1thenbeginwriteln(f，s)；inc(tl)；exit回溯end；thenforchatoeddo搜索每一个可填字母beginss+ch；i1；检查当前字串是否符合条件while(icopy(s，length(s)-2*i+1，i)doinc(i)；,ifiatdiv2thensolve(at+1)；若当前字串符合条件，则递归扩展下一个字母delete(s，length(s)，1)恢复填前的字串endforend；solvebeginreadln(n，p)；输入字串长度和前缀长短edchr(ord(a)+p-1)；计算可选字母集中的最大字母s；tl0；满足条件的字串初始化为空，字串数为0solve(1)；从第1个字母开始递归计算所有满足条件的字串writeln(Total：，tl)；输出满足条件的字串数end.main,基本搜索算法,深度搜索与广度搜索深度搜索与广度搜索的区别：深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。在具体实现上为了提高效率,所以采用了不同的数据结构。广度搜索是求解最优解的一种较好的方法，而深度搜索多用于只要求解，并且解答树中的重复节点较多并且重复较难判断时使用，但往往可以用A*或回溯算法代替。,搜索策略,综合数据库与问题相关的所有数据元素构成的集合，用来表述问题状态或有关事实。产生式规则构建了综合数据库以后，还需要研究问题的移动规则，称为产生式规则。搜索策略搜索策略的实质是确定如何选取规则的方式。有两种基本方式：一种是不考虑给定问题所具有的特定知识，系统根据事先确定好某种固定顺序，依次调用规则或随机调用规则，这实际上是盲目搜索的方法。另一种是考虑问题领域可应用的知识，动态地确定规则的排列次序，优先调用较合适的规则使用，这就是通常所说的启发式搜索策略。,一些基本概念,节点：记录扩展的状态。弧/边：记录扩展的路径。搜索树：描述搜索扩展的整个过程。节点的耗散值令C(i,j)为从节点ni到nj的这段路径（或者弧）的耗散值,一条路径的耗散值就等于连接这条路径各节点间所有弧的耗散值总和。可以用递归公式描述如下：C(ni,t)=C(ni,nj)+C(nj,t),八数码问题,在3*3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有18中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格中移动，如右图所示。这样通过移动将牌就可以不断改变的布局结构，给出一个初始布局（称初始状态）和一个目标布局（称目标状态），问如何移动将牌，才能实现从初始状态到目标状态的转换。,综合数据库,Pxy，其中1=1thenbeginPm,n:=Pm-1,n;Pm-1,n:=0end;ifn+1=3thenbeginPm,n:=Pm,n+1;Pm,n+1:=0end;ifm+1=3thenbeginPm,n:=Pm+1,n;Pm+1,n:=0end;ConstDir:array1.4,1.2ofinteger对应四种产生式规则=(1,0),(-1,0),(0,1),(0,-1);,控制策略,PROCEDUREProduction-System；DATA初始化数据库Repeat在规则集中选择某一条可作用于DATA的规则RDATAR作用于DATA后得到的结果UntilDATA满足结束条件,宽度优先搜索,PROCEDUREBFS-SEARCH;(算法1)1.G:=G0;2.open:=(Source);3.closed:=nil;4.Repeat5.IFOPEn=nilthenExit(Fail);6.n:=FIRST(OPEn);Remove(n,open);7.Add(n,closed);8.ifn=GoalthenExit(Success);9.mi:=Expand(n);10.对mi，舍去在G中已经出现的节点；11.将图中未出现的mi加入到open表的表尾12.Add(mi,G);13.Untilfalse;,八数码问题扩展过程,八数码搜索的主框架,List1=source;closed:=0;open:=1;初始化open,closed,ListRepeatclosed:=closed+1;n:=Listclosed;取出closed对应的节点Forx:=1to4donew:=Move(n,4);按第x条规则扩展，得到newifnot_Appear(new,List)then判重open:=open+1;Listopen:=new;加入新节点到openListopen.Father:=closed;修改指针ifListopen=GoalthenGetOut;Untilclosed=bestthenexit;最优化剪枝if(Liststep=Goal)and(stepbest)thenbest=step;记录当前最少步骤forx:=1to4do对使用第x条规则扩展new:=expand(Liststep,4);ifnot_Appear(new,List)then判重Liststep:=new;插入当前节点对new进行标号;Recursive(step);递归搜索下一层清除new的标号;PROCEDUREDFSList1:=Source;Best:=maxint;Recursive(1);输出,递归与非递归方式的比较,两种方式本质上是等价，但两者也时有区别的。递归方式实现简单，非递归方式较之比较复杂；递归方式需要利用栈空间，如果搜索量过大的话，可能造成栈溢出，所以在栈空间无法满足的情况下，选用非递归实现方式较好。,启发式搜索,启发式搜索是利用问题拥有的启发信息来引导搜索，达到减少搜索范围，降低问题复杂度的目的。这种利用启发信息的搜索过程称为启发式搜索方法。评价函数为了提高搜索效率，引入启发信息来进行搜索，在启发式搜索过程中，要对open表进行排序，这就需要有一种方法来计算待扩展节点有希望通向目标节点的程度，我们总希望能找到最有希望通向目标节点的待扩展节点优先扩展。一种常用的方法就是定义评价函数f(evaluationfuntion)对各个节点进行计算，其目的就是估算出“有希望”的节点来。,“不在位奖牌个数”作为启发信息的搜索过程,双向宽度优先搜索,双向宽度优先搜索注意的方面,规则必须可逆随时判重交叉扩展,搜索算法的优化,一、双向广度搜索二、分支定界三、A*算法,搜索算法的优化,一、双向广度搜索从正反两个方向进行广度搜索，理想情况下可以减少二分之一的搜索量，从而提高搜索速度。从初始状态和目标状态两个方向同时进行扩展，如果两棵解答树在某个节点第一次发生重合，则该节点所连接的两条路径所拼成的路径就是最优解。,搜索算法的优化,添加一张节点表，作为反向扩展表。在正向扩展出一个节点后，需在反向表中查找是否有重合节点。反向扩展时与之相同。,搜索算法的优化,对双向广度搜索算法的改进：略微修改一下控制结构，每次while循环时只扩展正反两个方向中节点数目较少的一个，可以使两边的发展速度保持一定的平衡，从而减少总扩展节点的个数，加快搜索速度。,搜索算法的优化,例题1：(最短编号序列)表A和表B各含k(k=20)个元素，元素编号从1到k。两个表中的每个元素都是由0和1组成的字符串。（不是空串）字符串的长度，则一条完成全部任务的路径是。,【分析】如果考虑从城市i出发，搜索所有相邻的城市，再根据当前所处的城市，确定任务的完成情况，从中找到最优解。这种搜索的效率极低。我们只需到达上货和下货的城市，其它的城市仅作为中间过程。因此，首先必须确定可能和不可能完成的任务，然后求出任意两城市间的最短路径。在搜索时，就只需考虑有货要上的城市，或者是要运到该城市的货全在车上两种情况。同时，还可以设定两个简单的槛值。如果当前费用+还需达的城市=当前最优解，或当前费用+返回城市1的费用=当前最优解，则不需继续往下搜索。,搜索剪枝应用举例,例题3：（多处理机调度问题）有n相同的处理机P1,P2Pn,和m个独立的作业J1,J2jm,处理机以互不相关的方式处理作业，现约定任何作业可以在任何一台处理机上运行，但未完工之前不允许中断作业，作业也不能拆分成更小的作业，已知作业Ji需要处理机处理的时间为Ti（i=1,2m）。编程完成以下两个任务：任务一：己知n、m和Ti（i=1,2m），求解一个调度方案，使得完成这m个作业的总工时最少并输出最少工时。任务二：给定作业时间表和限定完工时间，求在时间内完成这批作业所需最少处理机台数和调度方案。,搜索剪枝应用举例,【分析】此题有两种搜索方法：方法一：按顺序搜索每个作业。当搜索一个作业时，将其放在每台处理机搜索一次。方法二：按顺序搜索每台处理机。当搜索一台处理机时，将每个作业放在上面搜索一次。对比上述两种方法，可以发现：方法二较方法一更容易剪枝。,搜索剪枝应用举例,两种方法剪枝的对照：对于方法一：只能根据目前已确定的需时最长的处理机的耗时与目前最佳解比较。对于方法二：可约定Time1Time2Timen（Timei表示第i台处理机的处理时间）,从而可以设定槛值：如当前处理机的处理时间=目前最佳解，或剩下的处理机台数上一台处理机的处理时间剩余的作业需要的处理时间，则回溯。第二种方法显然是比第一种要好的。,搜索剪枝应用举例,第二种方法的深层探讨：对于任务一，首先可以用贪心求出Time1的上界。然后，还可以求出Time1的下界:UP（作业总时间/处理机台数）（UP表示大于等于该小数的最小整数）。搜索便从上界开始，找到一个解后，若等于下界即可停止搜索。对于任务二，可采用深度+可变下界。下界为：UP（作业总时间/限定时间），即至少需要的处理机台数。并设定Time1的上界为T。,搜索剪枝应用举例,例题4:有一个棋子，其1、6面2、4面3、5面相对。现给出一个M*N的棋盘，棋子起初处于(1,1)点，摆放状态给定，现在要求用最少的步数从(1,1)点翻滚到(M,N)点，并且1面向上。,搜索与其他算法的结合,【分析】这道题目用简单的搜索很容易发生超时，所以可以考虑使用动态规划来解题。对于一个棋子，其总共只有24种状态。在(1,1)点时，其向