广度优先搜索算法与双向广度优先搜索算法 【转】

 

     使用计算机求解的问题中，有许多问题是无法用数学公式进行计算推导采用模拟方法来找出答案的。这样的问题往往需要我们根据问题所给定的一些条件，在问题的所有可能解中用某种方式找出问题的解来，这就是所谓的搜索法或搜索技术。 

通常用搜索技术解决的问题可以分成两类：一类问题是给定初始结点，要求找出符合约束条件的目标结点；另一类问题是给出初始结点和目标结点，找出一条从初始结点到达目标结点的路径。 

     常见的搜索算法有枚举法、广度优先搜索法、深度优先搜索法、双向广度优先搜索法，A*算法、回溯法、分支定界法等。这里来讨论一下。

一.广度优先搜索算法

1. 问题的特征

     可以采用搜索算法解决的这类问题的特点是： 

1）有一组具体的状态，状态是问题可能出现的每一种情况。全体状态所构成的状态空间是有限的，问题规模较小。 

2）在问题的解答过程中，可以从一个状态按照问题给定的条件，转变为另外的一个或几个状态。 

3）可以判断一个状态的合法性,并且有明确的一个或多个目标状态。 

4）所要解决的问题是：根据给定的初始状态找出目标状态，或根据给定的初始状态和结束状态，找出一条从初始状态到结束状态的路径。

2.广度优先搜索算法解题的步骤

1）定义一个状态结点 

采用广度优先搜索算法解答问题时，需要构造一个表明状态特征和不同状态之间关系的数据结构，这种数据结构称为结点。不同的问题需要用不同的数据结构描述。 

2）确定结点的扩展规则 

     根据问题所给定的条件，从一个结点出发，可以生成一个或多个新的结点，这个过程通常称为扩展。结点之间的关系一般可以表示成一棵树，它被称为解答树。搜索算法的搜索过程实际上就是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的结点的过程。 

     广度优先搜索算法中，解答树上结点的扩展是沿结点深度的“断层”进行，也就是说，结点的扩展是按它们接近起始结点的程度依次进行的。首先生成第一层结点，同时检查目标结点是否在所生成的结点中，如果不在，则将所有的第一层结点逐一扩展，得到第二层结点，并检查第二层结点是否包含目标结点，...对长度为n+1的任一结点进行扩展之前，必须先考虑长度为n的结点的每种可能的状态。因此，对于同一层结点来说，求解问题的价值是相同的，我们可以按任意顺序来扩展它们。这里采用的原则是先生成的结点先扩展。 

     结点的扩展规则也就是如何从现有的结点生成新结点。对不同的问题，结点的扩展规则也不相同，需要按照问题的要求确定。 

3）搜索策略 

    为了便于进行搜索，要设置一个表存储所有的结点。因为在广度优先搜索算法中，要满足先生成的结点先扩展的原则，所以存储结点的表一般设计成队列的数据结构。 

搜索的步骤一般是： 

（1）从队列头取出一个结点，检查它按照扩展规则是否能够扩展，如果能则产生一个新结点。 

（2）检查新生成的结点，看它是否已在队列中存在，如果新结点已经在队列中出现过，就放弃这个结点，然后回到第（1）步。否则，如果新结点未曾在队列中出现过，则将它加入到队列尾。 

（3）检查新结点是否目标结点。如果新结点是目标结点，则搜索成功，程序结束；若新结点不是目标结点，则回到第（1）步，再从队列头取出结点进行扩展......。 

最终可能产生两种结果：找到目标结点，或扩展完所有结点而没有找到目标结点。 

     如果目标结点存在于解答树的有限层上，广度优先搜索算法一定能保证找到一条通向它的最佳路径，因此广度优先搜索算法特别适用于只需求出最优解的问题。当问题需要给出解的路径，则要保存每个结点的来源，也就是它是从哪一个节点扩展来的。

