双向广搜

2016-07-13 18:52:08 -0400

http://blog.sina.cn/dpool/blog/s/blog_8627bf080100ticx.html?vt=4

http://blog.sina.com.cn/s/blog_8627bf080100ticx.html

#include<IOSTREAM>
#include<queue>
using namespace std;
#define N 10
#define MAX 365000 

char visited[MAX];
int father1[MAX];  // 保存正向搜索当前状态的父亲状态结点
int father2[MAX];  // 保存反向搜索当前状态的父亲状态结点
int move1[MAX];    // 正向搜索的方向保存
int move2[MAX];   //  反向搜索的方向保存

struct Status   // 结构
{
       char eight[N];  // 八数码状态
       int space;     // x 位置
       int state;    // hash值,用于状态保存与判重 
};

queue<Status> Q1;  // 正向队列
queue<Status> Q2;  // 反向队列
Status s,s1,s2,t;

bool found;  // 搜索成功标记

int state;   // 正反搜索的相交状态

int factory[]={1,1,2,6,24,120,720,5040,40320,362880};  // 0..n的阶乘

int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

int Gethash(char eight[])  // 康托展开(获取状态,用于判重)
{
       int k=0;
       for(int i=0;i<9;i++)
       {
              int t=0;
              for(int j=i+1;j<9;j++)
                     if(eight[j]<eight[i])
                            t++;
              k+=(t*factory[9-i-1]);
       }
       return k;
}

int ReverseOrder(char eight[])  // 求状态的逆序数
{
       int i,j,num=0;
       for(i=0;i<9;i++)
       {
              for(j=0;j<i;j++)
              {
                     if(int(eight[i])==9)

                     {

                            break;

                     }

                     if(int(eight[j])==9)

                            continue;

                     if(int(eight[j])>int(eight[i]))

                            num++;

              }

       }

       num=num%2;
       return num;
}

void BFS_expand(queue<Status> &Q,bool flag)  // 单向广度搜索
{
       int k,x,y;
       s=Q.front();
       Q.pop();
       k=s.space;
       x=k/3;
       y=k%3;
       for(int i=0;i<4;i++)
       {
              int xx=x+dir[i][0];
              int yy=y+dir[i][1];
              if(xx>=0 && xx<=2 && yy>=0 && yy<=2)
              {
                     t=s;
                     t.space=xx*3+yy;   // 计算x位置
                     swap(t.eight[k],t.eight[t.space]);  // 交换两个数位置
                     t.state=Gethash(t.eight);
                     if(flag)  // 在正向队列中判断

                     {

                            if(visited[t.state]!=1 && ReverseOrder(t.eight)==0)  // 未在正向队列出现过并且满足奇偶性

                            {
                                   move1[t.state]=i;  // 保存正向搜索的方向
                                   father1[t.state]=s.state; // 保存正向搜索当前状态的父亲状态结点
                                   if(visited[t.state]==2)   //  当前状态在反向队列中出现过
                                   {
                                          state=t.state;  // 保存正反搜索中相撞的状态(及相交点)
                                          found=true;    // 搜索成功
                                          return;
                                   }

                                   visited[t.state]=1;   // 标记为在正向队列中
                                   Q.push(t);  // 入队

                            }

                     }

                     else  // 在反向队列中判断

                     {
                            if(visited[t.state]!=2 && ReverseOrder(t.eight)==0)   // 未在反向队列出现过并且满足奇偶性

                            {
                                   move2[t.state]=i;  // 保存反向搜索的方向
                                   father2[t.state]=s.state; // 保存反向搜索当前状态的父亲状态结点
                                   if(visited[t.state]==1)  //  当前状态在正向队列中出现过
                                   {
                                          state=t.state;  // 保存正反搜索中相撞的状态(及相交点)
                                          found=true;   // 搜索成功
                                          return;
                                   }
                                   visited[t.state]=2;  // 标记为在反向队列中
                                   Q.push(t);   // 入队

                            }

                     }

              }

       }

       return ;

}

void TBFS()            // 双向搜索

{

       memset(visited,0,sizeof(visited));
       while(!Q1.empty())
              Q1.pop();

       while(!Q2.empty())
              Q2.pop();

       visited[s1.state]=1;   // 初始状态
       father1[s1.state]=-1;
       visited[s2.state]=2;   // 目标状态
       father2[s2.state]=-1;
       Q1.push(s1);
       Q2.push(s2);
       while(!Q1.empty() || !Q2.empty())
       {

              if(!Q1.empty())
                     BFS_expand(Q1,true);

              if(found)
                     return ;

              if(!Q2.empty())
                     BFS_expand(Q2,false);

              if(found)
                     return ;

       }

}

void PrintPath1(int father[],int move[])   // 从相交状态向初始状态寻找路径

{

       int n,u;
       char path[1000];
       n=1;
       path[0]=move[state];
       u=father[state];
       while(father[u]!=-1)
       {
              path[n]=move[u];
              n++;
              u=father[u];

       }

       for(int i=n-1;i>=0;--i)
       {       

              if(path[i] == 0)           
                     printf("u");       

              else if(path[i] == 1)           
                     printf("d");       

              else if(path[i] == 2)           
                     printf("l");       

              else           
                     printf("r");   

       }

}

void PrintPath2(int father[],int move[])   // 从相交状态向目标状态寻找路径

{

       int n,u;
       char path[1000];
       n=1;
       path[0]=move[state];
       u=father[state];
       while(father[u]!=-1)
       {
              path[n]=move[u];
              n++;
              u=father[u];
       }

       for(int i=0;i<=n-1;i++)
       {       
              if(path[i] == 0)           
                     printf("d");       

              else if(path[i] == 1)           
                     printf("u");       

              else if(path[i] == 2)           
                     printf("r");       

              else           
                     printf("l");   

       }

}

int main()
{
       int i;
       char c;   
       while(scanf(" %c",&c)!=EOF)
       {
              if(c=='x')
              {
                     s1.eight[0]=9;
                     s1.space=0;

              }
              else
                     s1.eight[0]=c-'0';

              for(i=1;i<9;i++)
              {
                     scanf(" %c",&c);
                     if(c=='x')
                     {
                            s1.eight[i]=9;
                            s1.space=i;
                     }

                     else
                            s1.eight[i]=c-'0';

              }

              s1.state=Gethash(s1.eight);
              for(int i=0;i<9;i++)

                     s2.eight[i]=i+1;

              s2.space=8;

              s2.state=Gethash(s2.eight);

              if(ReverseOrder(s1.eight)==1)

              {
                     cout<<"unsolvable"<<endl;
                     continue;
              }
              found=false;
              TBFS();
              if(found)   // 搜索成功

              {
                     PrintPath1(father1,move1);
                     PrintPath2(father2,move2);

              }
              else
                     cout<<"unsolvable"<<endl;

              cout<<endl;

       }
       return 0;
}
main.cpp (7.6 KiB) | Read | Meta | +

Word Count: 7,412

«Newer      Older»
Comment:
Name:

Back to home

Subscribe | Register | Login | 中文 | N