搜索算法——BFS

搜索算法——BFS江家和•BFS：BreadthFirstSearch•宽度优先搜索（广度优先搜索）•就是先往“广”的地方找，再一层一层推下去。•换句话说就是先把同层的找完，再往下一层去找，是一种“扩散”的思想。•每个深度为t的结点一定会在深度为t+1的结点前被搜寻到。•用队列实现。•搜索顺序:A,(B,C,D),(E,F,G,H),(I,J,K,L)IBFHDJAECKLGBFS•前面我们说BFS是扩散的思想，现在用迷宫问题来解释：•一般的迷宫问题是只要找到从入口到出口的路就可以了。•但是现在需要求最少走几步就能找到出口？•当然我们可以使用暴力法去求解，把所有可能性都列出来，然后从中找步数最少的，这种暴力法就是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)(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]:=初始状态；{初始状态进入队列}whileclosedopendobegin{如果队列非空，则移出队首状态，扩展它所有的子状态}inc(closed);expand();{扩展它所有的子状态，满足条件入队}if到达目标状态then输出end;constda:array[1..4]ofinteger=(0,1,0,-1);db:array[1..4]ofinteger=(1,0,-1,0);vart,m,n,i1,i2,j1,j2,i,j,closed,open:longint;a:array[1..50,1..50]oflongint;h:array[1..1000]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;beginopen:=1;closed:=0;h[open].a1:=i1;h[open].b1:=j1;a[i1,j1]:=1;whileclosedopendobegininc(closed);fork:=1to4dobegini:=da[k]+h[closed].a1;j:=db[k]+h[closed].b1;if(i=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)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遵循从初始结点开始一层层扩展直到找到目标结点的搜索策略。如果目标结点处于很深的层，这时采用BFS搜索量是相当大的，往往会出现内存不够用的情况。双向BFS和A算法对广度优先的搜索方式进行了改良或改造，加入了一定的“智能因素”，使搜索能尽快接近目标结点，减少了在空间和时间上的复杂度。•有些问题按照广度优先搜索扩展结点的规则，既适合顺序，也适合逆序，于是我们考虑在寻找目标结点或路径的搜索过程中，初始结点向目标结点和目标结点向初始结点同时进行扩展，直至在两个扩展方向上出现同一个子结点，搜索结束，这就是双向搜索过程。出现的这个同一子结点，我们称为相交点，如果确实存在一条从初始结点到目标结点的最佳路径，那么按双向搜索进行搜索必然会在某层出现“相交”，即有相交点，初始结点一相交点一目标结点所形成的一条路径即是所求路径。例题：•移动一个只含字母A和B的字符串中的字母，给定初始状态为(a)表，目标状态为(b)表，给定移动规则为：只能互相对换相邻字母。请找出一条移动最少步数的办法。AABBAABAAAAB(a)(b)•分析：•从初始状态和目标状态均按照深度优先搜索扩展结点，当达到以下状态时，出现相交点，如图1(a)，结点序号表示结点生成顺序。双向扩展结点：顺序逆序11___AABBAA___BAAAAB2/\32/\3__ABABAA__AABABAABAAABBAAABA4/|5\67/\84/ABBAAABAABAAABAABAAAABBAAABAABAABAAB(a)图1(b)顺序扩展的第8个子结点与逆序扩展得到的第4个子结点就是相交点，问题的最佳路径是：[AABBAA]—[AABABA]—[AABAAB]—[ABAAAB]—[BAAAAB]