3.广度优先搜索算法的算法框架

 

     对于广度优先搜索法来说，问题不同则状态结点的结构和结点扩展规则是不同的，但搜索的策略是相同的，因此算法框架也基本相同。

1 struct   tnode{                          //定义一个结点数据类型  2              ....                               //根据具体问题确定所需的数据类型  3 }state[maxn];                          //定义tnode类型的数组作为存储结点的队列  4 void init();                              //初始化函数  5 bool extend();                         //判断结点是否能扩展，如果能则产生新结点  6 bool repeat();                         //检查新结点是否在队列中已经出现  7 bool find()                             //检查新结点是否目标结点  8 void outs();                            //输出结点状态  9 void printpath();                    //输出路径 10 void bfs(){                              //BFS算法主程序 11   tnode   temp;                         //tnode型临时结点 12   int head=0,tail=0;                 //队列头指针和尾指针 13   while(head<=tail  && tail          //根据具体问题确定一个结点扩展规则 14      temp=state[head];                  //取队列头的结点 15      if(extend()){                          //如果该结点可以扩展则产生一个新结点 16         if(!repeat()){                      //如果新结点未曾在队列中出现过则 17            tail++;                             // 将新结点加入队列尾    18           state[tail] =temp; 19           state[tail].last=head;                  //记录父结点标识 20           if(find()){                                  // 如果新结点是目标结点 21             hail++;                                     // 将队列尾结点的父结点指针指向队列尾    22             state[tail] =tail-1; 23             printpath();                               //输出路径 24             break;                                       //退出程序  25      } 26   } 27 } 28   head++;                                     //队列头的结点扩展完后出队，取下一结点扩展 29 } 30 }

     对于不同的问题，用广度优先搜索法的算法基本上都是一样的。但表示问题状态的结点数据结构、新结点是否目标结点和是否重复结点的判断等方面则有所不同，对具体的问题需要进行具体分析，这些函数要根据具体问题进行编写。

二.广度优先搜索算法的例子

下面来看几个简单的例子：

1.分油问题

一个一斤的瓶子装满油，另有一个七两和一个三两的空瓶，再没有其它工具。只用这三个瓶子怎样精确地把一斤油分成两个半斤油。 

选择广度优先算法来求解分油问题可以得到通过最少步骤完成分油的最优解。 

1）定义状态结点 

分油过程实际上就是将油从一个油瓶倒入另一个油瓶。分油过程中，各个油瓶中的油在不断变化，因此需要记录各个油瓶在不同状态所装油的多少。这里用一个数组bottle[3]存放当前油瓶中所装油的多少，不同油瓶用数组下标区分，数组元素bottle[0]是一斤油瓶中的油，bottle[1]是七辆油瓶中的油，而bottle[2]是三两油瓶中的油。 

此外，结点中用变量last还要记录每个状态是从哪一个状态变化来的，就是扩展出该结点的父结点编号。 

2）扩展规则 

     很明显，油瓶中必须有油才能把油倒出，同样油瓶必须不满才能将油倒入。分油过程中，将油从一个油瓶倒入另一个油瓶，可能的情形用变量i表示，一共只有6种，每种情形的序号与油瓶编号的关系如下表所示：

分油情形       i                                   0 1 2 3 4 5 

倒出油的油瓶 i/2                                0 0 1 1 2 2 

倒入油的油瓶 (i+3)/2 Mod  3               1 1 2 0 0 1  

3）重复结点和目标结点的判断 

    结点是否相同只需比较油瓶的状态。对于重复结点，需要将队列中的结点逐一检查，目标结点的判断则比较简单。

4）程序代码如下：

1 const maxn=100;  2 struct tnode{  3 int bottle[3];                  //当前油瓶装的油  4 int last;                          //父结点   5 int souc;                        //源瓶  6 int dest;                        //目标瓶   7 }state[maxn];                //状态队列    8 int capacity[3];               //油瓶容量 9 10 void init(){                      //初始化 11 state[0].bottle[0]=10; 12 state[0].bottle[1]=0; 13 state[0].bottle[2]=0; 14 state[0].last=0; 15 state[0].souc=0; 16 state[0].dest=0; 17 capacity[0]=10; 18 capacity[1]=7; 19 capacity[2]=3; 20 }21 22 bool expand(tnode& temp,int i,int j){           //扩展结点 23     if(temp.bottle[i]>0 && capacity[j]>temp.bottle[j]){  //如果源瓶中有油且目标瓶不满 24 if(temp.bottle[i]>=capacity[j]-temp.bottle[j]){  //源瓶的油大于目标瓶空余容量 25         temp.bottle[i]=temp.bottle[i]-capacity[j]+temp.bottle[j];//源瓶有余 26         temp.bottle[j]=capacity[j];              //目标瓶满 27 } 28 else{                                                       //否则 29         temp.bottle[j]=temp.bottle[j]+temp.bottle[i];    30         temp.bottle[i]=0;                            //源瓶空 31 } 32 temp.souc=i;                                         //记录源瓶于目标瓶 33 temp.dest=j; 34 return 1;                                                //可扩展,返回1 35     }  36     return 0; 37 }38 39 bool repeat(tnode state[],tnode temp,int tail){          //重复结点判断 40     for(int i=0;i<=tail;i++){ 41 for(int j=0;j<3;j++) 42       if(temp.bottle[j]!=state[i].bottle[j])break; 43           if(j==3)return 1; 44     } 45     return 0;  46 }47 48 bool finds(tnode temp){                                   //目标结点判断 49        if(temp.bottle[1]==5||temp.bottle[0]==5)return 1; 50        return 0; 51 }52 53 void printpath(tnode state[],int tail){                   //输出路径 54 if(tail>0){ 55       tail=state[tail].last; 56               printpath(state,tail); 57        cout<       cout<"<         for(int i=0;i<3;i++) 58             cout<            cout< } 59 }60 61 void bfs(){                                               //搜索主程序 62 tnode temp; 63 int head=0,tail=0,i; 64 while(head<=tail && tail       for(i=0;i<6;i++){ 65            temp=state[head]; 66   if(expand(temp,i/2,(i+3)/2%3)){ 67          if(repeat(state,temp,tail))continue; 68          state[++tail]=temp; 69          state[tail].last=head;      70         if(finds(temp)){                      //找到目标结点 71    tail++;                           //添加一个结点 72    state[tail].last=tail-1;    //最后结点的父结点是目标结点 73    printpath(state,tail);       //输出搜索路径 74                                         return;                           //找到最优解。退出程序 75                        }     76   } 77             } 78             head++; 79 }  80 } 81 void main() 82 { 83 init(); 84 bfs(); 85 } 86 执行结果为：  87    0     0    0-->0   10  0  0 88    1     0    0-->1    3  7  0 89    4     1    1-->2    3  4  3 90    6     4    2-->0    6  4  0 91    8     6    1-->2    6  1  3 92 10     8    2-->0    9  1  0 93 12   10    1-->2    9  0  1 94 14   12    0-->1    2  7  1 95 16   14    1-->2    2  5  3

   因为这里只求最优解，所以在找到解后，就退出程序，如果要求全部解，可将语句goto end换成break，并去掉语句end。

2.移动球的问题一

      10个盒子排成一列，前面两个是空的，后面盒子里相间放着4个红球和4个白球，若每次可移动任意两个相邻的球进入空盒，移动时两球不得更动原来次序。目标是将4个红球连在一起，而空盒位置不限。试编程，求出一种方案并输出每一次移动后的球的状态。下面是一种球放置的最初状态,其中O表示空盒子，A表示红球，B表示白球。 

O O A B A B A B A B 

1）定义状态结点 

     用一个数组ball[10]存放球的放置状态，变量last和spac分别存储父结点编号和第一个空盒的位置。 

2）扩展规则 

    因为只能同时移动两个球并且不改变顺序，因此球移动的目标是两个相连的空盒，否则不能移动。移动球后状态改变。 

3）重复结点与目标结点的判断 

     比较简单，只需顺次检查盒子状态即可。 

4）程序代码如下：

1 const maxn=250;  2 struct tnode{                              //状态结点  3        char ball[10];                      //盒子里球的状态  4        int last;                               //父结点  5        int spac;                             //第一个空格位置（从左起顺序为0、1...）  6 }state[maxn];                            //状态队列 7  8 void init(){                               //初始化  9 state[0].ball[0]=''O''; 10 state[0].ball[1]=''O''; 11 state[0].ball[2]=''A''; 12 state[0].ball[3]=''B''; 13 state[0].ball[4]=''A''; 14 state[0].ball[5]=''B''; 15 state[0].ball[6]=''A''; 16 state[0].ball[7]=''B''; 17 state[0].ball[8]=''A''; 18 state[0].ball[9]=''B'';  19 state[0].spac=0; 20 }21 22 bool expand(tnode& temp, int i){            //扩展结点  23 if((i-1==temp.spac)||(i==temp.spac)||(i+1==temp.spac))return 0; 24           //如果被移动的两个盒子包含空盒，则不能移动 25 temp.ball[temp.spac]=temp.ball[i];      //球放入空盒 26 temp.ball[temp.spac+1]=temp.ball[i+1]; 27 temp.ball[i]=''O''; 28 temp.ball[i+1]=''O''; 29 temp.spac=i;                            //记录新的空盒位置 30 return 1;   31 }32 33 bool rept(tnode state[],tnode temp,int k){  //判断重复结点 34 for(int i=0;i  for(int j=0;j<10;j++) 35    if(state[i].ball[j]!=temp.ball[j])break; 36   if(j==10)return 1; 37 } 38 return 0; 39 }40 41 bool find(tnode temp){                      //判断目标结点 42 int i=0,j=0; 43 while(i<10){ 44   if(temp.ball[i++]==''A''){ 45          j++; 46         if(j==4)return 1; 47   } 48   else 49        if(j>0)break;   50 } 51 return 0; 52 }53 54 void printpath(tnode state[], int tail){    //输出搜索路径   55 if(tail>0){ 56   tail=state[tail].last; 57   printpath(state,tail); 58   cout<  for(int i=0;i<10;i++)   59    cout<  cout< } 60 }61 62 void bfs(){                                  //搜索主程序  63 tnode temp;  64         int head=0,tail=0;    65 while(head<=tail && tail         for(int i=0;i<9;i++){ 66   temp=state[head]; 67   if(expand(temp,i)){ 68      if(rept(state,temp,tail))continue; 69            state[++tail]=temp; 70          state[tail].last=head; 71          if(find(temp)){ 72              tail++; 73              state[tail].last=tail-1; 74              printpath(state,tail); 75              cout<             break; 76          } 77   }   78            } 79            head++; 80 }  81 }82 83 void main(){ 84 init(); 85 bfs(); 86 }

3.移动球的问题二

     n个盒子被放成一圈，每个盒子按顺时针编号为1到n，每个盒子里都有一些球，且各个盒子里球的总数不超过n。这些球要按如下的方式移动：每一步可以将一个球从盒子中取出，放入一个相邻的盒子中。目标是用尽量少的移动使得所有的盒子中球的个数都不超过1。 

要最少移动次数，可采用广度优先搜索算法。 

1）定义状态结点 

     需要保存的状态是每个盒子里所放的球，以10个球为例，可用一个数组ball[10]存放盒子里放置球的状态，变量last存储父结点编号，而变量souc和dest则存放被移动的球移动前后所在盒子的编号。 

2）结点扩展规则 

     如果一个盒子里的球多于1个就可以将一个球移到相邻的盒子里去，既可向前（顺时针）移动，也可向后（逆时针）移动。球可以移到空盒子中，也可移到有球的盒子中。 

3）程序代码：

1 const maxn=500;  2 struct tnode{                             //状态结点  3        int ball[10];  4        int last;  5     int souc;  6     int dest;  7 }state[maxn]; 8  9 void init(){                              //初始化 10 state[0].ball[0]=6; 11 state[0].ball[1]=0; 12 state[0].ball[2]=0; 13 state[0].ball[3]=0; 14 state[0].ball[4]=1; 15 state[0].ball[5]=0; 16 state[0].ball[6]=0; 17 state[0].ball[7]=0; 18 state[0].ball[8]=0; 19 state[0].ball[9]=2; 20 } 21 bool repeat(tnode state[],tnode temp,int k){   //重复结点判断 22 for(int i=0;i<=k;i++){ 23   for(int j=0;j<10;j++)    24    if(temp.ball[j]!=state[i].ball[j])break; 25   if(j==10) return 1; 26 } 27    return 0; 28 } 29 bool find(tnode temp){                          //目标结点判断   30 for(int i=0;i<10;i++) 31   if(temp.ball[i]>1)break; 32 if(i==10) return 1; 33 else 34   return 0; 35 }36 37 void printpath(tnode state[],int tail){         //输出搜索路径 38 if(tail>0){ 39   tail=state[tail].last; 40   printpath(state,tail); 41   cout<" 42    <  for(int i=0;i<10;i++) 43    cout<  cout< } 44 }45 46 void bfs(){                                     //搜索主程序 47 tnode temp;  48 int head=0,tail=0,i;  49 while(head<=tail && tail  for(i=0;i<10;i++){ 50    int d=-1;                              //顺时针移动球 51    for(int j=0;j<=1;j++){ 52     temp=state[head]; 53     if(temp.ball[i]>1){ 54      temp.ball[i]--; 55      temp.ball[(i+d+10)%10]++; 56      temp.souc=i; 57      temp.dest=(i+d+10)%10; 58      d=-d;                          //逆时针移动球 59      if(repeat(state,temp,tail))continue; 60      state[++tail]=temp; 61      state[tail].last=head;                     62      if(find(temp)){ 63       tail++; 64       state[tail].last=tail-1; 65       printpath(state,tail); 66       cout<      break; 67      } 68     } 69    } 70   } 71   head ++; 72 }  73 }74 75 void main(){ 76 init(); 77 bfs(); 78 }

三.双向广度优先搜索算法

     广度优先算法需要从初始结点出发，逐步扩展才能找到问题的解。如果问题有解，它总是处在解答树的某一层上。解答树在扩展过程中，随着层次的增加，结点就越来越多，搜索的量也就迅速扩大，很容易产生数据溢出，导致搜索失败。下面来看一个例子：八数码问题(Eight-puzzle)。 

在3×3的棋盘上，摆有 8个棋子，在每个棋子上标有1～8中的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是，给出一种初始布局(初始状态)和目标布局(目标状态)，找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。设初始状态和目标状态如下： 

初始状态    1 2 3                 目标状态  2 8 3 

               8 0 4                              1 6 4 

               7 6 5                              7 0 5

     问题分析 ：由于题目要找的解是达到目标的最少步骤，因此可以采用BFS。以初始状态为搜索的出发点，把棋子移动一步后的布局全部找到，检查是否有达到目标的布局，如果没有，再从这些棋子移动一步的布局出发，找出棋子移动两步后的所有布局，再判断是否有达到目标的。依此类推，一直到某布局为目标状态为止，输出结果。由于是按棋子移动步数从少到多产生新布局的，所以找到的第一个目标一定是棋子移动步数最少的一个，也就是最优解。

1.定义结点

     用3×3的二维数组来表示棋盘的布局比较直观，如果将棋盘上的格子从左上角到右下角按0到8编号，就可用一维数组nums[9]来顺序表示棋盘上棋子的数字，空格用0表示，数组元素的下标是格子编号。状态结点除了棋子布局的数组外，还包括该布局的空格位置spac和该布局的父结点标识last。因此在程序中，定义状态结点为结构数据类型。

2.结点扩展规则

    棋子向空格移动实际上是空格向向相反方向移动。设空格当前位置是spac，则结点的扩展规则为： 

(1)空格向上移动，spac=spac-3；空格向左移动，spac=spac-1；空格向右移动，spac=spac+1；空格向下移动，spac=spac+3； 

    如果设向上移动k=1；向左移动k=2；向右移动k=3；向下移动k=4，则上述规则可归纳为一条： 空格移动后的位置为spac=spac-5+2*k。 

(2) 空格的位置<3，不能上移；空格的位置>5，不能下移；空格的位置是3的倍数，不能左移；空格的位置+1是3的倍数，不能右移； 

     广度优先搜索的过程中，新产生的结点放在队列后面，当前扩展的结点从队列前面选取。所以结点是按产生的先后次序进行扩展，深度大(步数多)的结点后扩展。程序中设置两个指针：队列的头指针Head和队列的尾指针tail，分别指向队列头和对列尾。

3. 搜索策略

1）从队列头取一个布局，按照向上、向右、向下和向左的顺序，检查移动空格后是否可以产生新的布局。 

2）如果移动空格后有新布局产生，则检查新布局是否已在队列中出现过，是则放弃，返回1）。 

3）如果新布局未在队列中出现过，就将它加入队列，再检查新布局是否目标布局，如果是，则找到解，程序结束。否则返回1）。 

4）程序代码：

1 struct tnode{  2 int nums[9];  3 int last;  4 int spac;   5 }state[10000];  6 tnode goal; 7  8 void init(){                     //初始化  9 state[0].nums[0]=1;          //初始状态 10 state[0].nums[1]=2; 11 state[0].nums[2]=3; 12 state[0].nums[3]=8; 13 state[0].nums[4]=0; 14 state[0].nums[5]=4; 15 state[0].nums[6]=7; 16 state[0].nums[7]=6; 17 state[0].nums[8]=5; 18 state[0].last=0;               19 state[0].spac=4;              //空格位置 20 goal.nums[0]=2;               //目标状态 21 goal.nums[1]=8; 22 goal.nums[2]=3; 23 goal.nums[3]=1; 24 goal.nums[4]=6; 25 goal.nums[5]=4; 26 goal.nums[6]=7; 27 goal.nums[7]=0; 28 goal.nums[8]=5; 29 goal.spac=6; 30 }31 32 bool expand(tnode& temp,int k){     //扩展结点     33 if(k==2 && (temp.spac==3 || temp.spac==6))return 0; 34 if(k==3 && (temp.spac==2 || temp.spac==5))return 0; 35 int i=temp.spac-5+2*k; 36 if(i<0 || i>8)return 0; 37 temp.nums[temp.spac]=temp.nums[i]; 38 temp.nums[i]=0; 39 temp.spac=i; 40 return 1; 41 }42 43 bool repeat(tnode state[],tnode temp,int tail){           //判断重复结点 44 int i,j; 45 for(i=0;i<=tail;i++){ 46   for(j=0;j<9;j++) 47    if(state[i].nums[j]!=temp.nums[j])break; 48         if(j==9)return 1; 49 } 50 return 0; 51 }52 53 bool find(tnode temp){                       //判断目标结点 54 if(temp.spac==goal.spac){ 55   for(int i=0;i<9;i++) 56    if(temp.nums[i]!=goal.nums[i])return 0; 57         return 1; 58 } 59 return 0; 60 }61 62 void printpath(tnode state[],int tail){       //输出路径 63 if(tail>0){ 64   tail=state[tail].last; 65   printpath(state,tail); 66   cout<  for(int i=0;i<9;i++){ 67    cout<   if((i+1)%3==0)cout<  } 68   cout< } 69 }70 71 void bfs(){                                   //搜索主程序 72 tnode temp; 73 int head=0,tail=0,i; 74 while(head<=tail && tail<10000){           75   for(i=1;i<5;i++){ 76    temp=state[head]; 77    if(expand(temp,i)){ 78     if(repeat(state,temp,tail))continue; 79     state[++tail]=temp; 80     state[tail].last=head; 81     if(find(temp)){ 82      tail++; 83      state[tail].last=tail-1; 84      printpath(state,tail); 85      cout<     return; 86     }     87    } 88   } 89   head++; 90 } 91 }92 93 void main(){ 94 init(); 95 bfs(); 96 }

程序执行结果为： 

       0                    2                    7                  15               26                 48        

     1  2  3           1  2  3           0  2  3           2  0  3           2  8  3           2  8  3 

     8  0  4  -->    0  8  4   -->   1  8  4  -->    1  8  4    -->  1  0  4    -->  1  6  4 

     7  6  5           7  6  5           7  6  5           7  6  5           7  6  5           7  0  5 

    结果表明，找到解总共搜索了48个结点。但实际上这里的目标状态是经过仔细选择的，如果更换一个目标状态，就会发现需要搜索的节点数量大大增加，例如目标状态是1  7  2  4  6  3  0  8  5，则需要搜索5496个结点才找到解，对于随机生成的初始状态和目标状态，大多数都搜索失败。 

     应当如何来减少搜索量的扩张呢？一个办法是采用双向广度优先搜索法。 

如果将上述问题中的初始状态和目标状态对换，仍然可以用广度优先搜索法找到解答，也就是说，搜索过程时可逆的。因为解答树靠近根部的层次结点少，所以如果从初始状态和目标状态同时向对方搜索，可以大大减少搜索结点数量，这正是双向广度优先搜索算法能够减少搜索量的依据。 

双向广度优先搜索算法的步骤如下： 

1）定义状态结点 

    与广度优先搜索算法相同。 

2）确定结点扩展规则 

    与广度优先搜索算法也相同。但需要定义两个队列，一个存储（从初始结点向目标结点）正向扩展的结点，另一个存储（从目标结点向初始结点）反向扩展的结点。 

3）搜索策略 

（1）从正向扩展的队列头取出一个结点，检查它按照扩展规则是否能够扩展，如果能则产生一个新结点。 

（2）检查新生成的结点，看它是否已在正向扩展的队列中存在，如果新结点已经在队列中出现过，就放弃这个结点。否则，如果新结点未曾在队列中出现过，则将它加入到队列尾。 

（3）检查新结点是否在反向扩展的队列中出现过，如果是，则两个队列在新结点处相遇，搜索成功，程序结束；若新不是，则继续。 

（4）对反向扩展的队列按（1）、（2）、（3）的步骤进行相同的处理。 

（5）未找到目标结点（两个队列位相遇）时回到第（1）步，再从队列头取出结点进行扩展......。 

4）程序代码如下）：

1 struct tnode{   2 int nums[9];   3 int last;   4 int spac;    5 };tnode statr[250],statb[250];  6   7 void init(){                            //初始化   8 statr[0].nums[0]=1;      //初始状态   9 statr[0].nums[1]=2;  10 statr[0].nums[2]=3;  11 statr[0].nums[3]=8;  12 statr[0].nums[4]=0;  13 statr[0].nums[5]=4;  14 statr[0].nums[6]=7;  15 statr[0].nums[7]=6;  16 statr[0].nums[8]=5;  17 statr[0].last=0;  18 statr[0].spac=4;  19 statb[0].nums[0]=1;       //目标状态  20 statb[0].nums[1]=7;  21 statb[0].nums[2]=2;  22 statb[0].nums[3]=4;  23 statb[0].nums[4]=6;  24 statb[0].nums[5]=3;  25 statb[0].nums[6]=0;  26 statb[0].nums[7]=8;  27 statb[0].nums[8]=5;  28 statb[0].spac=6;  29 } 30  31 bool expand(tnode& temp,int k){         //判断结点是否可扩展，可则扩展  32 if(k==2 && (temp.spac==3 || temp.spac==6))return 0;  33 if(k==3 && (temp.spac==2 || temp.spac==5))return 0;  34 int i=temp.spac-5+2*k;  35 if(i<0 || i>8)return 0;  36 temp.nums[temp.spac]=temp.nums[i];  37 temp.nums[i]=0;  38 temp.spac=i;  39 return 1;  40 } 41  42 bool repeat(tnode state[],tnode temp,int tail){        //重复结点判断  43 int i,j;  44 for(i=0;i<=tail;i++){  45   for(j=0;j<9;j++)  46    if(state[i].nums[j]!=temp.nums[j])break;  47   if(j==9)return 1;  48 }  49 return 0;  50 } 51  52 bool find(tnode state[],tnode temp,int& tail){  //判断目标结点（是否在另一队列中）     53 int i,j;  54 for(i=0;i<=tail;i++){  55   for(j=0;j<9;j++)  56    if(state[i].nums[j]!=temp.nums[j])break;  57   if(j==9){  58    tail=i;                                    //另一队列中相同结点编号  59    return 1;  60   }     61 }  62 return 0;  63 } 64  65 void printpath(tnode statr[],int tair,tnode statb[],int taib){  //输出路径  66 int p[20],k=0;  67 while(tair>0){                                              //将正向扩展队列逆转  68   p[k++]=tair;  69   tair=statr[tair].last;  70 }  71 p[k]=0;  72 for(int i=k;i>=0;i--){                                      //输出正向路径  73   cout<  cout<  for(int j=0;j<9;j++){  74    cout<         if((j+1)%3==0)cout<  }  75   cout< }  76 while(taib>0){                                              //输出逆向路径                77   taib=statb[taib].last;  78   cout<  cout<  for(int i=0;i<9;i++){  79    cout<   if((i+1)%3==0)cout<  }  80   cout< }  81 } 82  83 void bfs(){                                                       //搜索主程序  84 tnode temp;  85 int hear=0,tair=0,heab=0,taib=0,i;  86 while(hear<=tair && heab<=taib){  87   for(i=1;i<5;i++){                                         //正向扩展队列  88    temp=statr[hear];  89    if(expand(temp,i)){  90     if(repeat(statr,temp,tair))continue;       91     statr[++tair]=temp;  92     statr[tair].last=hear;  93     if(find(statb,statr[tair],taib)){  94      printpath(statr,tair,statb,taib);        95      return;  96     }      97    }  98   }  99   hear++; 100   for(i=1;i<5;i++){                                           //反向扩展队列   101    temp=statb[heab]; 102    if(expand(temp,i)){ 103     if(repeat(statb,temp,taib))continue; 104     statb[++taib]=temp; 105     statb[taib].last=heab; 106     if(find(statr,statb[taib],tair)){ 107      printpath(statr,tair,statb,taib);       108      return; 109     }     110    } 111   }   112   heab++; 113 } 114 }115 116 void main(){ 117 init(); 118 bfs(); 119 }

执行结果如下： 

0            0                  3              10                 18              32              60              

  1  2  3        1  2  3         1  2  3        1  2  3         1  2  3        1  2  3        1  2  3         

  8  0  4—>   8  4  0—>    8  4  5—>   8  4  5—>   8  4  5—>    0  4  5—>  4  0  5—>  

7  6  5        7  6  5         7  6  0         7  0  6        0  7  6        8  7  6         8  7  6

114（182）     42（74）      24             11             5               2            0          0 

1  2  3      1  2  3        1  2  3       1  2  0      1  0  2      1  7  2       1  7  2      1  7  2 

4  7  5-->  4  7  5—>  4  7  0—> 4  7  3 —> 4  7  3—> 4  0  3—> 4  6  3—> 4  6  3 

8  0  6        8  6  0       8  6  5      8  6  5       8  6  5       8  6  5       8  0  5      0  8  5

结果表明，两个方向的搜索，需要扩展的节点数量大大减少，总共不到300个结点（括弧中是结点本身的编号，即它在队列中的位置）。

 

 转载自