广度优先搜索.docx

《广度优先搜索.docx》由会员分享，可在线阅读，更多相关《广度优先搜索.docx（20页珍藏版）》请在三一办公上搜索。

1、广度优先搜索深度优先搜索遍历算法 深度优先搜索的过程 深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的节点，如果它还有以此为起点而未搜索的边，就沿此边继续搜索下去。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v有那条边的始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被发现为止。即 以给定的某个顶点V0为起始点，访问该顶点； 选取一个与顶点V0相邻接且未被访问过的顶点V1，用V1作为新的起始点，重复上述过程； 当到达一个其所有邻接的顶点都已被访问

2、过的顶点Vi时，就退回到新近被访问过的顶点Vi- 1，继续访问Vi-1尚未访问的邻接点，重复上述搜索过程； 直到从任意一个已访问过的顶点出发，再也找不到未被访问过的顶点为止，遍历便告完成。 这种搜索的次序体现了向纵深发展的趋势，所以称之为深度优先搜索。 深度优先搜索算法描述： 程序实现有两种方式-递归与非递归。 一、递归 递归过程为： Procedure DEF-GO(step) for i:=1 to max do if 子结点符合条件 then 产生新的子结点入栈； if 子结点是目标结点 then 输出 else DEF-GO(step+1)； 栈顶结点出栈； endif； enddo；

3、 主程序为： Program DFS； 初始状态入栈； DEF-GO(1)； 二、非递归 Program DEF(step)； step:=0； repeat step:=step+1； j:=0；p:=false repeat j:=j+1； if 结点符合条件 then 第 1 页 共 17 页 产生子结点入栈； if 子结点是目标结点 then 输出 else p:=true； else if j=max then 回溯 p:=false； endif； until p=true； until step=0； 回溯过程如下： Procedure BACK； step:=step-1； i

