由八数码问题引入。对BFS有更深考虑

12号到今天共研究八数码问题poj1077，首先用的是普通BFS，遇到很多问题，开始用一个二级指针作为结构成员，知道了二级指针与二维数值名的不同！http://write.blog.csdn.net/postedit！讲得不错。发现自己代码能力渣死！进入正题，用BFS过不了，先学习了八数码问题有解条件，并扩展到N数码有解问题。做到奇数偶数剪枝，过不了，太慢，于是学习了HASH判重，学习了康托展开（排列与数字的一一对应关系），效率大大增加！但是别人这样过了都，我是过不了啊！于是去学双广！没怎么看明白，，，很想放弃了！于是去学习了A*算法！（启发式搜索），46ms,BFS是最普通的A*，那么，我用优先队列优化，设置启发函数，把优先级高的先出队！本质已经破坏了BFS的分层搜索，倒是有点DFS了，我名之为bdfs!，有方向性！这样找一组解很容易！不用遍历所有！

于是去切了骑士问题，先是8格的的，再是n格的，接下！

#include<iostream> //优先（小的优先）队列BFS+hash判重+奇数偶数剪枝

#include<queue>

#include<string>

#include<cstdio>

#include<set>

#include<cstring>

using namespace std;

string a;

int f[4][2]={0,1,0,-1,1,0,-1,0};//方向

bool state[362881];

int fac[10]={1,1,2,6,24,120,720,5040,40320,362880};

struct xy

{

    string aa;    //当前状态

    int x;         //空格的坐标

    int y;

    int abs_to_end; //和目标数相同的方块数目！

    string s;      // 字符串，保存当前移动情况

    bool operator < (const xy & now) const //自定义离目标小的优先！

    {

        return now.abs_to_end>abs_to_end;

    }

};

int get_abs(string aa) //只要第一次获得，其他改变修改

{

    int res=0;

   for(int i=1;i<=9;i++)

        {

            if(aa[i]!='9'&&aa[i]==('0'+i))res++;

        }

     return res;

}

bool has_solution()  //无解条件，奇偶剪枝！

{

    int t[9];int count=0;

      for(int i=0;i<3;i++)

        for(int j=0;j<3;j++)

            t[count++]=a[i*3+j]-'0';

    count=0;

   for(int i=0;i<9;i++)

     for(int j=i+1;j<9;j++)

        if(t[j]!=9&&t[i]!=9&&t[j]<t[i])count++;

   if(count%2==0)return 1;

   return 0;

}

string bfs(int ox,int oy)          //

{

    priority_queue<xy>q;

    xy dian; dian.x=ox;dian.y=oy; //赋初值

    dian.s="";               //首地址的赋值，二维数组必先从一维建立。用的还是同一个！

    for(int i=0;i<3;i++)

       {

         for(int j=0;j<3;j++)

           {

              dian.aa+=a[i*3+j];

           }

       }

     dian.abs_to_end=get_abs(dian.aa);

    q.push(dian);

    if(dian.aa=="123456789")return dian.s;

    while(!q.empty())

    {

         xy temp=q.top();

         q.pop();            //取队首拓展

        for(int i=0;i<4;i++)

          {                             // xy next=temp;这样只是完全赋值，指针指的是同一块地址！

              xy next(temp);

              int space=next.x*3+next.y;

              next.x=next.x+f[i][0];           //四个方向拓展。

              next.y=next.y+f[i][1];

              if(next.x>=0&&next.x<3&&next.y>=0&&next.y<3)

               {

                  if(i==0)

                   {

                       if(next.s.size()>0&&'l'==next.s[next.s.size()-1])continue;

                       next.s+="r";

                       if(next.aa[space+1]=='1'+space+1)next.abs_to_end--;

                      if(next.aa[space+1]=='1'+space)next.abs_to_end++;

                        next.aa[space]=next.aa[space+1];

                        next.aa[space+1]='9';

                   }

                   else if(i==1)

                   {

                       if(next.s.size()>0&&'r'==next.s[next.s.size()-1])continue;

                       next.s+="l";

                       if(next.aa[space-1]=='1'+space-1)next.abs_to_end--;

                       if(next.aa[space-1]=='1'+space)next.abs_to_end++;

                        next.aa[space]=next.aa[space-1];

                        next.aa[space-1]='9';

                   }

                    else if(i==2)

                   {

                       if(next.s.size()>0&&'u'==next.s[next.s.size()-1])continue;

                       next.s+="d";

                         if(next.aa[space+3]=='1'+space+3)next.abs_to_end--;

                         if(next.aa[space+3]=='1'+space)next.abs_to_end++;

                        next.aa[space]=next.aa[space+3];

                        next.aa[space+3]='9';

                   }

                    else if(i==3)

                   {

                       if(next.s.size()>0&&'d'==next.s[next.s.size()-1])continue;

                        next.s+="u";

                       if(next.aa[space-3]=='1'+space-3)next.abs_to_end--;

                       if(next.aa[space-3]=='1'+space)next.abs_to_end++;

                        next.aa[space]=next.aa[space-3];

                        next.aa[space-3]='9';

                   }

                if(next.aa=="123456789")return next.s;

                string ts=next.aa;                 //int hash(string ts)

                    int res=0;

                     for(int i=0;i<9;i++)

                       {

                           int count=0;

                          for(int j=i+1;j<9;j++)

                                if(ts[j]<ts[i])count++;

                              res+=count*fac[9-i-1];

                        }

                   if(state[res])continue;

                    state[res]=true;

                q.push(next);

               }

          }

    }

}

int main()

 {

    string ta;

    while(getline(cin,ta))

  {

     int ox,oy;

     a.clear();

     for(int i=0;i<ta.size();i++)

        {

            if(ta[i]=='x') a+='9';

            else if(ta[i]!=' ')a+=ta[i];

        }

    for(int i=0;i<a.size();i++)

     {

        if(a[i]=='9'){ox=i/3;oy=i%3;}

     }

    memset(state,0,sizeof(state));

    if(!has_solution())cout<<"unsolvable"<<endl;

    else

    {

        cout<<bfs(ox,oy)<<endl;

    }

  }

    return  0;

}

巴特西

由八数码问题引入。对BFS有更深考虑

最新文章

热门文章