广度优先搜索.docx

1、广度优先搜索广度优先搜索算法一宽度优先搜索的过程宽度优先搜索算法是最简便和常用的图形搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。宽度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点，如此依次扩展，检查下去，直到发现目标节点为止。即1、从图中的某一顶点V0开始，先访问V0；2、访问所有与V0相邻接的顶点V1，

2、V2，.，Vt；3、依次访问与V1，V2，.，Vt相邻接的所有未曾访问过的顶点；4、循此以往，直至所有的顶点都被访问过为止。5、这种搜索的次序体现沿层次向横向扩长的趋势，所以称之为广度优先搜索。对同一层结点来说，一般按先生成先扩展的顺序进行，因此在数据结构上引入了“队列”结构。“队列” 是一种线性表，具有先进先出的特点，对于它所有的插入和删除操作分别仅在队列尾和队列首进行。二、广度优先搜索算法描述：Program Bfs；初始化，初始状态存入OPEN表；队列首指针head:=0;尾指针tail:=1；repeat 指针head后移一位，指向待扩展结点； for I=1 to max do ma

3、x为产生子结点的规则数 begin if 子结点符合条件 then begin tail指针增1，把新结点存入列尾； if新结点与原已产生结点重复then删去该结点（取消入队，tail减1） else if新结点是目标结点then输出并退出； end;end; until(tail=head); 队列空三、广度优先搜索注意事项：1、每生成一个子结点，就要提供指向它们父亲结点的指针。当解出现时候，通过逆向跟踪，找到从根结点到目标结点的一条路径。2、生成的结点要与前面所有已经产生结点比较，以免出现重复结点，浪费时间，还有可能陷入死循环。3、如果目标结点的深度与“费用”（如：路径长度）成正比，那么，

4、找到的第一个解即为最优解，这时，搜索速度比深度搜索要快些；如果结点的“费用”不与深度成正比时，第一次找到的解不一定是最优解。4、广度优先搜索的效率还有赖于目标结点所在位置情况，如果目标结点深度处于较深层时，需搜索的结点数基本上以指数增长。下面我们看看怎样用宽度优先搜索来解决八数码问题。例如图2给出广度优先搜索应用于八数码难题时所生成的搜索树。搜索树上的所有结点都标记它们所对应的状态，每个结点旁边的数字表示结点扩展的顺序。粗线条路径表明求得的一个解。从图中可以看出，扩展个结点和生成个结点之后，才求得这个解。此外，直接观察此图表明，不存在有更短走步序列的解。图2广度优先搜索图程序实现算法：Prog

5、ram BFS；建立数据库data；数据库赋初值；设队列头指针H:=0；队列尾指针L:=1；repeat取下一个H所指的结点；for i:=1 to max do i为产生新结点规则编号beginL增1，把新结点存入数据库队尾；记录父结点的位置； if 新结点与原有结点重复 then 删去该结点(L减1)elseif 新结点为目标结点 then 输出并退出；end；end；until H=L 队列为空程序：program 8no_bfs; 八数码的宽度优先搜索算法Const Dir : array1.4,1.2of integer 四种移动方向，对应产生式规则 = (1,0),(-1,0),(

6、0,1),(0,-1); N=10000;Type T8No = array1.3,1.3of integer; TList = record Father : integer; 父指针 dep : byte; 深度 X0,Y0 : byte; 0的位置 State : T8No; 棋盘状态 end;Var Source,Target : T8No; List : array0.10000 of TList; 综合数据库 Closed,Open,Best : integer Best表示最优移动次数 Answer : integer; 记录解 Found : Boolean; 解标志 proc

7、edure GetInfo; 读入初始和目标节点 var i,j : integer; begin for i:=1 to 3 do for j:=1 to 3 do read(Sourcei,j); for i:=1 to 3 do for j:=1 to 3 do read(Targeti,j); end; procedure Initialize; 初始化 var x,y : integer; begin Found:=false; Closed:=0;Open:=1; with List1 do begin State:=Source;dep:=0;Father:=0; For x:=