4、f step0 then 栈顶结点出栈 else p:=true； 例如 八数码难题-已知个数的起始状态如图1，要得到目标状态为图1(）。 图 1 求解时,首先要生成一棵结点的搜索树，按照深度优先搜索算法，我们可以生成图1的搜索树。图中，所有结点都用相应的数据库来标记，并按照结点扩展的顺序加以编号。其中，我们设置深度界限为。粗线条路径表示求得的一个解。从图中可见，深度优先搜索过程是沿着一条路径进行下去，直到深度界限为止，回溯一步，再继续往下搜索，直到找到目标状态或OPEN表为空为止。 第 2 页 共 17 页 图1 程序： program No8_DFS; 八数码的深度优先搜索算法 Const

5、 Dir : array1.4,1.2of integer = (1,0),(-1,0),(0,1),(0,-1); maxN = 15; 可以承受的最大深度 Type T8No = array1.3,1.3of integer; tList = record state : T8No; x0,y0 : integer; end; Var Source,Target : T8No; List,Save : array0.maxNof tList; 综合数据库，最优解路径 Open,Best : integer; procedure GetInfo; 见程序1 Function Same(A,B

6、 : T8No):Boolean; 见程序1 function Not_Appear(New : tList):boolean; 见程序1 procedure Move(N : tList;d : integer;var ok : boolean;var New : tList); 见程序1 第 3 页 共 17 页 procedure GetOutInfo; 输出 var i,x,y : integer; begin writeln(total = ,best); for i:=1 to best+1 do begin for x:=1 to 3 do begin for y:=1 to 3

7、 do write(Savei.Statex,y, ); writeln; end; writeln; end; end; Procedure Recursive; 递归搜索过程 Var i : integer; New: tList; ok : boolean; Begin If Open-1=Best then exit; If Same(ListOpen.state,Target) then begin 如果找到解，保存当前最优解 Best:=Open-1; Save:=List; end; For i:=1 to 4 do begin 依次选用规则 Move(ListOpen,i,OK

8、,New); if ok and not_Appear(New) then begin 如果没有重复 inc(open); 插入综合数据库 ListOpen:=New; Recursive; 继续搜索 dec(Open); 退栈 End; End; End; procedure Main; 搜索主过程 var x,y : integer; begin List1.state:=Source; 初始化 for x:=1 to 3 do for y:=1 to 3 do if Sourcex,y=0 then begin List1.x0:=x; List1.y0:=y; end; Best:=M

9、axN; 第 4 页 共 17 页 Open:=1; Recursive; 开始搜索 If Best=maxint then writeln(No answer) Else GetOutInfo; end; Begin Assign(Input,input.txt);ReSet(Input); Assign(Output,Output.txt);ReWrite(Output); GetInfo; Main; Close(Input);Close(Output); End. 上面的八数码程序利用到了递归来实现，其实深度优先搜索还有一种无需递归的实现方式，下面我们介绍一下深度优先的一般实现方法：递

10、归算法和非递归算法。 递归算法伪代码： procedure DFS_ recursive(N); 1. if N=target then 更新当前最优值并保存路径; 2. for r:=1 to 规则数 do 3. New:=Expand(N,r) 4. if 值节点New符合条件 then 5. 产生的子节点New压入栈; 6. DFS_recursive(i+1); 7. 栈顶元素出栈; 8. 9. program DFS; 1. 初始化; 2. DFS_recursive(N); 非递归算法伪代码： procedure Backtracking; 1. dep:=dep-1; 2. if

11、 dep0 then 取出栈顶元素 3. else p:=true; program DFS; 1. dep:=0; 2. Repeat 3. dep:=dep+1; 4. j:=0;brk:=false; 5. Repeat 第 5 页 共 17 页 6. j:=j+1; 7. New=Expand(Trackdep,j); 8. if New 符合条件 then 9. 产生子节点New并将其压栈; 10. If 子节点New=target then 更新最优值并出栈 11. else brk:=true; 12. 13. else if j=规则数 then Backtracking 14

12、. else brk:=false; 15. Until brk=true 16. Until dep=0; 两种方式本质上是等价，但两者也时有区别的。 1 递归方式实现简单，非递归方式较之比较复杂； 递归方式需要利用栈空间，如果搜索量过大的话，可能造成栈溢出，所以在栈空间无法满足的情况下，选用非递归实现方式较好。 广度优先搜索遍历算法 一宽度优先搜索的过程 宽度优先搜索算法是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。 宽度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点

13、，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点，如此依次扩展，检查下去，直到发现目标节点为止。即 从图中的某一顶点V0开始，先访问V0； 访问所有与V0相邻接的顶点V1，V2，.，Vt； 依次访问与V1，V2，.，Vt相邻接的所有未曾访问过的顶点； 循此以往，直至所有的顶点都被访问过为止。 这种搜索的次序体现沿层次向横向扩长的趋势，所以称之为广度优先搜索。 二、广度优先搜索算法描述： Program Bfs； 初始化，初始状态存入OPEN表； 队列首指针hea

14、d:=0;尾指针tail:=1； repeat 指针head后移一位，指向待扩展结点； for I=1 to max do max为产生子结点的规则数 begin 第 6 页 共 17 页 if 子结点符合条件 then begin tail指针增1，把新结点存入列尾； if新结点与原已产生结点重复then删去该结点 else if新结点是目标结点then输出并退出； end; end; until(tail=head); 队列空 三、广度优先搜索注意事项： 1、每生成一个子结点，就要提供指向它们父亲结点的指针。当解出现时候，通过逆向跟踪，找到从根结点到目标结点的一条路径。 2、生成的结点要与

15、前面所有已经产生结点比较，以免出现重复结点，浪费时间，还有可能陷入死循环。 3、如果目标结点的深度与“费用”成正比，那么，找到的第一个解即为最优解，这时，搜索速度比深度搜索要快些；如果结点的“费用”不与深度成正比时，第一次找到的解不一定是最优解。 4、广度优先搜索的效率还有赖于目标结点所在位置情况，如果目标结点深度处于较深层时，需搜索的结点数基本上以指数增长。 下面我们看看怎样用宽度优先搜索来解决八数码问题。 例如 图2给出广度优先搜索应用于八数码难题时所生成的搜索树。搜索树上的所有结点都标记它们所对应的状态，每个结点旁边的数字表示结点扩展的顺序。粗线条路径表明求得的一个解。从图中可以看出，扩

16、展个结点和生成个结点之后，才求得这个解。此外，直接观察此图表明，不存在有更短走步序列的解。 图2 广度优先搜索图 第 7 页 共 17 页 程序实现算法： Program BFS； 建立数据库data；数据库赋初值； 设队列头指针H:=0；队列尾指针L:=1； repeat 取下一个H所指的结点； for i:=1 to max do i为产生新结点规则编号 begin L增1，把新结点存入数据库队尾；记录父结点的位置； if 新结点与原有结点重复 then 删去该结点(L减1) else if 新结点为目标结点 then 输出并退出； end； end； until H=L 队列为空 程序：

17、 program 8no_bfs; 八数码的宽度优先搜索算法 Const Dir : array1.4,1.2of integer 四种移动方向，对应产生式规则 = (1,0),(-1,0),(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 T

18、List; 综合数据库 Closed,Open,Best : integer Best表示最优移动次数 Answer : integer; 记录解 Found : Boolean; 解标志 procedure GetInfo; 读入初始和目标节点 var i,j : integer; 第 8 页 共 17 页 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

19、,y : integer; begin Found:=false; Closed:=0;Open:=1; with List1 do begin State:=Source;dep:=0;Father:=0; For x:=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:

20、=1 to 3 do if Ai,jBi,j then exit; Same:=true; End; function Not_Appear(New : tList):boolean; 判断New是否在List中出现 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 :

21、tList); 将第d条规则作用于N得到New,OK是New是否可行的标志 var x,y : integer; begin X := N.x0 + Dird,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);ReWri

