双向广度优先搜索算法

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

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

3、) then expand(0); if not(head1tail1)or(tail1=maxn) then expand(1);Until (head0tail0)or(tail0=maxn) And (head1tail1)or(tail1=maxn)算法描述expand(st:0.1)程序代码如下: 取出队列当前待扩展的结点cst,headst inc(headst); I:=1; while (i=maxk) and (tailstmaxn) do begin inc(tailst); 产生新结点; check(st);检查新节点是否重复 inc(i); end;算法描述check(

4、st:0.1)程序代码:检查节点，如果不重复，则判断是否相遇 i:=1; flag:=true; while flag and (I tailst) do begin if cst,tailst.*=cst,i.* then begin flag:=false; dec(tailst);exit end; inc(I); end; if flag then encounter(st);判断是否相遇算法描述encounter(st:0.1)程序代码: for i:=1 to tail1-st do if cst,tailst.*=c1-st,i.* then print(st,tailst,i)

5、; 如果双向搜索相遇（即得到同一节点），则输出结果算法描述print(st,tail,k)程序代码： if st=0 then begin print0(tail); print1(k); end; else begin print0(k); print1(tail) end; writeln(cst,tailst.dep+c1-st,tailk.dep-1) close(f)； halt;算法描述print0(m)程序代码： if m0 then begin print0(c0,m.f); 输出c0,m.* end;输出正方向上产生的结点算法描述print1(m)程序代码; n:=c1,m.

6、f ; while n0 do begin 输出c1,n.*; n:=c1,n.f; end;输出反方向上产生的结点例例 八数码难题。八数码难题。 在在3*3的棋盘上，摆的棋盘上，摆 有八个棋子，每个棋子上标有有八个棋子，每个棋子上标有1至至8的某一数字。棋盘中留有一个空格。空格周围的棋的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是，给出一种初始子可以移到空格中。要求解的问题是，给出一种初始布局布局初始状态初始状态和目标布局和目标布局目标状态目标状态，找到一种移动，找到一种移动的方法，实现从初始布局到目标布局的转变。的方法，实现从初始布局到目标布局的转变。【输入格

7、式】【输入格式】 输入文件共输入文件共6 6行，每行三个数字（无间隔）。前三行，每行三个数字（无间隔）。前三行表示初始布局，后三行表示目标布局。行表示初始布局，后三行表示目标布局。【输出格式】【输出格式】 输出文件有若干行，每三行表示一种状态，两状态输出文件有若干行，每三行表示一种状态，两状态间有一空行隔开。间有一空行隔开。 例例 八数码难题。八数码难题。 在在3*3的棋盘上，摆的棋盘上，摆 有八个棋子，每个棋子上标有有八个棋子，每个棋子上标有1至至8的某一数字。棋盘中留有一个空格。空格周围的棋的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是，给出一种初始子可以移到

8、空格中。要求解的问题是，给出一种初始布局布局初始状态初始状态和目标布局和目标布局目标状态目标状态，找到一种移动，找到一种移动的方法，实现从初始布局到目标布局的转变。的方法，实现从初始布局到目标布局的转变。2 8 31 6 47 51 2 38 47 6 5283164705283164075283164750283104765283064175283014765203184765283140765283160754083264175283604175083214765283714065280143765283145760283106754280163754 综合数据库typetype ztst

9、r=string9; ztstr=string9; node=record node=record zt:ztstr; zt:ztstr; 当前状态当前状态 f:0.maxn; f:0.maxn; 父亲结点指针父亲结点指针 kong:shortint; kong:shortint; end; end;Var c:array0.1,1.maxn of node; c:array0.1,1.maxn of node; head,tail:arrayfx of integer; head,tail:arrayfx of integer; start,goal:ztstr; 产生式规则:4条，空格向上

10、，下，左，右四个方向移动生成结点的条件：（1）新状态不出界（2）和已生成结点不重复Temp:=cst,headst.kong;Cst,tailst:=cst,headst;with cst,tailst do begin ztkong:=ztkong+ydk; kong:=kong+ydk; xtkong:=0; f:=headst;dep:=dep+1; end;k1234方向左上右下Kong-1-3+1+3搜索策略（BFS） 框图：初始Headst=0Tailst=0初始化INIT;初始结点入队结点出队down(temp1)temp temp1 change(temp)For k:=1 t

