搜索算法——BFSppt课件.ppt
搜索算法BFS,江家和,BFS：Breadth First Search宽度优先搜索（广度优先搜索）就是先往“广”的地方找，再一层一层推下去。换句话说就是先把同层的找完，再往下一层去找，是一种“扩散”的思想。每个深度为t的结点一定会在深度为t+1的结点前被搜寻到。用队列实现。,搜索顺序: A,(B,C,D),(E,F,G,H),(I,J,K,L),I,B,F,H,D,J,A,E,C,K,L,G,BFS,前面我们说BFS是扩散的思想，现在用迷宫问题来解释：一般的迷宫问题是只要找到从入口到出口的路就可以了。但是现在需要求最少走几步就能找到出口？当然我们可以使用暴力法去求解，把所有可能性都列出来，然后从中找步数最少的，这种暴力法就是DFS。DFS在求解这类问题时的效率是非常非常低的，使用BFS就很合适，效率要高多了。让我们分析一下：,BFS,这是一个迷宫S为起点，F为终点涂黑的区域表示不通每次只能上下左右移动，而且每次只能走一格下面用队列来求解：,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,7,7,7,7,8,8,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 00 0 0 0 0 1 00 0 0 0 0 0 00 1 0 1 0 0 00 1 0 0 0 0 0 0 0 1 0 0 1 0,示例输出：1,12,13,14,15,16,17,1 从终止点到起始点的路径6 最少步数,bfs算法流程如下：,open:=1;closed:=0;hopen:=初始状态； 初始状态进入队列while closedopen do begin 如果队列非空，则移出队首状态，扩展它所有的子状态 inc(closed); expand(); 扩展它所有的子状态，满足条件入队 if 到达目标状态 then 输出 end;,const da:array1.4of integer=(0,1,0,-1); db:array1.4of integer=(1,0,-1,0);var t,m,n,i1,i2,j1,j2,i,j,closed,open:longint; a:array1.50,1.50of longint; h:array1.1000of record a1,b1:longint; end; father:array1.50of longint; f1,f2:text;procedure printf; var i:integer; begin t:=1;i:=open; while fatheri1 do begin i:=fatheri; writeln(f2,hi.a1,hi.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; hopen.a1:=i1;hopen.b1:=j1; ai1,j1:=1; while closed=1)and(i=1)and(j=n)and(ai,j=0) then begin inc(open); hopen.a1:=i;hopen.b1:=j; fatheropen:=closed; ai,j:=1; if (i=i2)and(j=j2) then printf; end; end; end; end;begin assign(f1,migong.in);reset(f1); assign(f2,migong.out);rewrite(f2); readln(f1,m,n); readln(f1,i1,j1,i2,j2); for i:=1 to m do begin for j:=1 to n do read(f1,ai,j); readln(f1); end; close(f1); writeln(f2,i2,j2); bfs;end.,双向广度优先搜索,广度优先搜索BFS遵循从初始结点开始一层层扩展直到找到目标结点的搜索策略。如果目标结点处于很深的层，这时采用BFS搜索量是相当大的，往往会出现内存不够用的情况。双向BFS和A算法对广度优先的搜索方式进行了改良或改造，加入了一定的“智能因素”，使搜索能尽快接近目标结点，减少了在空间和时间上的复杂度。有些问题按照广度优先搜索扩展结点的规则，既适合顺序，也适合逆序，于是我们考虑在寻找目标结点或路径的搜索过程中，初始结点向目标结点和目标结点向初始结点同时进行扩展，直至在两个扩展方向上出现同一个子结点，搜索结束，这就是双向搜索过程。出现的这个同一子结点，我们称为相交点，如果确实存在一条从初始结点到目标结点的最佳路径，那么按双向搜索进行搜索必然会在某层出现“相交”，即有相交点，初始结点一相交点一目标结点所形成的一条路径即是所求路径。,例题：,移动一个只含字母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 AABAAB (a) 图1 (b)顺序扩展的第8个子结点与逆序扩展得到的第4个子结点就是相交点，问题的最佳路径是：AABBAAAABABAAABAABABAAABBAAAAB,