22、te(Output); GetInfo; Initialize; Main; Close(Input);Close(Output); End. 例1 在一个瓶中装有80毫升化学溶剂，实验中需要精确地平分成两份，没有量具，只有两个杯子，其中一个杯子的容量是50毫升，另一个是30毫升，试设计一个程序将化学溶剂对分成两个40毫升，并以最少步骤给出答案。 分析:三个杯子水的初始状态为:、，生成新结点状态的方法为：将一个不空的杯子水倒入一个不满的杯中，且结点状态不重复，直到生成目标结点为止。 算法步骤: 数据库: 用数组d构成存放生成结点(杯子水状态)的队；数组p作为指向父结点的指针；t和s作为队头与队

23、尾指针。 结点的产生: (1)将结点中不空的杯子水倒入一个不满的杯子中，生成新的结点并记下父结点位置； (2)判断新结点是否已生成过， 以避免死循环； (3)生成的结点若为目标结点，输出。 搜索策略: 广度优先搜索。 源程序如下: 第 11 页 共 17 页 program ex3; type status= array 1.3 of integer; const v: array 1.3 of integer =(80，50,30); var d: array 1.200 of status; p: array 1.200 of integer; t,s,i,j: integer; proc

24、edure 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 do write(dmi,k:3); writeln; end; writeln(End.); halt; en

25、d; 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;是否为目标结点 begin 第 12 页 共 17 页 if (dw,1=40) and (dw,2=40) then

26、isobject:=true else isobject:=false; end; begin 生成新结点,将一个不空的杯子水倒入一个不满的杯子中 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,j+ds,i; ds,i:=0; if ds,jvj then begin ds,i:=ds,j-vj; ds,j:=vj; end; ps:=t;

27、if exampass(s) then begin if isobject(s) then draw(s); inc(s); end; end; inc(t); until t=s; writeln(NoWay); end. 例2 跳棋的原始状态如下图。其中0表示空格，-表示白子，+表示黑子，1-7表示棋盘格编号。跳棋的规则是： 任意一个棋子可移到相邻的空位上； 可跳过一个或两个棋子到空位上，与跳过的棋子的颜色无关； 棋子向左向右跳不限。 例如：4到1、5到4、3到5、6到3是成功的四步走法。请编一程序，用10步完成从原始状态跳变成目标状态。要求打印跳每一步后的状态。用数字表示棋盘格子的代号。

28、 1 2 3 4 5 6 7 原始位置 0 - - - + + + 目标位置 + + + - - - 0 分析:此题可以用广度与深度搜索两种方法求解，通过运行两种解法的程序，我们可以粗略地知道两种算法的区别。 算法步骤: 第 13 页 共 17 页 数据库：数组构成队，存放棋子的状态；数组作为指针指向其父结点位置；与分别表示队头与队尾指针。 结点的产生：与位置间距-3到3的棋子可移入空位，生成新结点状态。 搜索策略：广度优先搜索。 源程序如下: program ex143-1; 广度优先搜索 uses time; type status=string7; const start: status

29、 =0-+; obj: status =+-0; var a,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);输出 var m: array 1.10 of integer; i,j: integer; begin j:=0; while f1 do begin inc(j); mj:=f; f:=pf; end; writeln; writeln(Start: ,start); for i:=

30、j downto 1 do writeln(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;判断结点有否重复 var i: integer; begin 第 14 页 共 17 页 for i:=1 to w-1 do if gi=gw then begin exampass:=false; exit; end; exampass:=true; end;

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

32、rt: status =0-+; obj: status =+-0; var a,b,c: timetype; g: array 0.10 of status; 第 15 页 共 17 页 i,j,k: integer; procedure draw;输出 var i,j: integer; begin writeln(Start: ,start); for i:=1 to 10 do writeln(Step No.,i,: ,gi); writeln(End); gettimenow(b); howlong(a,b,c); printtime(Take Time: ,c); halt; e

33、nd; function exampass(w: integer): boolean;判断有否重复状态 var i: integer; begin for i:=1 to w-1 do if gi=gw then begin exampass:=false; exit; end; exampass:=true; end; procedure run(t: integer);搜索生成新结点 var i,k: integer; begin k:=pos(0,gt-1); for i:=-3 to 3 do if (i0) and (k+i=1) and (k+i=7) then begin gt:

34、=gt-1; gt,k:=gt,k+i; gt,k+i:=0; if exampass(t) then if gt=obj then draw else if t10 then run(t+1); end; end; begin gettimenow(a); g0:=start; run(1); 第 16 页 共 17 页 end. 运行两种算法程序可以发现，广度优先搜索运行速度比深度优先搜索快。 那么深度优先搜索与广度优先搜索算法有何区别呢？ 通常深度优先搜索法不全部保留结点，扩展完的结点从数据库中弹出删去，这样，一般在数据库中存储的结点数就是深度值，因此它占用空间较少。所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。 广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