HDU1043&3567 搜索（八数码，康托展开+双向bfs+A*）

八数码问题，类似华容道，要求给出复位的操作序列。

康托展开用于解决排列相关问题，实现了一个排列到整数双射。因此我们可以用一个整数表示当前排列，便于进行搜索。以下是康托展开和逆展开的模板。

int cantor(int* st){
    int x=0;
    for(int i=0;i<9;i++){
        int smaller=0;
        for(int j=i+1;j<9;j++){
            if(st[j]<st[i])
                smaller++;
        }
        x+=fac[8-i]*smaller;
    }
    return x;
}

void decantor(int x){
    vector<int> v;
    for(int i=1;i<=9;i++)
        v.push_back(i);
    for(int i=8;i>=0;i--){
        int r=x%fac[i];
        int t=x/fac[i];
        x=r;
        sort(v.begin(),v.end());
        tmp[8-i]=v[t];
        v.erase(v.begin()+t);
    }
}

题目打算采用bfs，从0状态出发寻找初始状态，途中每个状态都存储当前cmd序列和9的位置。但是这份代码最终mle了。。。

之后得知，路径最长不会超过三十多，则将路径储存在一个全局数组中path[9!][50]，空间缩小将近一半，但出现超时的问题，考虑剪枝：在移动x的过程中逆序数的变化为偶数，而由于目标序列逆序数为0，所以初始逆序数如果是奇数，则可直接排除。

依然超时，推测是因为数据组数多，bfs要打表了。之前一直都是当作直跑一次写的代码。打算干脆放下去学A*。

A*搜索的原理很符合逻辑，大概地判断当前情况的优劣，并以此为排序权重影响搜索的顺序。同时将x节点所代表的值由9改为0，方便计算逆序数。

AC代码：

#include<bits/stdc++.h>
using namespace std;

static const int fac[10]={1,1,2,6,24,120,720,5040,40320,362880};
int sp[9];
int target[9]={1,2,3,4,5,6,7,8,0};
bool vis[362880];
int step[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
char cmd[5]="drul";

int spos;
char path[362880];
int bck[362880];
void disp(int n){
    if(bck[n]){
        disp(bck[n]);
        printf("%c",path[n]);
    }
}

struct state{
    int dat;
    int pos;
    int h,g,f;
    state(){}
    state(int _dat,int _pos,int _h,int _g):dat(_dat),pos(_pos),h(_h),g(_g){
        f=g+h;
    }
    bool operator<(const state& st)const{
        if(f!=st.f)
            return f>st.f;
        else
            return g>st.g;
    }
};

int geth(int s[]){
    int res=0;
    for(int i=0;i<9;i++){
        if(s[i]==0)
            continue;
        int x=i/3;  //当前位置
        int y=i%3;
        int tx=(s[i]-1)/3;     //这个位置上的值，减一即为目标位置
        int ty=(s[i]-1)%3;
        res+=abs(x-tx)+abs(y-ty);
    }
    return res;

}

int cantor(int* st){
    int x=0;
    for(int i=0;i<9;i++){
        int smaller=0;
        for(int j=i+1;j<9;j++){
            if(st[j]<st[i])
                smaller++;
        }
        x+=fac[8-i]*smaller;
    }
    return x;
}

void decantor(int x,int* a){
    vector<int> v;
    for(int i=0;i<9;i++)
        v.push_back(i);
    for(int i=8;i>=0;i--){
        int r=x%fac[i];
        int t=x/fac[i];
        x=r;
        sort(v.begin(),v.end());
        a[8-i]=v[t];
        v.erase(v.begin()+t);
    }
}

int cal(int* s){
    //计算逆序数 reverse order number
    int res=0;
    for(int i=1;i<9;i++){
        if(!s[i])
            continue;
        int tmp=0;
        for(int j=0;j<i;j++)
            if(s[j]>s[i])
                tmp+=1;
        res+=tmp;
    }
    return res;
}
int s[9]={0};
void bfs(){
    memset(vis,0,sizeof(vis));
    memset(path,0,sizeof(path));
    memset(bck,0,sizeof(bck));
    int dest=cantor(target);

    memcpy(s,sp,9*sizeof(int));

    int ron=cal(sp)-cal(target);
    if(ron&1){
        puts("unsolvable");
        return;
    }

    priority_queue<state> q;
    state st;
    st.dat=cantor(s);
    st.pos=spos;
    st.g=0;
    st.f=0;
    st.h=0;
    q.push(st);
    
    vis[st.dat]=1;

    while(!q.empty()){
        state now=q.top();
        if(now.dat==dest){
            if(now.g==0)
                puts("lr");
            else{
                disp(dest);
                puts("");
            }
            return;
        }
        q.pop();

        int x=now.pos/3;
        int y=now.pos%3;
        for(int i=0;i<4;++i){
            int nx=x+step[i][0];
            int ny=y+step[i][1];
            if(nx<0||nx>2||ny<0||ny>2)
                continue;

            decantor(now.dat,s);

            swap(s[x*3+y],s[nx*3+ny]);
            int ndat=cantor(s);


            if(!vis[ndat]){
                int h=geth(s);
                vis[ndat]=1;
                bck[ndat]=now.dat;
                path[ndat]=cmd[i];

                q.push(state(ndat,nx*3+ny,h,now.g+1));
            }
            swap(s[x*3+y],s[nx*3+ny]);
        }
    }
    cout<<"unsolvable"<<endl;
}

int main(){
    char c;
    while(cin>>c){
        if(c=='x'){
                spos=0;
                sp[0]=0;
        }
        else
            sp[0]=c-'0';
        for(int i=1;i<9;i++){
            cin>>c;
            if(c=='x')
                spos=i,sp[i]=0;
            else
                sp[i]=c-'0';
        }
        bfs();
    }
    return 0;
}
/*
1 2 3 4 5 6 7 8 x

2 1 3 4 5 6 7 8 x

1 3 x 4 2 6 7 5 8

1 2 3 4 5 6 7 x 8
*/

接下来是HDU3567，这一题比前面那道区别在于，给出T个测试，每次任意给起点终点，要求输出最短字典序最小的操作序列。

考虑双向bfs，前半段的字典序可以通过控制每层遍历时的移动方向决定，后半段则只能通过枚举所有最短的序列。由于bfs的特点，每次循环的层数代表了序列的长度，这样一层一层找下去肯定首先找到最短的，再在其中寻找字典序最小。

建立两个队列，每次先对q1进行遍历，寻找有没有状态已从后半段抵达；再对q2遍历，每次遇到后半段已到达的则说明，这是这次遍历的成果，尝试进行字典序更新。

HDU1043&3567 搜索（八数码，康托展开+双向bfs+A*）

全站热榜