广度优先搜索1.docx

1、广度优先搜索1广度优先搜索12008年07月26日 星期六 下午 03:262 广度优先搜索 BFS 在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索， 本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生 的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。英语中用Breadth-First-Search表示，所以我们 也把广度优先搜索法简称为BFS。 1、广度优先搜索的基本思想 从图中某一顶点Vo出发，首先访问Vo相邻的所有未被访问过的顶点V1、V2、Vt；再依次访问与V1、V2、Vt相邻的且未被访

2、问过的所有顶点。如此继续，直到访问完图中所有的顶点。 如果用广度优先法对下图中结点进行搜索，从结点V1出发，先搜索处理 它的子结点V2和V3，即深度为2的结点；然后搜索深度为3的子结点V4、V5、V6、V7；最后搜索深度为4的 结点V8和V9。整个搜索的次序与结点产生的次序完全一致。深度 _V1_ 1 / V2 V3 2 / / V4 V5 V6 V7 3 / V8 V9 42.广度优先搜索基本算法： 1）从某个顶点出发开始访问，被访问的顶点作相应的标记，并输出访问顶点号； 2）从被访问的顶点出发，依次搜索与该顶点有边的关联的所有未被访问的邻接点，并作相应的标记。 3）再依次根据2）中所有被访

3、问的邻接点，访问与这些邻接点相关的所有未被访问的邻接点，直到所有顶点被访问为止。 【算法过程】procedure guangdu(i); begin write(i); vi:=true; insert(q,i);q是队列，i进队 repeat k:=delete(q)；出队 for j:=1 to n do if (ak,j=1) and (not vj) then begin write(j); vj:=true; insert(q,j); end; until 队列q为空; 【实际应用】：实际应用的算法流程图通常如下： 【问题描述】如下图，找出C1到C6的一条最短路径并求出其路程总长度(

4、采用广度优先搜索的顶点访问序列为C1,C2,C3,C4,C5,C6)。 【Pascal程序】program tu3bfs;type fg=set of 1.6;const link:array1.5,1.6 of integer=(0,4,8,0,0,0),(4,0,3,4,6,0),(8,3,0,2,2,0),(0,4,2,0,4,9),(0,6,2,4,0,4);var pnt,city:array1.10 of 0.6;flag:fg;r,k,head,tail:integer;procedure print;var n, i,cost,y:integer; s:array1.7 of

5、1.6;begin y:=tail;n:=0; cost:=0; while y0 do begin inc(n);sn:=y;y:=pnty end; writeln(minpath=,n-1); write(1); for i:=n-1 downto 1 do begin write(-,si); cost:=cost+linksi+1,si; end; writeln; writeln(cost=,cost); end;beginflag:=1;pnt1:=0; city1:=1;head:=0;tail:=1;repeathead:=head+1;k:=cityhead;for r:=

6、2 to 6 do if not(r in flag) and (linkk,r0) then begin inc(tail);citytail:=r; pnttail:=head; flag:=flag+r; if r=6 then begin print;halt end; end;until head=tail;readln;end. 22 广度优先搜索实例【例题】八数码难题(Eight-puzzle)。在3X3的棋盘上，摆有 8个棋子，在每个棋子上标有18中的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是，给出一种初始布局(初始状态)和目标布局(目标状态)，

7、找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。初始状态和目标状态如下：初始状态 目标状态 2 8 3 1 2 3 1 6 4 8 4 7 5 7 6 5求解本题我们可以分3步进行。 问题分析： 由于题目要找的解是达到目标的最少步骤，因此可以这样来设计解题的方法： 初始状态为搜索的出发点，把移动一步后的布局全部找到，检查是否有达到目标的布局，如果没有，再从这些移动一步的布局出发，找出移动两步后的所有布局，再判断是否有达到目标的。依此类推，一直到某布局为目标状态为止，输出结果。由于是按移动步数从少到多产生新布局的，所以找到的第一个目标一定是移动步数最少的一个，也就是最优解。 建立产生