8、1 to 3 do For y:=1 to 3 do if Statex,y=0 then Begin x0:=x;y0:=y; End; end; end; Function Same(A,B : T8No):Boolean; 判断A,B状态是否相等 Var i,j : integer; Begin Same:=false; For i:=1 to 3 do for j:=1 to 3 do if Ai,jBi,j then exit; Same:=true; End; function Not_Appear(New : tList):boolean; 判断New是否在List中出现，可用康

9、托展开实现映射，建立hash表，用O(1)的时间复杂度判重 var i : integer; begin Not_Appear:=false; for i:=1 to Open do if Same(New.State,Listi.State) then exit; Not_Appear:=true; end; procedure Move(N : tList;d : integer;var ok : boolean;var New : tList); 将第d条规则作用于N得到New,OK是New是否可行的标志 var x,y : integer; begin X := N.x0 + Dird

10、,1; Y := N.y0 + Dird,2; 判断New的可行性 If not (X 0) and ( X 0 ) and ( Y =Open) or Found; If Found then GetOutInfo 存在解 else Writeln(No answer); 无解 end;Begin Assign(Input,input.txt);ReSet(Input); Assign(Output,Output.txt);ReWrite(Output); GetInfo; Initialize; Main; Close(Input);Close(Output);End.例1 在一个瓶中装有

11、80毫升化学溶剂，实验中需要精确地平分成两份，没有量具，只有两个杯子，其中一个杯子的容量是50毫升，另一个是30毫升，试设计一个程序将化学溶剂对分成两个40毫升，并以最少步骤给出答案。(文件名：EX1.PAS)输出(EX1.OUT)：Start:80 0 0Step No.1:30 50 0Step No.2:30 20 30Step No.3:60 20 0Step No.4:60 0 20Step No.5:10 50 20Step No.6:10 40 30Step No.7:40 40 0End.分析:三个杯子水的初始状态为:、，生成新结点状态的方法为：将一个不空的杯子水倒入一个不满的

12、杯中，且结点状态不重复，直到生成目标结点为止。算法步骤:1、数据库: 用数组d构成存放生成结点(杯子水状态)的队；数组p作为指向父结点的指针；t和s作为队头与队尾指针。2、结点的产生: (1)将结点中不空的杯子水倒入一个不满的杯子中，生成新的结点并记下父结点位置；(2)判断新结点是否已生成过，以避免死循环；(3)生成的结点若为目标结点，输出。3、搜索策略: 广度优先搜索。源程序如下:program ex1;type status= array 1.3 of integer;const v: array 1.3 of integer =(80,50,30);var d: array 1.200

13、of status; p: array 1.200 of integer; t,s,i,j: integer;procedure draw(f: integer);输出var m: array 1.20 of integer; i,j,k: integer;begin j:=0; while f1 do begin inc(j); mj:=f; f:=pf; end; writeln; writeln(Start: ,d1,1:3,d1,2:3,d1,3:3); for i:=j downto 1 do begin write(Step No.,j+1-i,: ); for k:=1 to 3

14、 do write(dmi,k:3); writeln; end; writeln(End.); halt;end;function exampass(w: integer): boolean;新结点是否以前生成过var i: integer;begin for i:=1 to w-1 do if (di,1=dw,1) and (di,2=dw,2) and (di,3=dw,3) then begin exampass:=false; exit; end; exampass:=true;end;function isobject(w: integer): boolean;是否为目标结点be

15、gin if (dw,1=40) and (dw,2=40) then isobject:=true else isobject:=false;end;begin 生成新结点,将一个不空的杯子水倒入一个不满的杯子中 assign(output,ex1.out); rewrite(output); d1,1:=80; d1,2:=0; d1,3:=0; p1:=0; t:=1; s:=2; repeat for i:=1 to 3 do if dt,i0 then for j:=1 to 3 do if (ij) and (dt,jvj) then begin ds:=dt; ds,j:=ds,

