深搜广搜遍历算法

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

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

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

4、 p:=true ；例如 八数码难题-已知8个数的起始状态如图1(a),要得到目标状态为图1(b)28312316 48 47 57 6 5(a )( b )求解时，首先要生成一棵结点的搜索树，按照深度优先搜索算法，我们可以生成图1的搜索 树。图中，所有结点都用相应的数据库来标记，并按照结点扩展的顺序加以编号。其中，我们 设置深度界限为5。粗线条路径表示求得的一个解。从图中可见，深度优先搜索过程是沿着一 条路径进行下去，直到深度界限为止，回溯一步，再继续往下搜索，直到找到目标状态或OPEN表为空为止。分析钻研第16页训练提高图1深度优先搜索图程序：program No8_DFS;八数码的深度优

5、先搜索算法ConstDir : array1.4,1.2of integer = (1,0),(-1,0),(0,1),(0,-1);maxN = 15;TypeT8No = array1.3,1.3of integer;tList = recordstate : T8No;x0,y0 : integer;end;VarSource,Target : T8No;List,Save : array0.maxNof tList;Open,Best : integer;可以承受的最大深度综合数据库，最优解路径procedure GetInfo;见程序 1Function Same(A,B : T8N

6、o):Boolean;见程序 1function Not_Appear(New : tList):boolean;见程序 1procedure Move(N : tList;d : integer;var ok : boolean;var New : tList);见程序1procedure GetOutInfo;输出var i,x,y : integer; beginwriteln('total = ',best);for i:=1 to best+1 do beginfor x:=1 to 3 do beginfor y:=1 to 3 do write(Savei.Sta

7、tex,y,'');writeln;end;writeln;end;end;Procedure Recursive;Var i : integer;New: tList;ok : boolean;BeginIf Open-1>=Best then exit;If Same(ListOpen.state,Target) then begin Best:=Open-1;Save:=List;end;For i:=1 to 4 do beginMove(ListOpen,i,OK,New);if ok and not_Appear(New) then begin inc(ope

8、n);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:=MaxN; Open:=1; Recursive;开始搜索If Best=

9、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 dep>0 then取出栈顶元素3. else p:=true

11、;program DFS;1.dep:=0;2.Repeat3.dep:=dep+1;4.j:=0;brk:=false;5.Repeat6.j:=j+1;7.New=Expand(Trackdep,j);8.if New符合条件then 9.产生子节点New并将其压栈；10.If子甲点New=target then更新最优值并出栈11.1else brk:=true;12.13.else if j>=规则数then Backtracking14.1else brk:=false;15.Until brk=true16.Until dep=0;两种方式本质上是等价，但两者也时有区别的。1

12、. 递归方式实现简单，非递归方式较之比较复杂；递归方式需要利用栈空间，如果搜索量过大的话，可能造成栈溢出，所以在栈空间无法满 足的情况下，选用非递归实现方式较好。（二）广度优先搜索遍历算法一. 宽度优先搜索的过程宽度优先搜索算法（乂称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很 多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽 度优先搜索类似的思想。宽度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点 是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层 节点，并逐一检查第二层节点中

13、是否包含目标节点。若没有，再用算符逐一扩展第二层的所有 节点,，如此依次扩展，检查下去，直到发现目标节点为止。即1. 从图中的某一顶点V0开始，先访问V0;2. 访问所有与V0相邻接的顶点V1, V2, ., Vt;3. 依次访问与V1, V2, ., Vt相邻接的所有未曾访问过的顶点；4. 循此以往，直至所有的顶点都被访问过为止。这种搜索的次序体现沿层次向横向扩长的趋势，所以称之为广度优先搜索。二、广度优先搜索算法描述：Program Bfs ;初始化，初始状态存入OPENS;队歹0首指针head:=0;尾指针tail:=1 ；repeat指针head后移一位，指向待扩展结点；for I=1

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

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

16、短走步序列的解。（下图2广度优先搜索图）程序实现算法：Program BFS;建立数据库data ；数据库赋初值；设队歹0头指针H:=0;队歹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; 八数码的宽度优先搜索算法ConstDir : array1.4,1.2of integer=

17、(1,0),(-1,0),(0,1),(0,-1);N=10000;TypeT8No = array1.3,1.3of integer;TList = recordFather : integer;dep : byte;X0,Y0 : byte;State : T8No;end;VarSource,Target : T8No;List : array0.10000 of TList;Closed,Open,Best : integer Answer : integer;Found : Boolean;procedure GetInfo;var i,j : integer;beginfor i:

18、=1 to 3 do四种移动方向，对应产生式规则父指针深度0的位置棋盘状态综合数据库 Best表小最优移动次数记录解解标志读入初始和目标节点for j:=1 to 3 do read(Sourcei,j);for i:=1 to 3 dofor j:=1 to 3 do read(Targeti,j);end;procedure Initialize;初始化var x,y : integer;beginFound:=false;Closed:=0;Open:=1;with List1 do beginState:=Source;dep:=0;Father:=0;For x:=1 to 3 do

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