8、式系统： (1)综合数据库。用3X3的二维数组来表示棋盘的布局比较直观。我们用Chi,j表示第i行第j列格子上放的棋子数字，空格则用0来表示。为了编程方便，还需存储下面3个数据：该布局的空格位置(Si，Sj)；初始布局到该布局的步数，即深度dep；以及该布局的上一布局，即父结点的位置(pnt)。这样数据库每一个元素应该是由上述几个数据组成的记录。 在程序中，定义组成数据库元素的记录型为：Typenoderecord ch：array1.3，1.3 of byte；存放某种棋盘布局 si,sj:byte； 记录此布局中空格位置 dep,pnt：byte；end； 因为新产生的结点深度(从初始布局

9、到该结点的步数)一般要比数据库中原有的结点深度大(或相等)。按广度优先搜索的算法，深度大(步数多)的结点后扩展，所以新产生的结点应放在数据库的后面。而当前扩展的结点从数据库前面选取，即处理时是按结点产生的先后次序进行扩展。这样广度优先搜索的数据库结构采用队列的结构形式较合适。我们用记录数组data来表示数据库，并设置两个指针：Head为队列的首指针，tail为队列的尾指针。 (2)产生规则。原规则规定空格周围的棋子可以向空格移动。但如果换一种角度观察，也可看作空格向上、下、左、右4个位置移动，这样处理更便于编程。设空格位置在(Si，sj)，则有4条规则： 空格向上移动： if si-1=1 t

10、hen chsi,sj:=chsi-1,sj；chsi-1,sj:=0 空格向下移动： if si+1=3 then si,sj:=chsi+1,sj；chsi+1,sj:=0 空格向左移动： if sj-1=1 then si,sj:=chsi,sj-1；chsi,sj-1:=0 空格向右移动： if sj+1=3 then si,sj:=chsi,sj+1；chsi,sj+1:=0 我们用数组Di和Dj来表示移动时行列的增量，移动后新空格的位置可表示为： nx:=si+di(r) ny:=sj+dj(r)其中，r=1,2,3,4为空格移动方向，且r 1 2 3 4 方向 左 上 右 下 d

11、i 0 -1 0 1 dj -1 0 1 0 (3)搜索策略。按照问题分析中提出的方法，算法设计如下：program num8； 程序中新布局与队列中已有布局是否重复，用dup函数检查；找到目标结点后，print过程负责打印出从初始态到目标态移动时各步的布局，bufn)是用来存放待输出的布局在队列中的位置。procedure print； 根据上述算法编制的程序如下：program num8_str1；uses Crt；type a33：array1.3，1.3 Of byte；3X3的二维数组，用于存放棋盘布局a4=array1.4 of shortint;node=record 定义数据库

12、中每个元素记录类型结构 ch: a33; si, sj: byte; pnt, dep: byte;end;const goal:a33 = (1,2,3), (8,0,4), (7,6,5); 目标布局start:a33 =(2,8,3), (1,6,4), (7,0,5); 初始布局di:a4=(0,-1, 0, 1);dj:a4=(-1, 0, 1, 0);var data:array1.100 of node; temp: node; r, k, ni, nj, Head, Tail, depth: integer; 变量depth存放当前搜索深度function check(k: i

13、nteger) :boolean; 检查某步移动是否可行beginhi:=temp.si+dik ; nj:=temp.sj+djk;if (ni in 1.3) and (nj in 1.3) 移动后新位置仍在棋盘中then check:=true else check:= false;end;function dupe: boolean; 检查队尾新存入布局是否已在队列中存在var i,j, k: integer;buf:boolean;Beginbuf:= false; i: = 0;变量将i依次指向队列中的各个布局(最后一个除外)的位置repeat inc(i) ;buf:= true

14、; for j:=1 to 3 do for k:=1 to 3 do if datai.chj,k datatail.chj,k datatail是队列中最后一个元素，即新产生的布局 then bur:= false;until buf or (i = tail-1); buf=truee新布局与队列中布局有重复dupe:= bufend;function goals: boolean; 比较是否达到目标布局状态var i,j :byte;begingoals:= true;for i:=1 to 3 do for j:=1 to 3 do if datatail.chi,j goa1i,j

15、 then goals:=false 未达到目标布局end;procedure trace;var i,j :byte;beginwrite( cl=, Head, op=, tail);writeln(dep=,depth,k=,k);fori:=1 to 3 dobegin for j:= 1 to 3 do write(datatail, chi,j); writeln end;end;procedure print; 输出移动步骤var buf: array1.100 of integer;数组buf存放起始态、目标态以及从起始态到目标态所经过的各态的位置i,j, k, n: inte

