广度优先搜索

1、广度优先搜索广度优先搜索在树中又叫按层次遍历，对于树而言，宽度广度优先搜索在树中又叫按层次遍历，对于树而言，宽度优先搜索的思路可以描述为：访问根结点，依次访问根结优先搜索的思路可以描述为：访问根结点，依次访问根结点的每一个子结点（第二层），再通过这些结点访问第三点的每一个子结点（第二层），再通过这些结点访问第三层结点层结点。广度优先与深度优先搜索相比，时间复杂度。广度优先与深度优先搜索相比，时间复杂度都是相同的，不同的仅仅在于结点访问的顺序不同。它们都是相同的，不同的仅仅在于结点访问的顺序不同。它们在完全遍历的问题上应该是差不多，但是在有些问题上，在完全遍历的问题上应该是差不多，但是在有些问题

2、上，比如求最优解，有时广度优先要比深度优先搜索好。比如求最优解，有时广度优先要比深度优先搜索好。为了求一个最优解，如果使用深度优先并不能保证找到的为了求一个最优解，如果使用深度优先并不能保证找到的解最优，只有搜索完整棵树，找到所有解，再比较它们的解最优，只有搜索完整棵树，找到所有解，再比较它们的优劣，才能从中求出最优解，这显然不如广度优先搜索简优劣，才能从中求出最优解，这显然不如广度优先搜索简单。单。一般来说广度优先搜索可以利用队列实现，主要用于解决一般来说广度优先搜索可以利用队列实现，主要用于解决求一种状态通过几种规定的操作以最少次数变换到另一种求一种状态通过几种规定的操作以最少次数变换到另

3、一种状态的问题。状态的问题。引例经过城市最少的一条路径状态描述（矩阵表示）：1表示不相邻 0表示相邻const ju:array1.8,1.8of 0.1=(1,0,0,0,1,0,1,1), (0,1,1,1,1,0,1,1), (0,1,1,0,0,1,1,1), (0,1,0,1,1,1,0,1), (1,1,0,1,1,1,0,0), (0,0,1,1,1,1,1,0), (1,1,1,0,0,1,1,0), (1,1,1,1,0,0,0,1);结点定义type node=record city:char;城市名称 pre:integer;父结点end;varhead,tail,i:i

4、nteger;队列首与队列尾a:array1.100of node;结点数s:arrayA.Hof boolean;城市数procedure out(d:integer);输出过程，通过每个结点的父结点来输出Begin write(ad.city); repeat d:=ad.pre; write(-,ad.city); until ad.pre=0; writeln;end;procedure doit;begin head:=0;tail:=1;入队 a1.city:=A;a1.pre:=0;初始化从A结点开始扩展 fillchar(s,sizeof(s),true);所有结点可用 rep

5、eat inc(head);队首加，出队 for i:=1 to 8 do访问可扩展的结点 if (juord(ahead.city)-64,i=0)and (schr(i+64)=true)then结点可用 begin inc(tail);入队 atail.city:=chr(64+i); atail.pre:=head;记住它的父结点以便输出 satail.city:=false;该结点标志为已用 if atail.city=H then判断是否到达目标结点 begin out(tail);输出 break;退出搜索，因为已找到最优解 end; end; until head=tail;e

6、nd;begin doit;end.主程序主程序小结广度优先搜索相当于钟摆！图2 搜索树扩展根节点叶子节点4,5,6,7,81112131415161718小结广度优先算法描述：Program bfs; 初始化，初始状态存入队列；队列首指针head:=0;尾指针tail:=1;While headtail do begin 指针head后移一位，指向待扩展的结点；for i:=1 to maxdo begin if 扩展出的新结点是目标结点 then 输出并退出；if 扩展出的新结点符合条件，并且新结点与原已产生的结点不重复 then tail指针加，把新结点存入队列尾；end;End;注意事

7、项注意事项、每生成一个子结点，就要提供指向它们父结点的指针。当、每生成一个子结点，就要提供指向它们父结点的指针。当解出现时，通过逆向跟踪，找到从根结点到目标结点的一条路解出现时，通过逆向跟踪，找到从根结点到目标结点的一条路径。径。、生成的结点要与前面所有已经产生的结点比较，以免出现、生成的结点要与前面所有已经产生的结点比较，以免出现重复结点，浪费时间和空间，还有可能陷入死循环。重复结点，浪费时间和空间，还有可能陷入死循环。、如果目标结点的深度与、如果目标结点的深度与“费用费用”（如路径长度）成正比，（如路径长度）成正比，那么找到的第一个解即为最优解，这时，搜索速度比深度搜索那么找到的第一个解即

