八数码问题(A*&&双向BFS)

 

题目地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=217

      首先说一下八数码问题的可解性。

       1.互换2个非零位置，状态的逆序奇偶性将保持不变。

       2.互换0和另一个非零位置，状态的逆序奇偶性将发生颠倒。

       3.因此，如果目标状态和起始状态的逆序奇偶性相同，问题可解，否则不可解。所以对于八数码问题的一个目标状态有9!/2种可解状态

       逆序奇偶性可以这样来求，将状态转化了数列，然后去掉X位，然后对于每一位，计算在它之前小于它的个数，每一位对应的值之和就是逆序奇偶数。

      A*算法具体不多说了，它的精髓在于f(n)=g(n)+h(n),中估值函数h(n)的设计。值的注意的是：

      如果估价值h(n)<= n（到目标节点的实际步长），这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。

　　如果 估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

     因此在实际使用的时候应该更具需要来设计h(n)

     在zoj_1217中，为了不TLE，选择h(n)=20*dis(欧几里德距离)，但是得不到最优解

zoj_1217:

#include<cstdio>
#include<algorithm>
#include<queue>
#include<string.h>
#include<string>
#include<math.h>
#include<iostream>
using namespace std;
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
string path[4]={"d","r","u","l"};
int dp[10]={1,1,2,6,24,120,720,5040,40320,362880};
int final[9]={1,2,3,4,5,6,7,8,0};
bool hashtable[362885];
class state
{
public:
    int a[9],exp,zero,dept;
    string path;
    state(){};
    state(int num[9])
    {
        for(int i=0;i<9;++i)
            a[i]=num[i];
    }
    void swapn(int c)
    {
        swap(a[zero],a[c]);
    }
};
struct cmp
{
    bool operator()(const state x,const state y)
    {
        return x.exp>y.exp;
    }
};
int getHash(int code[9])
{
    int sum=0;
    bool flag[9];
    int k;
    memset(flag,false,sizeof(flag));
    for(int i=0;i<9;++i)
    {
        k=0;
        for(int j=code[i]+1;j<9;++j)
        {
            if(!flag[j])
                ++k;
        }
        sum+=k*dp[8-i];
        flag[code[i]]=true;
    }
    return 362879-sum;
}
int Eudis(int a[9])
{
    int dis=0;
    for(int i=0;i<9;++i)
    {
        for(int j=0;j<9;++j)
        {
            if(a[i]==final[j])
            {
                dis+=fabs(1.0*(i/3-j/3))+fabs(1.0*(i%3-j%3));
                break;
            }
        }
    }
    return dis/2;
}
state ans;
bool bfs(state ori)
{
    priority_queue<state,vector<state>,cmp >open;
    //queue<state>open;
    open.push(ori);
    while(!open.empty())
    {
        state t=open.top();
        open.pop();
        if(Eudis(t.a)==0)
        {
            ans=t;
            return true;
        }
        for(int i=0;i<4;++i)
        {
            int row=t.zero/3;
            int col=t.zero%3;
            int arow=row+next[i][1];
            int acol=col+next[i][0];
            if(arow<3&&arow>=0&&acol<3&&acol>=0)
            {
                int sw=arow*3+acol;
                state tmp=t;
                tmp.swapn(sw);
                tmp.zero=sw;
                int hcode=getHash(tmp.a);
                if(hashtable[hcode])
                    continue;
                hashtable[hcode]=true;
                int dis=50*Eudis(tmp.a);
                ++tmp.dept;
                tmp.exp=dis+tmp.dept;
                tmp.path+=path[i];
                open.push(tmp);
            }
        }
    }
    return false;
}
void test(bool flag[9],int b,int num[9])
{
    if(b>8)
    {
        printf("%d\n",getHash(num));
        return;
    }
    for(int i=0;i<9;++i)
    {
        if(!flag[i])
        {
            flag[i]=true;
            num[b]=i;
            test(flag,b+1,num);
            flag[i]=false;
        }
    }
}
bool isSolveable (int statue[9])
{
    int num=0;
    for (int i=1;i<=8;++i)
        {
            if(statue[i]==0)
            continue;
        for(int j=0;j<i;++j)
            {
                    if(statue[j]==0)
                continue;
            if(statue[i]>statue[j])
                ++num;
            }
        }
        if (num%2==1) return false;
        return true;
}

int main()
{
    //bool ff[9];
    //int nn[9];
    //memset(ff,false,sizeof(ff));
    //memset(nn,false,sizeof(nn));
    //test(ff,0,nn);
    //int a[9]={0,1,2,3,4,5,6,7,8};
    //int b[9]={8,7,6,5,4,3,2,1,0};
    //printf("%d\n",getHash(b));
    freopen("e:\\zoj\\zoj_1217.txt","r",stdin);
    while(1)
    {
        memset(hashtable,0,sizeof(hashtable));
        int flag=0;
        int num[9];
        int zero;
        char c;
        for(int i=0;i<9;++i)
        {
            if(scanf(" %c",&c)==EOF)
                return 0;
            if(c=='x')
            {
                zero=flag;
                num[flag++]=0;
            }
            if(c<='9'&&c>='1')
                num[flag++]=c-48;
            if(flag>=9)
                break;
        }
        state ori(num);
        ori.exp=20*Eudis(num);
        ori.zero=zero;
        ori.dept=0;
        int hcode=getHash(num);
        hashtable[hcode]=true;
        if(!isSolveable(num))
            printf("unsolvable\n");
        else
        {
        bool f=bfs(ori);
        int l=ans.path.length();
        for(int i=0;i<l;++i)
            printf("%c",ans.path[i]);
        puts("");
        }
    }
}

 双向BFS：

 

