双向广度优先搜索

广度优先搜索遵循从初始结点开始一层层扩展直到找到目标结点的搜索规则，它只能较好地解决状态不是太多的情况，承受力很有限。如果扩展结点较多，而目标结点又处在较深层，采用前文叙述的广度搜索解题，搜索量巨大是可想而知的，往往就会出现内存空间不够用的情况。双向搜索和A算法对广度优先的搜索方式进行了改良或改造，加入了一定的“智能因素”，使搜索能尽快接近目标结点，减少了在空间和时间上的复杂度。

　　(1)搜索过程
　　有些问题按照广度优先搜索法则扩展结点的规则，既适合顺序，也适合逆序，于是我们考虑在寻找目标结点或路径的搜索过程中，初始结点向目标结点和目标结点向初始结点同时进行扩展—，直至在两个扩展方向上出现同一个子结点，搜索结束，这就是双向搜索过程。出现的这个同一子结点，我们称为相交点，如果确实存在一条从初始结点到目标结点的最佳路径，那么按双向搜索进行搜索必然会在某层出现“相交”，即有相交点，初始结点一相交点一目标结点所形成的一条路径即是所求路径。

      (2)结点扩展顺序
    双向扩展结点，在两个方向的扩展顺序上，可以轮流交替进行，但由于大部分的解答树并不是棵完全树，在扩展完一层后，下一层则选择结点个数较少的那个方向先扩展，可以克服两个方向结点生成速度不平衡的状态，明显提高搜索效率。

　　(3)数据结构
    单向广度优先搜索需建立两个表OPEN和CLOSED，用来存储生成结点和已扩展结点，双向搜索从两个方向进行扩展，我们建立两个二维表OPEN，CLOSED，OPEN[1]，CLOSED[1]， OPEN[2]，CLOSED[2]分别存储两个方向上的生成结点和已扩展结点，OPEN仍然是具有“先进先出”的队列结构。为编程方便，我们采用基于广度优先搜索算法的双向，建立三个二维指针：Q1，Q2，Q3其作用如下：
    Q1[1]，Q1[2]：分别指向两个方向上当前待扩展层的第一个结点。
    Q2[1]，Q2[2]：分别指两个方向上队尾新产生的结点。
    Q3[1]，Q3[2]：分别指向两个方向上下一层的第一个结点位置。
    为了区分当前搜索方向，设方向标志：
    t=1表示处于正向搜索，t=2表示处于逆向搜索。
    Fail—有一个方向搜索失败时，为真，并且结束搜索过程，否则为假。
    I—全局变量，指向当前要扩展的结点。

　　(4)算法描述

初始化visited数组，将所有点的值设为false；//visited数组用来保存所有点的访问情况
visited[start]=true;//start为起始点
queue<type> search;//用来保存待搜索点的队列
search.push(start)；
while(!search.empty())
{
      v=search.front();
      search.pop();   //弹出一个点处理，用v表示
      for(每一个v的相邻点)
         if(!visited[v]){
            visited[v]=true;
            search.push(v);
         }
}

以上代码部分只是所有点的遍历，为的是理解思想，并没有加入达到终止条件返回步数(这很关键)，我会在下面双向广度优先搜索加上。
双向广度优先搜索则是从出发点和目标点分别向后向前搜索，当相遇时则终止。在code时关键问题有：怎么记录当前搜索步数；怎么判断和什么时候判断达到终止条件；搜索时向前向后的顺序。对于搜索函数伪代码(不考虑点的存储结构)如下：

if(start==finish)
      return 0;
初始化visited数组里每个值为0; //这里visited值为1则为向后搜索过的值，为2则为向前搜索过的值
初始化起始点start.step=true; //这里step属性为真则表示为某一搜索步数中的最后一个点,例如对于poj1915中第2步有八个点，只有第八个点的step为true,其余为false
初始化目标点finish.step=true;
visited[start]=true;
visited[finish]=true;
queue<type> frontSearch;       //记录从前向后搜索的队列
queue<type> backSearch;       //记录从后向前搜索的队列
fstep=0;                                    //记录从前向后搜索的步数
bstep=0;                                   //记录从后向前搜索的步数
frontSearch.push(start);
backSearch.push(finish);
while(!frontSearch.empty() || !backSearch.empty())
    {
        if(!frontSearch.empty())
                {
                     do{
                              current=frontSearch.front();//从队列中弹出当前搜索的点
                              frontSearch.pop();
                              for(每一个current的相邻点v){
                                    if(visited[v]==2)
                                          return fstep+bstep+1;//如果遇到了从后向前搜索搜过的点则终止，并且返回总步数
                                    if(!visited[v]){
                                          visited[v]=1;
                                          frontSearch.push(v);
                                    }
                              }
                          }while(!current.step)               //同一步的点已经全部搜完，结束循环
                           fstep++;                                //增加从前向后搜索的步数
                           current=frontSearch.front();
                           frontSearch.pop();
                           current.step=true;
                           frontSearch.push(current);      //将当前步数最后一个点的step属性设为true；

                 }
                  if(!backSearch.empty())
                {
                     do{
                              current=backSearch.front();//从队列中弹出当前搜索的点
                              backSearch.pop();
                              for(每一个current的相邻点v){
                                    if(visited[v]==1)
                                          return fstep+bstep+1;//如果遇到了从前向后搜索搜过的点则终止，并且返回总步数
                                    if(!visited[v]){
                                          visited[v]=2;
                                          backSearch.push(v);
                                    }
                              }
                          }while(!current.step)               //同一步的点已经全部搜完，结束循环
                           bstep++;                                //增加从后向前搜索的步数
                           current=backSearch.front();
                           backSearch.pop();
                           current.step=true;
                           backSearch.push(current);      //将当前步数最后一个点的step属性设为true；

                 }
}