8、为最优解，这时，搜索速度比深度搜索要快些。如果结点的要快些。如果结点的“费用费用”不与深度成正比时，第一次找到不与深度成正比时，第一次找到的解不一定是最优解。的解不一定是最优解。、广度优先搜索的效率还有赖于目标结点所在位置情况，如、广度优先搜索的效率还有赖于目标结点所在位置情况，如果目标结点深度处于较深层时，需搜索的结点数基本上以指数果目标结点深度处于较深层时，需搜索的结点数基本上以指数增长，这时一般要采用循环队列来储存扩展结点。增长，这时一般要采用循环队列来储存扩展结点。 设有下图所示的一个棋盘，在棋盘上的设有下图所示的一个棋盘，在棋盘上的A(0,0)点有一个中国象棋马，点有一个中国象棋马，

9、并约定马走的规则：并约定马走的规则： 1、马只向右走；、马只向右走； 2、马走、马走“日日“字。字。找出所有从找出所有从A到到B的路径。的路径。输入：输入：B的坐标的坐标n，m（=15）。）。输出：所有走法。输出：所有走法。如：如：输入：输入：8 4输出：（输出：（0,0)(2 1)(4 0)(5 2)(6 0)(7 2)(8 4)共共37组解见组解见tmall.txt1234567123跳马问题最小步数跳马问题最小步数最优解输出结果为：最优解输出结果为：（8，4）（6，3）（4，2）（2，1），），-（0，0）求最少步到达求最少步到达B点。点。Best:最短路线，最短路线，a：临时得到的一个

10、路线。：临时得到的一个路线。Min：最少步。：最少步。procedure try(i:integer); 搜索到当前第搜索到当前第i个点个点 var j:integer; begin if (ai,1=n) and (ai,2=m)and(imin) then begin min:=i;best:=a;exit;end; 记下当前最短路径和最少步数记下当前最短路径和最少步数 if (ai,1n) or (ai,2m)and(i=min) then exit; 剪枝优化剪枝优化 for j:=1 to 4 do if (ai,1+xj,1=0)and(ai,1+xj,1=0)and(ai,2+x

11、j,2=m) then begin ai+1,1:=ai,1+xj,1; ai+1,2:=ai,2+xj,2; try(i+1); end; end;我们可以参照工作分配中求最大效益的方法来求解我们可以参照工作分配中求最大效益的方法来求解缺点：缺点：很明显，要找到一条跳的步数最小的路径，必须把很明显，要找到一条跳的步数最小的路径，必须把所有路径全部跳完后才能判断哪一条是最优路径，所有路径全部跳完后才能判断哪一条是最优路径，搜索效率比较低。搜索效率比较低。广度搜索求解跳马问题状态产生规则状态产生规则const dx:array1.4 of integer=(1,2,2,1); dy:array1

12、.4 of integer=(2,1,-1,-2);type node=record lx,ly:integer; pre:integer;父结点，输出时用 end;var a:array0.1000of node; h,t,n,m,i,x,y:integer;procedure print;输出，倒着输出直到父结点变成始结点止begin while at.pre0 do begin write(at.lx,at.ly,-); t:=at.pre; end; writeln(0,0); halt;由于搜索到的肯定是最优解所以程序运行结束end;begin readln(n,m); h:=0;

13、t:=1; a1.lx:=0;记录始状态 a1.ly:=0; a1.pre:=0; while h=1)and(x=1)and(y=m) then begin inc(t);入队 at.pre:=h;记住父结点 at.lx:=x; at.ly:=y;记录新结点 if (x=n) and (y=m) then print;是否到达 end; end; end;writeln(No solution)end.输出结果为：8，46，34，22，1-0，0【基础】走迷宫 题目描述题目描述迷宫由N*N个方格组成，每个方格均被组织者事先标上了“0”或“1”（左上角第一个方格和右下角最后一个方格一定是“0”

14、）。当你进入左上角的第一个方格中时，看到相邻的方格是“0”时则可以进入，而如果是“1”时则表示此路不通。兔兔被告之：从迷宫的左上角第一个方格的入口处准备进入时，你可得到一个记有N*N分值的记分表，每经过一个标有“0”的方格，记分表将自动扣去1分，当走到右下角最后一个方格的出口处时，将显示你手中的记分表剩余的分值。夏令营的组织者将只奖励所有参加此项活动中，记分表剩余的分值最多的营员。输入输入第一行是一个整数N（3N40），接下来有N行，每行均有N个由0 和1组成的数据输出输出包括一个整数（记分表剩余的分值）样例输入样例输入4 00111000 00011000 样例输出样例输出9解题思想：此题本