20、teger;beginNot_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;beginX := N.x0 + Dird,1;Y := N.y0 + Dird,2;判断New的可行性If not (X > 0) a

21、nd ( X < 4 ) and ( Y > 0 ) and ( Y < 4 ) then begin ok:=false;exit end;OK:=true;New.State:=N.State; New=Expand(N,d)New.StateX,Y:=0;New.StateN.x0,N.y0:=N.StateX,Y;New.X0:=X;New.Y0:=Y;end;procedure Add(new : tList);beginIf not_Appear(New) then Begin Inc(Open);ListOpen := New;end;end;插入节点New如果

22、New没有在List出现New加入Open表procedure Expand(Index : integer; var N : tList); var i : integer;New : tList;OK : boolean;BeginIf Same(N.State , Target) then beginFound := true;Best :=N.Dep;Answer:=Index;Exit;end;For i := 1 to 4 do beginMove(N,i,OK,New);if not ok then continue;New.Father := Index;New.Dep :=N

23、.dep + 1;Add(New);end;end;procedure GetOutInfo;procedure Outlook(Index : integer);var i,j : integer;beginif Index=0 then exit;Outlook(ListIndex.Father);with ListIndex dofor i:=1 to 3 do beginfor j:=1 to 3 do write(Statei,j,'');writeln;end;writeln;end;beginWriteln('Total = ',Best);Out

24、look(Answer);end;扩展N的子节点如果找到解依次使用4条规则输出递归输出每一个解procedure Main;(搜索主过程beginRepeatInc(Closed);Expand(Closed,ListClosed);扩展 ClosedUntil (Closed>=Open) or Found;If Found then GetOutInfo存在解else Writeln('No answer');无解end;BeginAssign(Input,'input.txt');ReSet(Input);Assign(Output,'Out

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

26、数组p作为指向父结点的指 针；t和s作为队头与队尾指针。2. 结点的产生：(1) 将结点中不空的杯子水倒入一个不满的杯子中，生成新的结点并记下父结点位置；(2) 判断新结点是否已生成过，以避免死循环；(3) 生成的结点若为目标结点，输出。3. 搜索策略：广度优先搜索。源程序如下:program ex3;typestatus= array 1.3 of integer;constv: array 1.3 of integer =(80, 50,30);vard: array 1.200 of status;p: array 1.200 of integer;t,s,i,j: integer;pr

27、ocedure draw(f: integer); 输出varm: array 1.20 of integer;i,j,k: integer;beginj：=0;while f<>1 do begininc(j);mj:=f;f:=pf;end;writeln;writeln('Start: ',d1,1:3,d1,2:3,d1,3:3);for i:=j downto 1 do beginwrite('Step No.',j+1-i,':');for k:=1 to 3 do write(dmi,k:3);writeln;end;w

28、riteln('End.');halt;end;function exampass(w: integer): boolean;新结点是否以前生成过 vari: integer;beginfor i:=1 to w-1 doif (di,1=dw,1) and (di,2=dw,2) and (di,3=dw,3)then beginexampass:=false;exit;end;exampass:=true;end;function isobject(w: integer): boolean;是否为目标结点beginif (dw,1=40) and (dw,2=40) the

29、n isobject:=trueelse isobject:=false;end;begin 生成新结点，将一个不空的杯子水倒入一个不满的杯子中d1,1:=80; d1,2:=0; d1,3:=0;p1:=0;t:=1; s:=2;repeatfor i:=1 to 3 doif dt,i<>0 thenfor j:=1 to 3 doif (i<>j) and (dt,j<>vj) then beginds:=dt;ds,j:=ds,j+ds,i;ds,i:=0;if ds,j>vj then beginds,i:=ds,j-vj;ds,j:=vj;

30、end;ps：=t;if exampass(s) then beginif isobject(s) then draw(s);inc(s);end;end;inc(t);until t>=s;writeln('NoWay');end.例2跳棋的原始状态如下图。其中"0"表示空格，"-"表示白子，"+"表示黑子，"1-7"表 示棋盘格编号。跳棋的规则是：1. 任意一个棋子可移到相邻的空位上；2. 可跳过一个或两个棋子到空位上，与跳过的棋子的颜色无关；3. 棋子向左向右跳不限。例如：4到1、5到4

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

32、e;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 f<>1 do begininc(j);mj:=f;f

33、:=pf;end;writeln;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-

34、1 doif gi=gw then beginexampass:=false;exit;end;exampass:=true;end;begin (生成新结点gettimenow(a);g1:=start; p1:=0;t:=1; s:=2;repeatk:=pos('0',gt);for i:=-3 to 3 doif (i<>0) and (k+i>=1) and (k+i<=7) then begings:=gt;gs,k:=gs,k+i; gs,k+i:='0'ps:=t;if exampass(s) then beginif gs=obj then draw(s);inc(s);end;end;inc(t);until t>=s;writeln('NoWay'); end.算法骤(二):1. 数据库：数组g构成堆栈，存放棋子的状态。2. 结点的产生：与空位置问距一3到3的棋子可移入空位，生成新结点状态3. 搜索策略：含有深度界限的深度优