加载中…
个人资料
qingge
qingge
  • 博客等级:
  • 博客积分:0
  • 博客访问:5,818
  • 关注人气:2
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

双向广搜

(2011-08-31 16:45:24)
标签:

八数码

康托

双向广搜

逆序数

杂谈

分类: ACM

 

  Eight   

   题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1043

   讲到双向广搜,那就不能不讲经典的八数码问题,有人说不做此题人生不完整 。

   所谓双向广搜,就是初始结点向目标结点和目标结点向初始结点同时扩展,直至在两个扩展方向上出现同一个结点,搜索结束。它适用的问题是,扩展结点较多,而目标结点又处在深沉,如果采用单纯的广搜解题,搜索量巨大,搜索速度慢是可想而知的,同时往往也会出现内存空间不够用的情况,这时双向广搜的作用就体现出来了。双向广搜对单纯的广搜进行了改良或改造,加入了一定的“智能因数”,使搜索能尽快接近目标结点,减少了在空间和时间上的复杂度。

   当在讲题前,不得不先给大家补充一点小知识,大家都知道搜索的题目其中难的一部分就是事物的状态,不仅多而且复杂,要怎么保存每时刻的状态,又容易进行状态判重呢,这里提到了一种好办法   ------康托展开(只能针对部分问题)

 

康托展开

康托展开式:

  X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0!

 其中,a为整数,并且0<=ai<i(1<=i<=n)。

 

例:

问:1324是{1,2,3,4}排列数中第几个大的数?

解:第一位是1小于1的数没有,是0个 0*3! 第二位是3小于3的数有1和2,但1已经在第一位了,所以只有一个数2 1*2! 。第三位是2小于2的数是1,但1在第一位,所以有0个数 0*1! ,所以比1324小的排列有0*3!+1*2!+0*1!=2个,1324是第三个大数。

 

好吧,先看下代码实现:

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

 

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;   // 返回该数是第几大

}

好的,现在再来看看双向广搜模版:

void TBFS()

{

       bool found=false;

       memset(visited,0,sizeof(visited));  // 判重数组

       while(!Q1.empty())  Q1.pop();   // 正向队列

       while(!Q2.empty())  Q2.pop();  // 反向队列

       //======正向扩展的状态标记为1,反向扩展标记为2

       visited[s1.state]=1;   // 初始状态标记为1

       visited[s2.state]=2;   // 结束状态标记为2

       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 BFS_expand(queue<Status> &Q,bool flag)

 

       s=Q.front();  // 从队列中得到头结点s

      Q.pop()

      for( 每个s 的子节点 t )

     {

             t.state=Gethash(t.temp)  // 获取子节点的状态

             if(flag)   // 在正向队列中判断

             {

                      if (visited[t.state]!=1)// 没在正向队列出现过

                   

                           if(visited[t.state]==2)  // 该状态在反向队列中出现过

                          {

                                 各种操作;

                                 found=true;

                                 return;

                           }

                            visited[t.state]=1;   // 标记为在在正向队列中

                            Q.push(t);  // 入队

                      

            

             else    // 在正向队列中判断

             {

                      if (visited[t.state]!=2) // 没在反向队列出现过

                   

                           if(visited[t.state]==1)  // 该状态在正向向队列中出现过

                           {

                                  各种操作;

                                  found=true;

                                  return;

                            }

                             visited[t.state]=2;  // 标记为在反向队列中

                             Q.push(t);  // 入队

                      

             }             

                   

 

好的,现在开始说说八数码问题

其实,Eight有一个很重要的判断,那就是逆序数的判断。如果i>j,并且ai<aj,那么定义(i,j)为一个逆序对,而对于一个状态排列中所含的逆序对的个数总和就是逆序数。而本题的逆序数的奇偶性的判断是至关重要的:

如果x在同一行上面移动那么1~8的逆序数不变

如果x在同一列上面移动,每次逆序数增加偶数个或者减少偶数个

因为目标结点的状态的逆序数为0,为偶数,所以每次访问到的状态的逆序数也必须为偶数,保持奇偶性性质,否则就不必保存该状态。

 

#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;

}

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
前一篇:背包问题
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇背包问题
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有