15、质上还是求最短的路径，因为求剩余的价值最大，也就是意味着要走过的路最短这样减少的值就会少！另外，对于此题不要求输出最短的路径，所以变量定义时可以考虑更少，不用再记录所走过的每个结点的位置，而且根据广度优先搜索的原理，从一个结点扩展到下一层结点，所剩余的值就是父结点的值减一即可，到了最后的目标结点，剩余的值就是所求的值。注意事项：输入是字符，不是数字0，1来源来源武进区第4届程序设计比赛题（初中）const dx:array1.4of integer=(1,0,-1,0);坐标增量 dy:array1.4of integer=(0,1,0,-1);type node=record s,x,y:i

16、nteger;S表示剩余的值，初值为n*n，x,y表示位置 end;varq:array1.100000of node;队列a:array1.100,1.100of char;状态变量h,t,i,j,n,lx,ly:longint;状态产生规则begin readln(n); for i:=1 to n do begin for j:=1 to n do read(ai,j);由于读入是字符，务必请注意 readln; end; h:=0;t:=1;q1.s:=n*n-1;q1.x:=1;q1.y:=1;a1,1:=1;从第一个结点开始，初值为n*n-1 repeat inc(h);出队 fo

17、r i:=1 to 4 do遍历所有结点 begin lx:=qh.x+dxi;ly:=qh.y+dyi; if (lx in 1.n)and(ly in 1.n)and(alx,ly=0) then结点可用 begin inc(t);入队 qt.s:=qh.s-1;该结点的剩余值为父结点的值减一 qt.x:=lx;记录位置，便于下次扩展用 qt.y:=ly; if (lx=n)and(ly=n) then begin writeln(qt.s);halt;end;如果到了目标结点直接输出 alx,ly:=1;该结点标志为已用过，以免重复入队 end; end; until h=t;end.例

18、例3-13-1：（：（xibaoshumuxibaoshumu.txt.txt） 一矩形阵列由数字一矩形阵列由数字0 0到到9 9组成组成, ,数字数字1 1到到9 9代表细胞代表细胞, ,细胞的定义为沿细胞数字上下左右还是细胞数字则为同细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞一细胞, ,求给定矩形阵列的细胞个数。求给定矩形阵列的细胞个数。输入：整数输入：整数m,n(mm,n(m行，行，n n列列) ) 矩阵矩阵输出：细胞的个数。输出：细胞的个数。样例样例: :输入输入: : 4 10 4 100234500067023450006710345605001034560500204

19、5600671204560067100000000890000000089输出输出:4:40234500067103456050020456006710000000089共共4 4个细胞个细胞算法步骤：算法步骤： 1 1、从文件中读入、从文件中读入m m* *n n矩阵，将其转换为矩阵，将其转换为0 0、1 1矩阵存入矩阵存入picpic数组中；数组中； 2 2、沿、沿picpic数组矩阵从上到下，从左到右，找到遇到的第数组矩阵从上到下，从左到右，找到遇到的第一个细胞；将细胞的位置入队一个细胞；将细胞的位置入队h h，并沿其上、下、左、右，并沿其上、下、左、右四个方向上搜索，如果遇到细胞四个方

20、向上搜索，如果遇到细胞(picI,j(picI,j=1)=1)则将其位置入队，则将其位置入队，入队后的位置入队后的位置picI,jpicI,j 数组置为数组置为0 0； 3 3、将、将h h队的队头出队，沿其上、下、左、右四个方向上队的队头出队，沿其上、下、左、右四个方向上搜索，如果遇到细胞则将其位置入队，入队后的位置搜索，如果遇到细胞则将其位置入队，入队后的位置picpic数数组置为组置为0 0； 4 4、重复、重复3 3，直至，直至h h队空为止，则此时找出了一个细胞；队空为止，则此时找出了一个细胞； 5 5、重复、重复2 2，直至矩阵找不到细胞；，直至矩阵找不到细胞； 6 6、输出找到的

21、细胞数。、输出找到的细胞数。const dx:array1.4 of -1.1=(-1,0,1,0); dy:array1.4 of -1.1=(0,1,0,-1);var s:string; pic:array1.50,1.80 of 0.1; 0:无细胞；无细胞；1：有细胞：有细胞 m,n,i,j,num:integer; h:array1.4000,1.2 of byte; 队列：存细胞的坐标，队列：存细胞的坐标，1：行；：行；2：列：列procedure doing(i,j:integer); var k,open,closed,x,y:integer; begin inc(num);