16、j+ds,i; ds,i:=0; if ds,jvj then begin ds,i:=ds,j-vj; ds,j:=vj; end; ps:=t; if exampass(s) then begin if isobject(s) then draw(s); inc(s); end; end; inc(t); until t=s; writeln(NoWay); close(output);end.例2 跳棋的原始状态如下图。其中0表示空格，-表示白子，+表示黑子，1-7表示棋盘格编号。跳棋的规则是：任意一个棋子可移到相邻的空位上；可跳过一个或两个棋子到空位上，与跳过的棋子的颜色无关；棋子向左

17、向右跳不限。例如：4到1、5到4、3到5、6到3是成功的四步走法。请编一程序，用10步完成从原始状态跳变成目标状态。要求打印跳每一步后的状态。用数字表示棋盘格子的代号。 1 2 3 4 5 6 7原始位置 0 - - - + + + 目标位置 + + + - - - 0分析:此题可以用广度与深度搜索两种方法求解，通过运行两种解法的程序，我们可以粗略地知道两种算法的区别。算法步骤:数据库：数组构成队，存放棋子的状态；数组作为指针指向其父结点位置；与分别表示队头与队尾指针。结点的产生：与位置间距-3到3的棋子可移入空位，生成新结点状态。搜索策略：广度优先搜索。源程序如下:program ex143

18、-1; 广度优先搜索uses time;typestatus=string7;conststart: status =0-+;obj: status =+-0;vara,b,c: timetype;g: array 1.200 of status;p: array 1.200 of integer;i,j,k: integer;t,s: integer;procedure draw(f: integer);输出varm: array 1.10 of integer;i,j: integer;beginj:=0;while f1 do begininc(j);mj:=f;f:=pf;end;wr

19、iteln;writeln(Start: ,start);for i:=j downto 1 dowriteln(Step No.,j+1-i,: ,gmi);writeln(End);gettimenow(b);howlong(a,b,c);printtime(Time Take: ,c);halt;end;function exampass(w: integer): boolean;判断结点有否重复vari: integer;beginfor i:=1 to w-1 doif gi=gw then beginexampass:=false;exit;end;exampass:=true;e

20、nd;begin 生成新结点gettimenow(a);g1:=start; p1:=0;t:=1; s:=2;repeatk:=pos(0,gt);for i:=-3 to 3 doif (i0) and (k+i=1) and (k+i=s;writeln(NoWay);end.算法(二):1、数据库：数组构成堆栈，存放棋子的状态。2、结点的产生：与空位置间距到的棋子可移入空位，生成新结点状态。3、搜索策略：含有深度界限的深度优先搜索。源程序如下:program ex143-2; 深度优先搜索uses time;typestatus=string7;conststart: status =

21、0-+;obj: status =+-0;vara,b,c: timetype;g: array 0.10 of status;i,j,k: integer;procedure draw;输出vari,j: integer;beginwriteln(Start: ,start);for i:=1 to 10 dowriteln(Step No.,i,: ,gi);writeln(End);gettimenow(b);howlong(a,b,c);printtime(Take Time: ,c);halt;end;function exampass(w: integer): boolean;判断

22、有否重复状态vari: integer;beginfor i:=1 to w-1 doif gi=gw then beginexampass:=false;exit;end;exampass:=true;end;procedure run(t: integer);搜索生成新结点vari,k: integer;begink:=pos(0,gt-1);for i:=-3 to 3 doif (i0) and (k+i=1) and (k+i=7) then begingt:=gt-1;gt,k:=gt,k+i; gt,k+i:=0;if exampass(t) thenif gt=obj then

23、 drawelseif t10 then run(t+1);end;end;begingettimenow(a);g0:=start;run(1);end.运行两种算法程序可以发现，广度优先搜索运行速度比深度优先搜索快。那么深度优先搜索与广度优先搜索算法有何区别呢？通常深度优先搜索法不全部保留结点，扩展完的结点从数据库中弹出删去，这样，一般在数据库中存储的结点数就是深度值，因此它占用空间较少。所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些。