深搜广搜遍历算法.doc

信息学资料算法 JOY深度优先搜索遍历算法深度优先搜索的过程深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的节点，如果它还有以此为起点而未搜索的边，就沿此边继续搜索下去。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v有那条边的始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被发现为止。即以给定的某个顶点V0为起始点，访问该顶点；选取一个与顶点V0相邻接且未被访问过的顶点V1，用V1作为新的起始点，重复上述过程；当到达一个其所有邻接的顶点都已被访问过的顶点Vi时，就退回到新近被访问过的顶点Vi-1，继续访问Vi-1尚未访问的邻接点，重复上述搜索过程；直到从任意一个已访问过的顶点出发，再也找不到未被访问过的顶点为止，遍历便告完成。这种搜索的次序体现了向纵深发展的趋势，所以称之为深度优先搜索。深度优先搜索算法描述：程序实现有两种方式-递归与非递归。一、递归递归过程为：Procedure DEF-GO(step)for i:=1 to max doif 子结点符合条件 then 产生新的子结点入栈；if 子结点是目标结点 then 输出else DEF-GO(step+1)；栈顶结点出栈；endif；enddo；主程序为：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；else if j=max then 回溯 p:=false；endif；until p=true；until step=0；回溯过程如下：Procedure BACK；step:=step-1；if step0 then 栈顶结点出栈else p:=true；例如八数码难题-已知个数的起始状态如图1（），要得到目标状态为图1(）。 （）（）求解时,首先要生成一棵结点的搜索树，按照深度优先搜索算法，我们可以生成图1的搜索树。图中，所有结点都用相应的数据库来标记，并按照结点扩展的顺序加以编号。其中，我们设置深度界限为。粗线条路径表示求得的一个解。从图中可见，深度优先搜索过程是沿着一条路径进行下去，直到深度界限为止，回溯一步，再继续往下搜索，直到找到目标状态或OPEN表为空为止。 图1 深度优先搜索图程序：program No8_DFS; 八数码的深度优先搜索算法Const 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 : T8No):Boolean; 见程序1 function Not_Appear(New : tList):boolean; 见程序1 procedure Move(N : tList;d : integer;var ok : boolean;var New : tList); 见程序1 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 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,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:=MaxN; 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.上面的八数码程序利用到了递归来实现，其实深度优先搜索还有一种无需递归的实现方式，下面我们介绍一下深度优先的一般实现方法：递归算法和非递归算法。递归算法伪代码：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 dep0 then 取出栈顶元素3. else p:=true;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. else brk:=true;12. 13. else if j=规则数 then Backtracking 14. else brk:=false;15. Until brk=true16. Until dep=0;两种方式本质上是等价，但两者也时有区别的。1 递归方式实现简单，非递归方式较之比较复杂；递归方式需要利用栈空间，如果搜索量过大的话，可能造成栈溢出，所以在栈空间无法满足的情况下，选用非递归实现方式较好。（二）广度优先搜索遍历算法一宽度优先搜索的过程宽度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。宽度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点，如此依次扩展，检查下去，直到发现目标节点为止。即从图中的某一顶点V0开始，先访问V0；访问所有与V0相邻接的顶点V1，V2，.，Vt；依次访问与V1，V2，.，Vt相邻接的所有未曾访问过的顶点；循此以往，直至所有的顶点都被访问过为止。这种搜索的次序体现沿层次向横向扩长的趋势，所以称之为广度优先搜索。二、广度优先搜索算法描述：Program Bfs；初始化，初始状态存入OPEN表；队列首指针head:=0;尾指针tail:=1；repeat 指针head后移一位，指向待扩展结点； for I=1 to max do max为产生子结点的规则数 begin if 子结点符合条件 then begin tail指针增1，把新结点存入列尾； if新结点与原已产生结点重复then删去该结点（取消入队，tail减1） else if新结点是目标结点then输出并退出； end;end; until(tail=head); 队列空三、广度优先搜索注意事项：1、每生成一个子结点，就要提供指向它们父亲结点的指针。当解出现时候，通过逆向跟踪，找到从根结点到目标结点的一条路径。2、生成的结点要与前面所有已经产生结点比较，以免出现重复结点，浪费时间，还有可能陷入死循环。3、如果目标结点的深度与“费用”（如：路径长度）成正比，那么，找到的第一个解即为最优解，这时，搜索速度比深度搜索要快些；如果结点的“费用”不与深度成正比时，第一次找到的解不一定是最优解。4、广度优先搜索的效率还有赖于目标结点所在位置情况，如果目标结点深度处于较深层时，需搜索的结点数基本上以指数增长。下面我们看看怎样用宽度优先搜索来解决八数码问题。例如图2给出广度优先搜索应用于八数码难题时所生成的搜索树。搜索树上的所有结点都标记它们所对应的状态，每个结点旁边的数字表示结点扩展的顺序。粗线条路径表明求得的一个解。从图中可以看出，扩展个结点和生成个结点之后，才求得这个解。此外，直接观察此图表明，不存在有更短走步序列的解。（下图2广度优先搜索图）程序实现算法：Program 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),(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; 解标志 procedure 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:=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中出现 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,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 在一个瓶中装有80毫升化学溶剂，实验中需要精确地平分成两份，没有量具，只有两个杯子，其中一个杯子的容量是50毫升，另一个是30毫升，试设计一个程序将化学溶剂对分成两个40毫升，并以最少步骤给出答案。分析:三个杯子水的初始状态为:、，生成新结点状态的方法为：将一个不空的杯子水倒入一个不满的杯中，且结点状态不重复，直到生成目标结点为止。【算法步骤:】数据库: 用数组d构成存放生成结点(杯子水状态)的队；数组p作为指向父结点的指针；t和s作为队头与队尾指针。结点的产生: (1)将结点中不空的杯子水倒入一个不满的杯子中，生成新的结点并记下父结点位置；(2)判断新结点是否已生成过， 以避免死循环；(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;procedure draw(f: integer);输出varm: array 1.20 of integer;i,j,k: integer;beginj:=0;while f1 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;writeln(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) then 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,i0 thenfor j:=1 to 3 doif (ij) and (dt,jvj) then beginds:=dt;ds,j:=ds,j+ds,i;ds,i:=0;if ds,jvj then beginds,i:=ds,j-vj;ds,j:=vj;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表示棋盘格编号。跳棋的规则是：任意一个棋子可移到相邻的空位上；可跳过一个或两个棋子到空位上，与跳过的棋子的颜色无关；棋子向左向右跳不限。例如：4到1、5到4、3到5、6到3是成功的四步走法。请编一程序，用10步完成从原始状态跳变成目标状态。要求打印跳每一步后的状态。用数字表示棋盘格子的代号。 1 2 3 4 5 6 7原始位置 0 - - - + + + 目标位置 + + + - - - 0分析:此题可以用广度与深度搜索两种方法求解，通过运行两种解法的程序，我们可以粗略地知道两种算法的区别。算法步骤:数据库：数组构成队，存放棋子的状态；数组作为指针指向其父结点位置；与分别表示队头与队尾指针。结点的产生：与位置间距-3到3的棋子可移入空位，生成新结点状态。搜索策略：广度优先搜索。源程序如下:program ex143-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;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-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 (i0) and (k+i=1) and (k+i=s;writeln(NoWay);end.算法骤(二):数据库：数组构成堆栈，存放棋子的状态。结点的产生：与空位置间距到的棋子可移入空位，生成新结点状态。搜索策略：含有深度界限的深度优先搜索。源程序如下:program ex143-2; 深度优先搜索uses time;typestatus=string7;con