广度优先双向搜索算法

1、第一章 广度优先双向搜索1.1 广度双向搜索的概念所谓双向搜索指的是搜索沿两个力向同时进行：正向搜索：从初始结点向目标结点方向搜索；逆向搜索：从目标结点向初始结点方向搜索；当两个方向的搜索生成同一子结点时终止此搜索过程。1. 2 广度双向搜索算法广度双向搜索通常有两中方法：2. 两个方向交替扩展3. 选择结点个数较少的那个力向先扩展方法 2 克服了两方向结点的生成速度不平衡的状态，明显提高了效率。算法说明：设置两个队列c:array0.1,1.maxn of jid ，分别表示正向和逆向的扩展队列。设置两个头指针head:array0.1 of integer 分别表示正向和逆向当前将扩展结点

2、的头指针。设置两个尾指针tail:array0.1 of integer 分别表示正向和逆向的尾指针。maxn 表示队列最大长度。算法描述如下：1 .主程序代码repeat 选择节点数较少且队列未空、未满的方向先扩展if (tail0<=tail1) and not(head0>=tail0)or(tail0>=maxn) then expand(0);if (tail1<=tail0) and not(head1>=tail1)or(tail1>=maxn) then expand(1); 如果一方搜索终止，继续另一方的搜索，直到两个方向都终止if not

3、(head0>=tail0)or(tail0>=maxn) then expand(0);if not(head1>=tail1)or(tail1>=maxn) then expand(1);Until (head0>=tail0)or(tail0>=maxn) And (head1>=tail1)or(tail1>=maxn)2 .expand(st:0.1) 程序代码如下:inc(headst;取出队列当前待扩展的结点cst,headstfor i:=1 to maxk dobeginif tailst>=maxn then exit;

4、inc(tailst);产生新结点;check(st); 检查新节点是否重复end;3 .check(st:0.1) 程序代码:for i:=1 to tailst-1 doif cst,tailstp* = cst,ip* then begin dec(tailst);exit end;bool(st); 如果节点不重复，再判断是否到达目标状态4 .bool(st:0.1) 程序代码:for i:=1 to tail1-st doif cst,tailstF.*=c1-st,iA.* then print(st,tailst,i); 如果双向搜索相遇(即得到同一节点)，则输出结果5 .pri

5、nt(st,tail,k) 程序代码：if st=0 then begin print0(tail);print1(k) end;else begin print0(k);print1(tail) end;6 .print0(m) 程序代码：if m<>0 then begin print(c0,mA.f);输出 c0,mA.* end; 输出正方向上产生的结点7 .print1(m) 程序代码;n:=c1,mA.fwhile m<>0begin输出 c1,nA.*;n:=c1,nA.f;end 输出反方向上产生的结点1.3 例题与习题例 1 ： 8 数码难题：2 8

6、31 2 31 6 4 -> 8 4(用最少的步数)7 5 7 6 5程序如下：program num8;const maxn=4000;type jid=recordstr:string9;f:0.maxn;dep:byte;end;bin=0.1;var c:array0.1,1.maxn of Ajid;head,tail:array0.1 of integer;start,goal:string9;procedure init;var i,j:integer;beginstart:='283164705'goal:='123804765'for i

7、:=0 to 1 dofor j:=1 to maxn donew(ci,j);c0,1A.str:=start; c0,1A.f:=0; c0,1A.dep:=0;c1,1A.str:=goal; c1,1A.f:=0; c1,1A.dep:=0;for i:=0 to 1 dobegin headi:=0;taili:=1;end;end;procedure print(st:bin;tail,k:integer);procedure print0(m:integer);beginif m<>0 thenbegin print0(c0,mA.f);writeln(c0,mA.s

8、tr) end;end;procedure print1(m:integer);var n:integer;beginn:=c1,mA.f;while n<>0 dobegin writeln(c1,nA.str); n:=c1,nA.f end;end;beginif st=0 thenbegin writeln('step=',c0,tailA.dep+c1,kA.dep);print0(tail); print1(k);endelse begin writeln('step=',c0,kA.dep+c1,tailA.dep);print0(k)

9、; print1(tail); end ;halt;end;procedure check(st:bin);procedure bool(st:bin);var i:integer;beginfor i:=1 to tail1-st doif cst,tailstA.str=c1-st,iA.str then print(st,tailst,i); end;var i:integer;beginfor i:=1 to tailst-1 doif cst,tailstA.str=cst,iA.str thenbegin dec(tailst);exit end;bool(st);end;proc

10、edure expand(st:bin);var i,p0,p1,d:integer;str0,str1:string9;begininc(headst);str0:=cst,headstA.str;d:=cst,headstA.dep;p0:=pos('0',str0);for i:=1 to 4 dobeginif tailst>=maxn then exit;p1:=p0+2*i-5;if (p1 in 1.9) and not (p0=3) and (p1=4)and not(p0=4)and (p1=3)and not(p0=6)and(p1=7)and not

11、(p0=7)and(p1=6)thenbegininc(tailst);str1:=str0;str1p0:=str1p1;str1p1:='0'cst,tailstF.str:=str1;cst,tailstF.f:=headst;cst,tailstF.dep:=d+1;check(st);end;end;end;begininit;check(0);repeatif (tail0<=tail1) and not(head0>=tail0)or(tail0>=maxn)then expand(0);if (tail1<=tail0) and not(

12、head1>=tail1)or(tail1>=maxn)then expand(1);if not(head0>=tail0)or(tail0>=maxn) then expand(0);if not(head1>=tail1)or(tail1>=maxn) then expand(1);Until(head0>=tail0)or(tail0>=maxn)And(head1>=tail1)or(tail1>=maxn);writeln('No answer');end.练习：1.问题描述:已知有两个字串A$, B$及一

13、组字串变换的规则(至多6个规则)：A1$-> B1$A2$ -> B2$规则的含义为：在 人$中的子串 A1$可以变才奂为B1$、A2$可以变才奂为B2$例如：A$ = 'abcd' B$='xyz'变换规则为：，abc，->，xu，ud>，y，y>，yz，则此时，A$可以经过一系列的变换变为B$,其变换的过程为：，abcd'-，xud，-，xy，-，xyz，共进行了三次变换，使得 A$变换为B$ 输入:键盘输人文件名。文件格式如下：A$ B$A1$ B1$ A2$ B2$ -变换规则 . . /所有字符串长度的上限为20。输出:输出至屏幕。格式如下：若在10步（