16、ger;beginn:= 1;i:= tail;buf1:= i; buf1中是目标布局在队列中位置repeat j:=datai.pnt; dataI.pnt的值是布局I的父结点的位置 inc(n); bufn:=j; i:=juntil i=0; 根结点(初态)的父结点为0，即I=0writeln( staps:, depth + 1);for i:= 1 to 3 do 打印棋盘布局begin for k:=n-1 down to 1 do begin for j:= 1 to 3 do write(databufk.chi,j); if i = 2 then write( - ) el

17、se write( ); end; writeln;end;readln; haltend; main program = beginHead:= 0; tail:= 1;with data1 do 队列中存入第一个元素(初始状态)begin ch:= start; si:= 3; sj:= 2; pnt:= 0; dep:= 0;end;repeat inc(Head);temp:=dataHead; 取队首记录 depth:= temp.dep; for r:= 1 to 4 do 对取出记录进行扩展 if check(r) then 布局中空格向某方向移动成功 begin inc(tai

18、l);datatail:= temp; 新产生布局存入队尾 with datatail do begin chsi,si:= chnj,nj; chni,nj:=0;si:=nj;si:=nj; pnt:=Head;记录此布局的上一布局在队列中的位置 dep:= depth + 1;记录本布局的搜索深度 end; trace; if dupe then dec(tail) dec(tail删除新产生的结点) else if goals then print; end; until Head=tail; 队列空 writeln(no solution);readlnend运行结果：283 283

19、 283 023 123 123164104184184084804705 765 765 765 765 765 上述程序产生的搜索各个布局图略。 从上面搜索图中可看出，程序执行时先产生深度为1的所有结点，然后再产生深度为2的所有结点，最后产生含有目标的深度为5的结点结束。先往横向扩展，再往纵向深入，这就是广度优先搜索法搜索过程。 从上例我们看出，广度优先搜索法可以求出步数最少的解，即深度最少的解。因此广度优先搜索法经常用于一些求最优解的问题中。 与深度优先搜索法类似，不同的问题用广度优先搜索法的基本算法都是一样的，但在数据库的表示方法上、在产生的结点是否符合条件上和重复的判断上可以有不同的

20、编程技巧，程序运行效率也会有所不同。以八数码问题为例，上面程序中用3X3的二维数组表示布局比较直观，但在判断有重复布局，判断是否达到目标布局方面，却增加了编程复杂性，同时也影响了运行速度。我们可以改用字符串形式来表示布局。例如初始布局表示为283164705，目标布局表示为“123804765”，即按行的顺序排列。 产生规则也必须作相应改动。设空格当前位置是Si，则有： (1)空格向上移动：空格的位置减3，即交换Si和Si3的字符； (2)空格向左移动：空格的位置减1，即交换Si和Si1的字符； (3)空格向右移动：空格的位置加1，即交换Si和Si1的字符； (4)空格向下移动：空格的位置加3

21、，即交换Si和Si3的字符； 如设规则编号为k，则上述四条规则可归纳为一条： 交换Si和Si+(2*k-5)的字符。其中，k=1为向上移动；k=2为向左移动；k=3是向右移动；k=4为向下移动。 布局用字符串表示后，使得判断重复和是否目标态变得十分简单，只需判断两个字符串是否相等就可以了。 【思考】试按照上述改进算法，编制出解八数码题的PASCAL程序。2-3 双向广度优先搜索广度优先搜索遵循从初始结点开始一层层扩展直到找到目标结点的搜索规则，它只能较好地解决状态不是太多的情况，承受力很有限。如果扩展结点较多，而目标结点又处在较深层，采用前文叙述的广度搜索解题，搜索量巨大是可想而知的，往往就会

22、出现内存空间不够用的情况。双向搜索和A算法对广度优先的搜索方式进行了改良或改造，加入了一定的“智能因素”，使搜索能尽快接近目标结点，减少了在空间和时间上的复杂度。(1)搜索过程有些问题按照广度优先搜索法则扩展结点的规则，既适合顺序，也适合逆序，于是我们考虑在寻找目标结点或路径的搜索过程中，初始结点向目标结点和目标结点向初始结点同时进行扩展，直至在两个扩展方向上出现同一个子结点，搜索结束，这就是双向搜索过程。出现的这个同一子结点，我们称为相交点，如果确实存在一条从初始结点到目标结点的最佳路径，那么按双向搜索进行搜索必然会在某层出现“相交”，即有相交点，初始结点一相交点一目标结点所形成的一条路径即

