首页 > 代码库 > 双向广搜 开始!!!

双向广搜 开始!!!

先简单的了解一下,双向广搜很好理解,就是从两端一起搜,如果遇到之前已经搜到过的状态,就相当于已经有解了,这样就会节省一半的内存和时间,并且代码复杂度并不高。只需要在正常的基础上多开一个域,保存这个点是从起始状态还是终止状态拓展的。当然双向广搜中状态的判断需要一些技巧,现在还没有总结出什么。

 

八数码问题:

      很经典的一种双向广搜,因为只有九个数,所以用康托展开作为hash值。拓展时,如果这个hash值已经访问过,就判断,如果是两条路过来的就输出,否则就继续做;对于没有访问过的hash值就可以添加到队列里,扩展方向和头指针的一样。如果要输出路径的话,就用递归输出,分别从两边输出。

技术分享
#include<iostream>#include<cstdio>using namespace std;struct use{    int map[3][3],xx,yy,can,pre,kind;}que[1000000],st,sta;int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},step[1000000]={0},dis[1000000]={0},mi[9]={0},c[10]={0},    cc[1000000];char ss[9];bool dodo=false;int cantor(struct use num){    int i,j,kind=0,ge;    for (i=0;i<3;++i)      for (j=0;j<3;++j)        c[i*3+j+1]=num.map[i][j];    for (i=1;i<=8;++i)    {      ge=0;      for (j=i+1;j<=9;++j)            if (c[i]>c[j]) ++ge;      kind+=mi[9-i]*ge;    }    return kind;}void print1(int x){    if (que[x].pre==0) return;    print1(que[x].pre);    if (que[x].kind==0) printf("r");    if (que[x].kind==1) printf("l");    if (que[x].kind==2) printf("d");    if (que[x].kind==3) printf("u");}void print2(int x){    if (que[x].pre==0) return;    if (que[x].kind==0) printf("l");    if (que[x].kind==1) printf("r");    if (que[x].kind==2) printf("u");    if (que[x].kind==3) printf("d");    print2(que[x].pre);}void bfs(){    int i,j,head,tail,ans=0,t;    bool ff=false;    head=1;tail=0;    i=cantor(st);step[i]=1;cc[i]=1;    ++tail;que[tail]=st;que[tail].can=i;que[tail].kind=que[tail].pre=0;    i=cantor(sta);step[i]=2;cc[i]=2;    ++tail;que[tail]=sta;que[tail].can=i;que[tail].kind=que[tail].pre=0;    while(head<=tail)    {        st=que[head];        t=st.can;        for (i=0;i<4;++i)        {            sta=st;            sta.xx=st.xx+dx[i];            sta.yy=st.yy+dy[i];            if (sta.xx>=0&&sta.xx<3&&sta.yy>=0&&sta.yy<3)            {              j=sta.map[st.xx][st.yy];sta.map[st.xx][st.yy]=sta.map[sta.xx][sta.yy];              sta.map[sta.xx][sta.yy]=j;              j=cantor(sta);              if (step[j]==0)              {                   ++tail;que[tail]=sta;                   dis[j]=dis[t]+1;                   que[tail].can=j;                   step[j]=step[t];                   que[tail].pre=head;                   que[tail].kind=i;                   cc[j]=tail;                   if (dis[j]>100)                    {                       dodo=true;                       return;                   }              }              else              {                  if (step[j]!=step[t])                  {                      if (step[j]==1)                      {                        print1(cc[j]);                        if (i==0) printf("l");                        if (i==1) printf("r");                        if (i==2) printf("u");                        if (i==3) printf("d");                      print2(head);                    }                    else                    {                        print1(head);                        if (i==0) printf("r");                        if (i==1) printf("l");                        if (i==2) printf("d");                        if (i==3) printf("u");                        print2(cc[j]);                    }                      ff=true;                      break;                  }              }            }        }        if (ff) break;        ++head;    }}int main(){    int i,j;    char ch;    for (i=0;i<3;++i)      for (j=0;j<3;++j)      {          while(scanf("%c",&ch))              if (ch!= )               {                  ss[i*3+j]=ch;                  break;              }          if (ss[i*3+j]==x) st.map[i][j]=0;        else          st.map[i][j]=ss[i*3+j]-0;        if (st.map[i][j]==0)         {          st.xx=i;st.yy=j;        }      }    ss[0]=1;ss[1]=2;ss[2]=3;ss[3]=4;ss[4]=5;ss[5]=6;ss[6]=7;ss[7]=8;ss[8]=0;    for (i=0;i<3;++i)      for (j=0;j<3;++j)      {          sta.map[i][j]=ss[i*3+j]-0;        if (sta.map[i][j]==0)         {            sta.xx=i;sta.yy=j;        }      }    mi[1]=1;    for (i=2;i<=8;++i)      mi[i]=mi[i-1]*i;    if (cantor(st)!=cantor(sta))    {       bfs();       if (dodo) printf("unsolvable\n");    }    else printf("0\n");}
poj1077(输出路径)

这道题中有无解的情况,如果一边的步数超过100就看做无解。当然有一种不知道证明的很正确的判断方法,就是如果初始状态和目标状态的奇偶性不同就是无解。

双向广搜 开始!!!