22、 pici,j:=0; open:=0; 队列头队列头 closed:=1; 队列尾队列尾 h1,1:=i; h1,2:=j;遇到的第一个细胞入队遇到的第一个细胞入队 while open0) and (x0) and (y=n) and (picx,y=1) (x,y)处有细胞处有细胞 then begin inc(closed);进队列进队列 hclosed,1:=x;hclosed,2:=y; picx,y:=0;打删除标志打删除标志 end;为细胞的入队为细胞的入队 end; end;begin fillchar(pic,sizeof(pic),0); num:=0; fillchar

23、(h,sizeof(h),0); assign(input,a.in);reset(input); assign(output,a.out);rewrite(output); readln(m,n); for i:=1 to m do begin readln(s); for j:=1 to n do if sj=0 then pici,j:=0 else pici,j:=1; end; for i:=1 to m do for j:=1 to n do if pici,j=1 then doing(i,j);在矩阵中寻找细胞 writeln(num); close(input); close

24、(output);end.八数码问题在在3*3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有18中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格中移动，如右图所示。这样通过移动将牌就可以不断改变的布局空格中移动，如右图所示。这样通过移动将牌就可以不断改变的布局结构，给出一个初始布局（称初始状态）和一个目标布局（称目标状结构，给出一个初始布局（称初始状态）和一个目标布局（称目标状态），问如何移动将牌，才能实现从初始状态到目标状态的转换。态），问如何移动将牌，才能实现从

25、初始状态到目标状态的转换。图图1八数码问题的初始和目标状态八数码问题的初始和目标状态状态表示：显然用二维数组来表示布局直观，状态表示：显然用二维数组来表示布局直观，S（I,j）表示第）表示第I行第行第J列列格子上放的数字。空格用格子上放的数字。空格用0表示；表示；移动规则：根据题意空格周围的棋子可以向空格移动。为便于解决问移动规则：根据题意空格周围的棋子可以向空格移动。为便于解决问题，显然从另一个角度来看，空格周围的棋子可以向空格移动相当于题，显然从另一个角度来看，空格周围的棋子可以向空格移动相当于“空格向四周移动空格向四周移动”，这样就把四枚棋子的移动转化为一个空格的移，这样就把四枚棋子的移

26、动转化为一个空格的移动，从而便于问题的处理。动，从而便于问题的处理。移动规则：移动规则：1、向上移动、向上移动Y+12、向下移动、向下移动Y-13、向左移动、向左移动X-14、向右移动、向右移动X+1搜索策略：搜索策略：1、把初始状态作为当前状态；、把初始状态作为当前状态；2、从当前的状态出发，运用四条移动规则，产生新的、从当前的状态出发，运用四条移动规则，产生新的状态状态3、判断新的状态是否达到目标状态，如果是，转、判断新的状态是否达到目标状态，如果是，转5；4、把新的状态记录下，取出下一个中间状态作为当前、把新的状态记录下，取出下一个中间状态作为当前状态，返回状态，返回2；5、输出从初始状

27、态到目标状态的路径，结束。、输出从初始状态到目标状态的路径，结束。const n:array1.4,1.2of integer=(1,0),(-1,0),(0,1),(0,-1);四个规则type arr=array1.3,1.3of integer;var a,b:Arr; list:array1.10000of arr;队列，存放结点 fa:array1.10000of integer;记录父结点 t:integer; i,o,j,x,y:integer; found:boolean;判断是否到达目标结点function f(c,d:arr):boolean;var k,l:integer

28、;begin f:=true; for k:=1 to 3 do for l:=1 to 3 do if ck,ldk,l then f:=false;end;判断是否已经存放在队列中function pa(c:arr):boolean;var k,l:integer;begin pa:=true; for k:=1 to o do if f(c,listk) then pa:=false;end;递归输出，按父结点是否为0来输出procedure print(c:integer);begin if fac0 then print(fac); for i:=1 to 3 do begin fo

29、r j:=1 to 3 do write(listci,j, ); writeln; end; writeln;end;找0的位置以便于继续扩展procedure fou;var k,l:integer;begin for k:=1 to 3 do for l:=1 to 3 do if listjk,l=0 then begin x:=k; y:=l; end;end;beginfor i:=1 to 3 do begin for j:=1 to 3 do begin read(list1i,j); end; readln; end; for i:=1 to 3 do begin for j

30、:=1 to 3 do read(bi,j); readln; end; o:=1;队列初始化 j:=0; fa1:=0; while j0)and(y+ni,20)and(x+ni,14)and(y+ni,21000) then break; end; if found then print(o) else writeln(NO ANSWER);end.最少步数在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生设想：如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个19