#include<cstdio>
#include<algorithm>
#include<queue>
#include<string.h>
#include<string>
#include<iostream>
using namespace std;
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
string path[4]={"d","r","u","l"};
string path2[4]={"u","l","d","r"};
int dp[10]={1,1,2,6,24,120,720,5040,40320,362880};
int final[9]={1,2,3,4,5,6,7,8,0};
int hashtable[362885];
class state
{
public:
    int a[9],zero;
    string path;
    state(){};
    state(int num[9])
    {
        for(int i=0;i<9;++i)
            a[i]=num[i];
    }
    void swapn(int c)
    {
        swap(a[zero],a[c]);
    }
};
state x,y;
state sl[362885];
int getHash(int code[9])
{
    int sum=0;
    bool flag[9];
    int k;
    memset(flag,false,sizeof(flag));
    for(int i=0;i<9;++i)
    {
        k=0;
        for(int j=code[i]+1;j<9;++j)
        {
            if(!flag[j])
                ++k;
        }
        sum+=k*dp[8-i];
        flag[code[i]]=true;
    }
    return 362879-sum;
}
bool check(state a,state b)
{
    bool flag=true;
    for(int i=0;i<9;++i)
    {
        if(a.a[i]!=b.a[i])
        {
            flag=false;
            break;
        }
    }
    return flag;
}
bool bfs(state ori,state fin)
{
    queue<state>open,open2;
    open.push(ori);
    open2.push(fin);
    int hcode,fcode;
    state tmp,tmp2,t1,t2;
    while(1)
    {
        if(!open.empty())
        {
            t1=open.front();
            open.pop();
            for(int i=0;i<4;++i)
            {
                int row=t1.zero/3;
                int col=t1.zero%3;
                int arow=row+next[i][1];
                int acol=col+next[i][0];
                if(arow<3&&arow>=0&&acol<3&&acol>=0)
                {
                    int sw=arow*3+acol;
                    tmp=t1;
                    tmp.swapn(sw);
                    tmp.zero=sw;
                    tmp.path+=path[i];
                    hcode=getHash(tmp.a);
                    if(hashtable[hcode]==1)
                        continue;
                    if(hashtable[hcode]==2)
                    {
                        x=tmp;
                        y=sl[hcode];
                        return true;
                    }
                    hashtable[hcode]=1;
                    sl[hcode]=tmp;
                    open.push(tmp);
                }
            }
        }
        if(!open2.empty())
        {
            t2=open2.front();
            open2.pop();
            for(int i=0;i<4;++i)
            {
                int row=t2.zero/3;
                int col=t2.zero%3;
                int arow=row+next[i][1];
                int acol=col+next[i][0];
                if(arow<3&&arow>=0&&acol<3&&acol>=0)
                {
                    int sw=arow*3+acol;
                    tmp2=t2;
                    tmp2.swapn(sw);
                    tmp2.zero=sw;
                    tmp2.path+=path2[i];
                    fcode=getHash(tmp2.a);
                    if(hashtable[fcode]==2)
                        continue;
                    if(hashtable[fcode]==1)
                    {
                        y=tmp2;
                        x=sl[fcode];
                        return true;
                    }
                    hashtable[fcode]=2;
                    sl[fcode]=tmp2;
                    open2.push(tmp2);
                }
            }
        }
    }
    return false;
}
bool isSolveable (int statue[9])
{
    int num=0;
    for (int i=1;i<=8;++i)
        {
            if(statue[i]==0)
            continue;
        for(int j=0;j<i;++j)
            {
                    if(statue[j]==0)
                continue;
            if(statue[i]>statue[j])
                ++num;
            }
        }
        if (num%2==1) return false;
        return true;
}

int main()
{
    freopen("e:\\zoj\\zoj_1217.txt","r",stdin);
    while(1)
    {
        memset(hashtable,0,sizeof(hashtable));
        int flag=0;
        int num[9];
        int zero;
        char c;
        for(int i=0;i<9;++i)
        {
            if(scanf(" %c",&c)==EOF)
                return 0;
            if(c=='x')
            {
                zero=flag;
                num[flag++]=0;
            }
            if(c<='9'&&c>='1')
                num[flag++]=c-48;
            if(flag>=9)
                break;
        }
        state ori(num);
        ori.zero=zero;
        state fin(final);
        fin.zero=8;
        int ocode=getHash(num);
        int fcode=getHash(final);
        hashtable[ocode]=1;
        hashtable[fcode]=2;
        sl[ocode]=ori;
        sl[fcode]=fin;
        if(!isSolveable(num))
            printf("unsolvable\n");
        else
        {
            if(check(ori,fin))
                puts("");
            bool f=bfs(ori,fin);
            int l=x.path.length();
            for(int i=0;i<l;++i)
                printf("%c",x.path[i]);
            l=y.path.length();
            for(int i=l-1;i>=0;--i)
                printf("%c",y.path[i]);
            puts("");
        }
    }
}