文档介绍：搜索算法—— BFS 江家和? BFS : Breadth First Search ?宽度优先搜索(广度优先搜索) ?就是先往“广”的地方找,再一层一层推下去。?换句话说就是先把同层的找完,再往下一层去找,是一种“扩散”的思想。?每个深度为 t的结点一定会在深度为 t+1 的结点前被搜寻到。?用队列实现。?搜索顺序: A,(B,C,D),(E,F,G,H),(I,J,K,L) I BFH D J A E CKL G BFS ?前面我们说 BFS 是扩散的思想,现在用迷宫问题来解释: ?一般的迷宫问题是只要找到从入口到出口的路就可以了。?但是现在需要求最少走几步就能找到出口? ?当然我们可以使用暴力法去求解,把所有可能性都列出来, 然后从中找步数最少的,这种暴力法就是 DFS 。 DFS 在求解这类问题时的效率是非常非常低的,使用 BFS 就很合适, 效率要高多了。?让我们分析一下: BFS ?这是一个迷宫?S为起点, F为终点?涂黑的区域表示不通?每次只能上下左右移动,而且每次只能走一格?下面用队列来求解: F S . 012345S611 1222 2 3333 444 44 55 5555 556 666 66 66 7777 88 7 (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) (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) F BFS 迷宫问题迷宫问题: 求从起点到终点的最短路径,并输出相应的点的坐标。示例输入: 7 7 {行列数} 7 1 1 1 {起始点和终止点} 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 示例输出: 1,1 2,1 3,1 4,1 5,1 6,1 7,1 {从终止点到起始点的路径} 6 {最少步数} bfs 算法流程如下: open:=1;closed:=0; h[open ]:= 初始状态; {初始状态进入队列} while closed<open do begin {如果队列非空,则移出队首状态,扩展它所有的子状态} inc(closed ); expand(); {扩展它所有的子状态,满足条件入队} if 到达目标状态 then 输出 end; const da:array[1..4]of integer=(0,1,0,-1); db:array[1..4]of integer=(1,0,-1,0); var t,m,n,i1,i2,j1,j2,i,j,closed,open:longint; a:array[1..50,1..50]of longint ; h:array[1..1000]of record a1,b1:longint; end; father:array[1..50]of longint ; f1,f2:text; procedure printf ; var i:integer ; begin t:=1;i:=open; while father[i ]<>1 do begin i:= father[i ]; writeln(f2,h[i].a1,',',h[i].b1); inc(t ); end; writeln(f2,i1,',',j1); writeln(f2,t); close(f2); halt; end; procedure bfs ; var i,j,k:longint ; begin open:=1;closed:=0; h[open].a1:=i1;h[open].b1:=j1; a[i1,j1]:=1; while closed<open do begin inc(closed ); for k:=1 to