31、19的围棋的围棋盘上任选两点A，B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走。俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为（1，1）的点时，谁获胜。现在他请你帮忙，给你A，B两点的坐标，想知道两个位置到（1，1）点的可能的最少步数。输入：12 1618 10输出：89分析：由于A,B两点是随机输入的，因此我们无法找到计算最少步数的数学规律，只能通过广度优先搜索的办法求解。（1）确定出发点从（x,y）出发通过一次广度优先搜索，可以找到从（x,y）至棋盘上所有可达到的点的最少步数。而问题中要求的是黑马所在的（x1,y1）和白马所在的（x2,y2

32、）到达（1，1）目标点的最少步数。虽然两条路径的起点不同,但它们的终点却是相同的。如果我们将终点（1，1）为起点，这样只需要一次广度搜索便可以得到（x1,y1）和（x2,x2）到达（1，1）的最小步数。（2）数据结构设：que队列，存储从（1，1）可到达的点（quek，1.2）以及到达该点所需要的最小步数（quek，3）（0k192+1）。队列的首指针为closed，尾指针为open。初始时，que中只有一个元素为（1，1），最少步数为0。s记录（1，1）到每点所需的最少步数。显然，问题的答案是sx1，y1和x2，y2 。初始时，s1，1为0，除此之外的所有元素的值均设为-1。为了使马从棋盘内

33、任意位置扩展出的坐标均在s的范围内，我们将s的数组的范围扩大至s-1.21,-1.21。dx,dy移动后的位置增量数组。马有12种不同的扩展方向：马走“日”：(x-2,y-1),(x-1,y-2),(x-2,y+1),(x-1,y+2),(x+2,y-1),(x+1,y-2),(x+2,y+1),(x+1,y+2)。马走“田”:(x-2,y-2),(x-2,y+2),(x+2,y-2),(x+2,y+2).我们将i方向上的位置增量存入常量数组dxi和dxi中（1i12）：Const dx:array1.12 of integer=(-2,-2-1,1,2,2,2,2,1,-1,-2,-2);

34、dy:array1.12 of integer=(-1,-2,-2,-2,-2,-1,1,2,2,2,2,1);(3)约束条件不能越出界外。由于马的所有可能的落脚点s均在s的范围内，因此一旦马越出界外，就将其s值赋为0，表示“已经扩展过，且到达（1，1）最少需要0步”。这看上去是荒谬的，但是可以简单而有效地避免马再次落入这些界外点。该点在以前的扩展中没有到达过。如果曾经到达过，则根据广度优先搜索的的原理，先前到达该点所需的步数一定小于当前步数，因此完全没有必要再扩展下去。由此得出，马跳后的位置（x,y）是否可以入队的约束条件是sx,y0。（4）算法流程 fillchar(s,sizeof(s)

35、,o);s1,1:=0; for x1:=1 to 19 do for y1:=1 to 19 do sx1,y1:=-1; open:=1;closed:=0; que1,1:=1;que1,2:=1; read(x1,y1,x2,y2); while closedopen do begin inc(closed); for d:=1 to 12 do begin x:=queclosed,1+dxd; y:=queclosed,2+dyd; if sx,y0 then begin sx,y:=queclosed,3+1; inc(open); queopen,1:=x;queopen,2:

36、=y;queopen,3:=sx,y; end; end; end; end; writeln(sx1,y1); writeln(sx2,y2);小鼠迷宫问题【问题描述】小鼠a与小鼠b身处一个mn的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这mn个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿上，下，左，右4个方向进入未封闭的房间。小鼠a位于迷宫的（p，q）方格中，它必须找出一条通向小鼠b所在的（r，s）方格的路。请帮助小鼠a找出通向小鼠b的最短道路。 【输入格式】输入文件中的第一行为三个正整数n，m，k（1=n，m=100，0=k=mn-2），分别表示迷宫的行数，

37、列数和封闭的房间数。接下来的k行，每行有两个正整数，表示被封闭的房间所在的行号和列号。最后的两行，每行有两个正整数，分别表示小鼠a所处的方格（p，q）和小鼠b所处的方格（r，s），小鼠a和小鼠b所处的方格是不封闭的。【输出格式】输出文件中为计算出的小鼠a通向小鼠b的最短路长度。【输入输出样例】输入：（maze.in）：8 8 33 34 56 62 17 7输出：（maze.out）：11源程序：const maxn=100;w:array1.4of integer=(1,0,-1,0);定义状态变化u:array1.4of integer=(0,1,0,-1);var map:array1.