广度(宽度)优先搜索l

广度（宽度）优先搜索深度搜索与广度搜索区分[深度搜索与广度搜索]•深度搜索与广度搜索的区别：深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。•在具体实现上为了提高效率,所以采用了不同的数据结构。•广度搜索是求解最优解的一种较好的方法，而深度搜索多用于只要求解，并且解答树中的重复节点较多并且重复较难判断时使用，但往往可以用回溯算法代替。一些基本概念•节点：记录扩展的状态。•弧/边：记录扩展的路径。•搜索树：描述搜索扩展的整个过程。•节点的耗散值令C(i,j)为从节点ni到nj的这段路径（或者弧）的耗散值,一条路径的耗散值就等于连接这条路径各节点间所有弧的耗散值总和。可以用递归公式描述如下：C(ni,t)=C(ni,nj)+C(nj,t)4搜索树根节点叶子节点4,5,6,7,88123567广度优先搜索的过程广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。广度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。即⒈从图中的某一顶点V0开始，先访问V0；⒉访问所有与V0相邻接的顶点V1，V2，......，Vt；⒊依次访问与V1，V2，......，Vt相邻接的所有未曾访问过的顶点；⒋循此以往，直至所有的顶点都被访问过为止。这种搜索的次序体现沿层次向横向扩长的趋势，所以称之为广度优先搜索。广度搜索策略•综合数据库（变量设置）与问题相关的所有数据元素构成的集合，用来表述问题状态或有关事实。•产生式规则构建了综合数据库以后，还需要研究问题的移动规则，称为产生式规则。•搜索策略搜索策略的实质是确定如何选取规则的方式。有两种基本方式：一种是不考虑给定问题所具有的特定知识，系统根据事先确定好某种固定顺序，依次调用规则或随机调用规则，这实际上是盲目搜索的方法。另一种是考虑问题领域可应用的知识，动态地确定规则的排列次序，优先调用较合适的规则使用，这就是通常所说的启发式搜索策略。广度优先搜索算法描述：Programbfs；初始化，初始状态存入队列；队列首指针head:=0;尾指针tail:=1；repeat指针head后移一位，指向待扩展结点；fori:=1tomaxdobegin//max为产生子结点的规则数if子结点符合条件thenbegintail指针增1，把新结点存入列尾；if新结点与原已产生结点重复then删去该结点（取消入队，tail减1）elseif新结点是目标结点then输出并退出；end;end;until(head=tail);//队列为空广度优先搜索注意事项1、每生成一个子结点，就要提供指向它们父亲结点的指针。当解出现时候，通过逆向跟踪，找到从根结点到目标结点的一条路径。当然不要求输出路径，就没必要记父亲。2、生成的结点要与前面所有已经产生结点比较，以免出现重复结点，浪费时间，还有可能陷入死循环。3、如果目标结点的深度与“费用”（如：路径长度）成正比，那么，找到的第一个解即为最优解，这时，搜索速度比深度搜索要快些，在求最优解时往往采用广度优先搜索；如果结点的“费用”不与深度成正比时，第一次找到的解不一定是最优解。4、广度优先搜索的效率还有赖于目标结点所在位置情况，如果目标结点深度处于较深层时，需搜索的结点数基本上以指数增长。八数码问题在3*3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1—8中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格中移动，如图1所示。这样通过移动将牌就可以不断改变的布局结构，给出一个初始布局（称初始状态）和一个目标布局（称目标状态），问如何移动将牌，才能实现从初始状态到目标状态的转换。下面我们看看怎样用宽度优先搜索来解决八数码问题。图2给出广度优先搜索应用于八数码难题时所生成的搜索树。搜索树上的所有结点都标记它们所对应的状态，每个结点旁边的数字表示结点扩展的顺序。粗线条路径表明求得的一个解。从图中可以看出，扩展第２６个结点，总共生成４６个结点之后，才求得这个解。此外，直接观察此图表明，不存在有更短走步序列的解。八数码问题扩展搜索树综合数据库（变量设置）{Pxy}，其中1=x,y=3，Pxy∈{0,1,2,3,4,5,6,7,8}，且Pxy互不相等用Pascal语言描述如下：typet8no=array[1..3,1..3]oflongint;{棋盘状态}tList=record{描述一个节点}Father:longint;{父指针}dep:longint;{深度}x,y:longint;{空格的位置}state:t8no;end;constMax=10000;vars,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;ConstDir:array[1..4,1..2]oflongint{对应四种产生式规则}=((1,0),(-1,0),(0,1),(0,-1));控制策略PROCEDUREProduction-System；•DATA初始化数据库•Repeat•在规则集中选择某一条可作用于DATA的规则R•DATAR作用于DATA后得到的结果UntilDATA满足结束条件八数码问题宽度优先算法框架List[1]=source;closed:=0;open:=1;{加入初始节点,List为扩展节点的表}Repeatclosed:=closed+1;n:=List[closed];{取出closed对应的节点}Forx:=1to4dobeginnew:=move(n,4);{对n节点使用第x条规则，得到new}ifnot_appear(new,List)thenbegin{如果new没有在List中出现}open:=open+1;List[open]:=new;{加入新节点到open}List[open].Father:=closed;{修改指针}ifList[open]=GoalthenGetOut;end;enduntilclosedopen;八数码参考程序（宽度优先）•program8no_bfs;{八数码的宽度优先搜索算法}•Const•dir:array[1..4,1..2]oflongint{四种移动方向，对应产生式规则}•=((1,0),(-1,0),(0,1),(0,-1));•n=10000;•Type•T8no=array[1..3,1..3]oflongint;•TList=record•Father:longint;{父指针}•dep:longint;{深度}•X0,Y0:longint;{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;beginfori:=1to3doforj:=1to3doread(Source[i,j]);fori:=1to3doforj:=1to3doread(Target[i,j]);end;procedureInitialize;{初始化}varx,y:integer;beginFound:=false;Closed:=0;open:=1;withList[1]dobeginState:=Source;dep:=0;Father:=0;Forx:=1to3doFory:=1to3doifState[x,y]=0thenBeginx0:=x;y0:=y;End;end;end;functionnot_Appear(new:tList):boolean;{判断new是否在List中出现}vari:integer;beginnot_Appear:=false;fori:=1toopendoifSame(new.State,List[i].State)thenexit;not_Appear:=true;end;procedureMove(n:tList;d:integer;varok:boolean;varnew:tList);{将第d条规则作用于n得到new,OK是new是否可行的标志}varx,y:integer;beginX:=n.x0+Dir[d,1];Y:=n.y0+Dir[d,2];{判断new的可行性}ifnot((X0)and(X4)and(Y0)and(Y4))thenbeginok:=false;exitend;OK:=true;FunctionSame(A,B:T8no):Boolean;{判断A,B状态是否相等}Vari,j:integer;BeginSame:=false;Fori:=1to3doforj:=1to3doifA[i,j]B[i,j]thenexit;Same:=true;End;new.State:=n.State;{new=Expand(n,d)}new.State[X,Y]:=0;new.State[n.x0,n.y0]:=n.State[X,Y];new.X0:=X;new.Y0:=Y;end;procedureAdd(new:tList);{插入节点new}beginifnot_Appear(new)thenBegin{如果new没有在List出现}Inc(open);{new加入open表}List[open]:=new;end;end;procedureExpand(Index:integer;varn:tList);{扩展n的子节点}vari:integer;new:tList;OK:boolean;BeginifSame(n.State,Target)thenbegin{如果找到解}Found:=true;Best:=n.Dep;Answer:=Index;Exit;end;Fori:=1to4dobegin{依次使用４条规则}Move(n,i,OK,new);ifnotokthencontinue;new.Father:=Index;new.Dep:=n.dep+1;Add(new);end;end;procedureGetOutInfo;{输出}procedureOutlook(Index:integer);{递归输出每一个解}vari,j:integer;beginifIndex=0thenexit;Outlook(List[Index].Father);withList[Index]dofori:=1to3dobeginforj:=1to3dowrite(State[i,j],'');writeln;end;writeln;end;beginWriteln('Total=',Best);