搜索算法——BFS课件.ppt

《搜索算法——BFS课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、搜索算法——BFS江家和BFS：BreadthFirstSearch宽度优先搜索（广度优先搜索）就是先往“广”的地方找，再一层一层推下去。换句话说就是先把同层的找完，再往下一层去找，是一种“扩散”的思想。每个深度为t的结点一定会在深度为t+1的结点前被搜寻到。用队列实现。搜索顺序:A,(B,C,D),(E,F,G,H),(I,J,K,L)IBFHDJAECKLGBFS前面我们说BFS是扩散的思想，现在用迷宫问题来解释：一般的迷宫问题是只要找到从入口到出口的路就可以了。但是现在需要求最少走几步就能找到出口？当然我们可以使用暴力法去求解，把所有可能性都列出来，然后从中找步

2、数最少的，这种暴力法就是DFS。DFS在求解这类问题时的效率是非常非常低的，使用BFS就很合适，效率要高多了。让我们分析一下：BFS这是一个迷宫S为起点，F为终点涂黑的区域表示不通每次只能上下左右移动，而且每次只能走一格下面用队列来求解：FS._.0123456012345S6111222233334444455555555666666667777887(5,1)(4,1)(5,0)(6,1)(4,0)(4,2)(6,0)(6,2)(3,0)(3,2)(4,3)(6,3)(2,0)(2,2)(4,4)(5,3)(6,4)(1,0)(2,1)(1,2)(2,3)(3,4

3、)(4,5)(5,4)(6,5)(0,0)(1,1)(0,2)(1,3)(2,4)(3,5)(4,6)(6,6)(0,1)(1,4)(2,5)(3,6)(5,6)(0,4)(2,6)9(0,5)(1,6)FBFS迷宫问题迷宫问题：求从起点到终点的最短路径，并输出相应的点的坐标。示例输入：77{行列数}7111{起始点和终止点}000100000000100000000010100001000000010010示例输出：1,12,13,14,15,16,17,1{从终止点到起始点的路径}6{最少步数}bfs算法流程如下：open:=1;closed:=0;h[open]

4、:=初始状态；{初始状态进入队列}whileclosed

5、0]ofrecorda1,b1:longint;end;father:array[1..50]oflongint;f1,f2:text;procedureprintf;vari:integer;begint:=1;i:=open;whilefather[i]<>1dobegini:=father[i];writeln(f2,h[i].a1,',',h[i].b1);inc(t);end;writeln(f2,i1,',',j1);writeln(f2,t);close(f2);halt;end;procedurebfs;vari,j,k:longint;beginop

6、en:=1;closed:=0;h[open].a1:=i1;h[open].b1:=j1;a[i1,j1]:=1;whileclosed=1)and(i<=m)and(j>=1)and(j<=n)and(a[i,j]=0)thenbegininc(open);h[open].a1:=i;h[open].b1:=j;father[open]:=closed;a[i,j]:=1;if(i=i2

7、)and(j=j2)thenprintf;end;end;end;end;beginassign(f1,'migong.in');reset(f1);assign(f2,'migong.out');rewrite(f2);readln(f1,m,n);readln(f1,i1,j1,i2,j2);fori:=1tomdobeginforj:=1tondoread(f1,a[i,j]);readln(f1);end;close(f1);writeln(f2,i2,',',j2);bfs;end.双向广度优先搜索广度优先搜索BFS遵循从初始结点开始一层层