Pascal广度优先搜索.ppt

09年暑假集训（二）,广度优先搜索,广度优先搜索概念,广度优先是另一种控制结点扩展的策略，这种策略优先扩展深度小的结点，把问题的状态向横向发展。广度优先搜索法也叫BFS法(BreadthFirstSearch)，进行广度优先搜索时需要利用到队列这一数据结构。,广度优先搜索算法适应范围,如果问题的解是由若干部选择构成的一个选择序列，题目要求我们用最少的步骤解决最优化的问题，这个时候我们一般考虑是否使用广度优先搜索。广度优先搜索具有很明确的解题结构，很容易掌握。让我们来看个例子！,重排九宫问题游戏,在一个3乘3的九宫中有1-8的8个数及一个空格随机摆放在其中的格子里。如下面左图所示。现在要求实现这样的问题：将该九宫调整为如下图右图所示的形式。调整规则是：每次只能将与空格（上，下或左，右）相临的一个数字平移到空格中。试编程实现。|2|8|3|1|2|3|-|1|4|8|4|7|6|5|7|6|5|,在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索，本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。,在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索，本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。,特别提示,在有些情况下，比如求最优秀解的时候，有时广度搜索比深度搜索好;一般来说广度优先搜索可以利用队列实现，主要用于求一种状态通过几种规定的操作以最小次的变换到另一种状态,广度优先搜索基本算法,1）从某个顶点出发开始访问，被访问的顶点作相应的标记，并输出访问顶点号；2）从被访问的顶点出发，依次搜索与该顶点有边的关联的所有未被访问的邻接点，并作相应的标记。3）再依次根据2）中所有被访问的邻接点，访问与这些邻接点相关的所有未被访问的邻接点，直到所有顶点被访问为止。,【算法过程框架】,procedureguangdu(i);beginwrite(i);vi:=true;insert(q,i);q是队列，i进队repeatk:=delete(q)；出队forj:=1tondoif(ak,j=1)and(notvj)thenbeginwrite(j);vj:=true;insert(q,j);end;until队列q为空;变化的就是每个节点的表示形式和扩展的策略,例一、分油问题,假设有3个油瓶，容量分别为4，3，1(斤)。开始时4斤油瓶是满的，另外两个是空的，请用这三个油瓶将倒出2斤的油来分析：由于每一次倒油都是从一个油瓶向另外一个油瓶倒油，要么向外倒油的油瓶倒空，要不接受倒油的油瓶道满。我们将三个油瓶编号，用三个油瓶的油表示当前状态，共有六种不同的倒油方法1-2;1-3;2-3;2-1;3-2;3-1;（相当于八种跳马的方案,回溯的条件是该状态在以前出现过，而我们现在不但要求出一种解，而且我们要的出最优化（操作次数最少的解），也就是我们要求我们搜索树的层最少),深度优先搜索:状态树,400,130,013,031,301,400,310,211,130,12,13,21,12,31,32,12,13,状态树(广度优先搜索）,4，0，0,1，3，0,3，0，1,4,0,0,1,2,1,1-2,1-3,0,3,1,1-3,2-3,2-1,在上面的状态树中，我们要注意下面几点1:对于每个当前的状态节点来说，可能有八种可能，但是有些可能我们可以预先处理处理。缩小该节点的度数（要求到出的酒杯非空），另外如果该节点已经被产生那么我们就不必在搜索下去了，我们利用队列来控制）；2：我们搜索的结束条件是搜索到有2着瓶油；3：因为我们要找到最优秀解，所以我们按照层来搜索,广度优先搜索所用的数据结构,DATA（状态）,OP（由何种操作变换而来),PRE(由何种状态变换来，即父节点）,初始状态,初始状态A操作结果,初始状态B操作结果,初始状态经过两次A的结果,0,1,2,B,1,A,A,FRONT,REAR,一:交通图问题,表示的是从城市A到城市H的交通图。从图中可以看出，从城市A到城市H要经过若干个城市。现要找出一条经过城市最少的一条路线。,分析该题,分析：看到这图很容易想到用邻接距阵来表示，0表示能走，1表示不能走。如图5。,利用队列广度搜索,首先想到的是用队的思想。我们可以a记录搜索过程，a.city记录经过的城市,a.pre记录前趋元素，这样就可以倒推出最短线路。具体过程如下：（1）将城市A入队，队首、队尾都为1。（2）将队首所指的城市所有可直通的城市入队（如果这个城市在队中出现过就不入队，可用一个集合来判断），将入队城市的pre指向队首的位置。然后将队首加1，得到新的队首城市。重复以上步骤，直到城市H入队为止。当搜到城市H时，搜索结束。利用pre可倒推出最少城市线路。,参考程序constju:array1.8,1.8of0.1=(1,0,0,0,1,0,1,1),(0,1,1,1,1,0,1,1),(0,1,1,0,0,1,1,1),(0,1,0,1,1,1,0,1),(1,1,0,1,1,1,0,0),(0,0,1,1,1,1,1,0),(1,1,1,0,0,1,1,0),(1,1,1,1,0,0,0,1);typer=record记录定义city:array1.100ofchar;pre:array1.100ofinteger;end;varh,d,i:integer;a:r;s:setofA.H;procedureout;输出过程beginwrite(a.cityd);repeatd:=a.pred;write(-,a.cityd);untila.pred=0;writeln;halt;end;,用数组合表示8个城市的相互关系,proceduredoit;beginh:=0;d:=1;a.city1:=A;a.pre1:=0;s:=A;repeat步骤2inc(h);队首加一，出队fori:=1to8do搜索可直通的城市if（juord(a.cityh)-64,i=0）and（not（chr（i+64）ins）then判断城市是否走过begininc(d);队尾加一，入队a.cityd:=chr(64+i);a.pred:=h;s:=s+a.cityd;ifa.cityd=Hthenout;end;untilh=d;end;begin主程序doit;end.输出：H-F-A,题二字串变换（NOIPG2.pas),问题描述:已知有两个字串A$,B$及一组字串变换的规则（至多6个规则）:A1$-B1$A2$-B2$规则的含义为：在A$中的子串A1$可以变换为B1$、A2$可以变换为B2$。例如：A$abcdB$xyz变换规则为：abc-xuud-yy-yz则此时，A$可以经过一系列的变换变为B$，其变换的过程为：abcd-xud-xy-xyz共进行了三次变换，使得A$变换为B$。输入:键盘输人文件名。文件格式如下：A$B$A1$B1$A2$B2$|-变换规则./所有字符串长度的上限为20。输出:输出至屏幕。格式如下：若在10步（包含10步）以内能将A$变换为B$，则输出最少的变换步数；否则输出NOANSWER!,三、骑士精神（Knight）,在一个55的棋盘上有12个白色的骑士和12个黑色的骑士，且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘：为了体现出骑士精神，他们必须以最少的步数完成任务。,输入文件：第一行有一个正整数T(T=10)，表示一共有N组数据。接下来有T个55的矩阵，0表示白色骑士，1表示黑色骑士，*表示空位。两组数据之间没有空行。输出文件：对于每组数据都输出一行。如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出1。SampleInput21011001*1110111010010000001011110*1011100101000100,题目四:移棋子,MFG投资公司发明了一种游戏棋盘，这个棋盘有15个孔，除了一个孔外，其它孔中都有一粒棋子。一粒棋子能沿着棋盘中的直线跳过一个或多个相邻的棋子到最近的一个空孔中，被跳过的棋子就被移出棋盘。在下面的图形中，位于12孔或者位于14号孔的棋子能跳入5号孔。如果位于12号孔的棋子跳过来，则位于8号孔的棋子就被移出棋盘，同样如果是位于14号孔的棋子跳过来，则位于9号孔的棋子就被移走了。,请你编写一个程序，找出用最少跳动序列移走其它棋子，除了最后一粒棋子留在初始的空孔中。如果这样的序列不存在，则程序要输出一行信息IMPOSSIBLE。,输入输入包含T个测试数据。输入文件的第一行给出了T。每一个测试数