11、o 4 doCheck(temp) and not(dupe(temp)ynup(temp)Temp=goalynPrint 打印Exit 退出Until head=tail1.1.字串变换（字串变换（stringstring）已知有两个字串已知有两个字串 A$, B$ A$, B$ 及一组字串变换的规则（至多及一组字串变换的规则（至多6 6个个规则）规则）:A1$ - B1$:A1$ - B1$ A2$ - B2$A2$ - B2$规则的含义为：在规则的含义为：在 A$A$中的子串中的子串 A1$ A1$ 可以变换为可以变换为 B1$B1$、A2$ A2$ 可以变换为可以变换为 B2$ B2

12、$ 。例如：例如：A$A$abcdabcdB$B$xyzxyz变换规则为：变换规则为：abc-abc-xuxuud-ud-yyy-y-yzyz则此时，则此时，A$ A$ 可以经过一系列的变换变为可以经过一系列的变换变为 B$B$，其变换的过程，其变换的过程为：为：abcd-abcd-xud-xud-xy-xy-xyzxyz共进行了三次变换，使得共进行了三次变换，使得 A$ 变换为变换为B$。 输入文件格式输入文件格式:A$ B$A$ B$A1$ B1$ A1$ B1$ A2$ B2$ |- A2$ B2$ |- 变换规则变换规则. . /. . /所有字符串长度的上限为所有字符串长度的上限为

13、2020。 输出文件格式输出文件格式:若在若在 10 10 步（包含步（包含 1010步）以内能将步）以内能将 A$ A$ 变换为变换为 B$ B$ ，则输，则输出最少的变换步数；否则输出出最少的变换步数；否则输出NO ANSWER! NO ANSWER! 输入输出样例输入输出样例 string.in:string.in:abcd xyzabcd xyzabc xuabc xuud yud yy yzy yzstring.outstring.out：3 3练习：如图是六个城市之间道路联系的示意图，连线表示两城市间有道路相通，连线旁的数字表示路程。请编程序找出从C1到C6的一条路径及路程总长度，

14、要求求出经过城市最少的解（想一想，如果要求求出路程总长度最少的解应该怎么做）。 C63448492264C1C2C5C4C3综合数据库typenode=record city:integer;城市编号 flag:set of 1.6;到根结点的路径 f:integer;父节点 end;Var data:array1.1000 of node; temp:node;产生式规则有5条，向R（R=2-6）城市移动生成结点的条件：（1）城市R不在已走路径中 （not(R in datahead.flag)） （2）当前城市到R有路（linkx,r0） Datatemp.city:=R; Datatem

15、p.flag:= Datatemp.flag+R; Datatemp.pnt:=head; 搜索策略（BFS） 框图：初始head=0Tail=1初始化INIT;初始结点入队Inc(head); tempdatahead结点出队For r:=2 to 6 do条件1 and 条件2yn新结点是目标结点新结点是目标结点ynPrint 打印Exit 退出Until head=tailin(temp)新结点入队新结点入队新结点入队：新结点入队：In(temp)Inc(tail);With datatail do begin cityr flagtemp.flag+r pnthead end;练习3：

16、翻币问题。有N个硬币（N=6），正面朝上排成一排，每次将5个硬币翻过来放在原来位置，直到最后全部硬币翻成反面朝上为止。编程让计算机找步数最少的翻法，并把翻币过程及次数打印出来（用O表示正面，*表示反面） 综合数据库typenode=record r:integer; ( 由父节点翻了几个正面朝上的硬币得到当前状态由父节点翻了几个正面朝上的硬币得到当前状态) num:integer;(当前状态中硬币正面朝上的个数当前状态中硬币正面朝上的个数) pnt:integer;( 父节点位置父节点位置)end;Var data:array1.1000 of node; temp:node;产生式规则:6条，即翻R个（R=0，1，2，3，4，5）正面朝上的硬币 生成结点的条件：（1）当前状态有多于R个正面朝上的硬币M=R（M表示当前结点正面朝上硬币的个数），否则出现负数 （2）当前状态有多于5-R个反面朝上的硬币N-M=5-R（N表示硬币总数），例如当全部是正面时，R只能取5，不能取04。这时N=M，只有R=5时，不等式才成立。 （3