23、是所求路径。 例如：移动一个只含字母A和B的字符串中的字母，给定初始状态为(a)表，目标状态为(b)表，给定移动规则为：只能互相对换相邻字母。请找出一条移动最少步数的办法。AABBAA BAAAAB (a) (b) 解题分析：从初始状态和目标状态均按照深度优先搜索扩展结点，当达到以下状态时，出现相交点，如图1(a)，结点序号表示结点生成顺序。双向扩展结点：顺序 逆序 1 1 _AABBAA_ BAAAAB 2 / 3 2 / 3 _ABABAA_ AABABA ABAAAB BAAABA 4 / |5 6 7 / 8 4 /ABBAAA BAABAA ABAABA AAABBA AABAAB

24、AABAAB (a) 图1 (b) 顺序扩展的第8个子结点与逆序扩展得到的第4个子结点就是相交点，问题的最佳路径如图2。 AABBAAAABABAAABAABABAAABBAAAAB 图2 从搜索的结点来看，双向广度要简单得多。假设每一个子结点可以扩展的子结点数是X，不计约束条件，以完全X叉树计算，那么用广度优先搜索一个长度为I的最佳路径的解，共需要扩展结点X(XL-1)(X-1)。从双向搜索来看，设正个方向的搜索在第y层找到向交点，那么正向共搜索了X(XY-1)(X-1)，逆向扩展的结点数为(XL-y-1)(X-1)，两个方向共搜索了 X(XY+XL-Y-2)(X-1)。我们假设L为偶数，则

25、Y=L/2，双向搜索扩展的结点数约为单向搜索的2(XL/2+1)*100，相对减少(XL/2-1)(XL/2+1)*100。 当然这里只是作个粗略的比较，事实上在其它一般情况下，双向搜索搜索量都要比单向搜索来的少。(2)结点扩展顺序 双向扩展结点，在两个方向的扩展顺序上，可以轮流交替进行，但由于大部分的解答树并不是棵完全树，在扩展完一层后，下一层则选择结点个数较少的那个方向先扩展，可以克服两个方向结点生成速度不平衡的状态，明显提高搜索效率。(3)数据结构 单向广度优先搜索需建立两个表OPEN和CLOSED，用来存储生成结点和已扩展结点，双向搜索从两个方向进行扩展，我们建立两个二维表OPEN，C

26、LOSED，OPEN1，CLOSED1， OPEN2，CLOSED2分别存储两个方向上的生成结点和已扩展结点，OPEN仍然是具有“先进先出”的队列结构。为编程方便，我们采用基于广度优先搜索算法的双向，建立三个二维指针：Q1，Q2，Q3其作用如下： Q11，Q12：分别指向两个方向上当前待扩展层的第一个结点。 Q21，Q22：分别指两个方向上队尾新产生的结点。 Q31，Q32：分别指向两个方向上下一层的第一个结点位置。 为了区分当前搜索方向，设方向标志： t=1表示处于正向搜索，t=2表示处于逆向搜索。 Fail有一个方向搜索失败时，为真，并且结束搜索过程，否则为假。 I全局变量，指向当前要扩展

27、的结点。(4)算法描述Program DOUBFS； 初始化，初始结点，和目标结点分别进入OPEN1和OPEN2表； Q11:=1;Q21:=1;Q12:=1;Q22:=1； repeat if (Q21-Q11)Q2t)； 其中过程EXPEND(t)的结构如下： Procedure expand(t：integer)； Var j：integer； begin for j:=1 to n do n为最多后继状态数 begin 产生i点的第j个后继状态，将它加入到队尾(Q2t+1)； if新结点未与其上一层以上的所有点重复 then if isans(t) then 输出解；halt； else else将新点从队列中去掉；(Q2t-1) end； - end； 判断是否是相交点的过程isans(t)如下： function isans(t：integer)：Boolean； var j，t1：integer； begin if t=1 then t1:=2 else t1:=1； isans:=false； forj:=Q1t1 to Q2t1 do if Q2t=j Q2t新结点是相交点 then isans:=true；exit； end；(5)例题应用 【例1】魔方问题 在魔方风靡全