day3搜索-曹利国-noip培训

搜索算法搜索算法的基本思想搜索是计算机解题中常用的方法，它实质上是枚举法的应用。由于它相当于枚举法，所以其效率是相当地低。因此，为了提高搜索的效率，人们想出了很多剪枝的方法，如分枝定界，启发式搜索等等。在竞赛中，我们不仅要熟练掌握这些方法，而且要因地制宜地运用一些技巧，以提高搜索的效率。定义：FunctionExpendNode(Situation:Tsituation;ExpendWayNo:Integer):TSituation;表示对给出的节点状态Sitution采用第ExpendWayNo种扩展规则进行扩展，并且返回扩展后的状态。基本搜索算法一【回溯算法】回溯算法是采用了一种“走不通就掉头”思想作为其控制结构，用先根遍历的方法来构造解答树，可用于找所有解以及最优解。回溯算法对空间的消耗较少，当其与分枝定界法一起使用时，对于所求解在解答树中层次较深的问题有较好的效果。但应避免在后继节点可能与前继节点相同的问题中使用，以免产生循环。基本搜索算法一【回溯算法】Type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(p≤26)个字母中选取，使得没有相邻的子序列相等。例如p=3，n=5时‘abcba’满足条件‘abcbc’不满足条件输入：n，p输出：所有满足条件的字串分析状态：待扩展的字母序号at。实际上字串s亦参与了递归运算，但是由于该变量的存储量太大，因此我们将s设为全局变量；边界条件和目标状态：产生了一个满足条件的字串，即at=n+1；搜索范围：第at位置可填的字母集{‘a’..chr(ord(‘a’)+p-1)}；约束条件：当前字串没有相邻子串相等的情况varn，p：integer；{字串长度和可选字母的个数}tl：longint；{满足条件的字串数}ed：char；{可选字母集中的最大字母}s：string；{满足条件的字串}proceduresolve(at：integer)；{递归扩展第at个字母}varch：char；i：integer；beginifat=n+1{若产生了一个满足条件的字串，则输出，满足条件的字串数+1}thenbeginwriteln(f，s)；inc(tl)；exit{回溯}end；{then}forch←'a'toeddo{搜索每一个可填字母}begins←s+ch；i←1；{检查当前字串是否符合条件}while(i=atdiv2)and(copy(s，length(s)-i+1，i)copy(s，length(s)-2*i+1，i))doinc(i)；ifiatdiv2thensolve(at+1)；{若当前字串符合条件，则递归扩展下一个字母}delete(s，length(s)，1){恢复填前的字串}end{for}end；{solve}beginreadln(n，p)；{输入字串长度和前缀长短}ed←chr(ord('a')+p-1)；{计算可选字母集中的最大字母}s←''；tl←0；{满足条件的字串初始化为空，字串数为0}solve(1)；{从第1个字母开始递归计算所有满足条件的字串}writeln('Total：'，tl)；{输出满足条件的字串数}end.{main}基本搜索算法[深度搜索与广度搜索]深度搜索与广度搜索的区别：深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。在具体实现上为了提高效率,所以采用了不同的数据结构。广度搜索是求解最优解的一种较好的方法，而深度搜索多用于只要求解，并且解答树中的重复节点较多并且重复较难判断时使用，但往往可以用A*或回溯算法代替。搜索策略综合数据库与问题相关的所有数据元素构成的集合，用来表述问题状态或有关事实。产生式规则构建了综合数据库以后，还需要研究问题的移动规则，称为产生式规则。搜索策略搜索策略的实质是确定如何选取规则的方式。有两种基本方式：一种是不考虑给定问题所具有的特定知识，系统根据事先确定好某种固定顺序，依次调用规则或随机调用规则，这实际上是盲目搜索的方法。另一种是考虑问题领域可应用的知识，动态地确定规则的排列次序，优先调用较合适的规则使用，这就是通常所说的启发式搜索策略。一些基本概念节点：记录扩展的状态。弧/边：记录扩展的路径。搜索树：描述搜索扩展的整个过程。节点的耗散值令C(i,j)为从节点ni到nj的这段路径（或者弧）的耗散值,一条路径的耗散值就等于连接这条路径各节点间所有弧的耗散值总和。可以用递归公式描述如下：C(ni,t)=C(ni,nj)+C(nj,t)4搜索树根节点叶子节点4,5,6,7,88123567八数码问题在3*3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1—8中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格中移动，如右图所示。这样通过移动将牌就可以不断改变的布局结构，给出一个初始布局（称初始状态）和一个目标布局（称目标状态），问如何移动将牌，才能实现从初始状态到目标状态的转换。综合数据库{Pxy}，其中1=x,y=3，Pxy∈{0,1,2,3,4,5,6,7,8}，且Pxy互不相等用Pascal语言描述如下：typeT8no=array[1..3,1..3]ofinteger;{棋盘状态}TList=record{描述一个节点}Father:integer;{父指针}dep:byte;{深度}x,y:byte;{空格的位置}state:T8no;end;constMax=10000;vars,t:T8no;{s为初始状态，t为目标状态}List:array[0..max]ofTList;{综合数据库}产生式规则if条件then规则；设Pxy表示将牌第x行第y列的数码，m,n表示数码空格所在的行列值，记Pm,n=0,则可以得到如下四条规则：①ifn-1=1thenbeginPm,n:=Pm,n-1;Pm,n-1:=0end;②ifm-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;ConstDir:array[1..4,1..2]ofinteger{对应四种产生式规则}=((1,0),(-1,0),(0,1),(0,-1));控制策略PROCEDUREProduction-System；DATA初始化数据库Repeat在规则集中选择某一条可作用于DATA的规则RDATAR作用于DATA后得到的结果UntilDATA满足结束条件宽度优先搜索PROCEDUREBFS-SEARCH;(算法1)1.G:=G0;2.open:=(Source);3.closed:=nil;4.Repeat5.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;八数码问题扩展过程八数码搜索的主框架List[1]=source;closed:=0;open:=1;{初始化open,closed,List}Repeatclosed:=closed+1;n:=List[closed];{取出closed对应的节点}Forx:=1to4do[new:=Move(n,4);{按第x条规则扩展，得到new}ifnot_Appear(new,List)then{判重}[open:=open+1;List[open]:=new;{加入新节点到open}List[open].Father:=closed;{修改指针}ifList[open]=GoalthenGetOut;];]Untilclosedopen;八数码问题宽度优先算法框架List[1]=source;closed:=0;open:=1;{加入初始节点,List为扩展节点的表}Repeatclosed:=closed+1;n:=List[closed];{取出closed对应的节点}Forx:=1to4do[new:=Move(n,4);{对n节点使用第x条规则，得到new}ifnot_Appear(new,List)then[{如果new没有在List中出现}open:=open+1;List[open]:=new;{加入新节点到open}List[open].Father:=closed;{修改指针}ifList[open]=GoalthenGetOut;];]Untilclosedopen;八数码参考程序（宽度优先）program8no_bfs;{八数码的宽度优先搜索算法}ConstDir:array[1..4,1..2]ofinteger{四种移动方向，对应产生式规则}=((1,0),(-1,0),(0,1),(0,-1));n=10000;TypeT8no=array[1..3,1..3]ofinteger;TList=recordFather:integer;{父指针}dep:byte;{深度}X0,Y0:byte;{0的位置}State:T8no;{棋盘状态}end;VarSource,Target:T8no;List:array[0..10000]ofTList;{综合数据库}Closed,open,Best:integer{Best表示最优移动次数}Answer:integer;{记录解}Found:Boolean;{解标志}procedureGetInfo;{读入初始和目标节点}vari,j:integer;beginfori:=1to3doforj:=1to3doread(Source[i,j]);fori:=1to3doforj:=1to3doread(Target[i,j]);end;procedureInitialize;{初始化}varx,y:integer;beginFound:=false;Closed:=0;open:=1;withList[1]dobeginState:=Source;dep:=0;Father:=0;Forx:=1to3doFory:=1to3doifState[x,y]=0thenBeginx0:=x;y0:=y;End;end;end;FunctionSame(A,B:T8no):Boolean;{判断A,B状态是否相等}Vari,j:integer;BeginSame:=false;Fori:=1to3doforj:=1to3doifA[i,j]B[i,j]thenexit;Same:=true;End;functionnot_Appear(n