题解 UVA10181

· · 题解

题意：

经典的 15 数码华容道问题，给定一些开始方案，求最少步数拼到起点的方法，步数不超过 45。

思路：

1. 无解判定

当然，由于存在无解情况可能导致无用的搜索，我们首先需要判定当前情况是否无解。按照 zjjws 题解的方法，判断逆序对。

具体地，可以发现对于任何一次数码的左右移动，逆序对数量不会有改变。而对于任何一次上下的移动，逆序对数量一定增加奇数个。（可以参考 zjjws 的题解或者手玩以下，这里不过多赘述）

而每次上下移动，空格子一定也会上下移动。而空格子最终会移到最底部。因此，空格子到最底部的竖直距离和总体的逆序对数之和的奇偶性决定了整个方案是否可行。

即：空格子到最底部一横行的距离与除空格之外所有数字的逆序对数之和为偶数，这个问题才有解。

2. 记录路径搜索

排除无解情况之后就可以开始搜索了。首先，用哈希（unordered_map）记录状态。接着采用 A* 进行启发式搜索。

简单介绍一下 A 算法。它在代码实现上有点类似于广搜（最短路的 Dijkstra 本质上也和 A 非常类似）。

简单来讲，传统 BFS 使用朴素的队列对每一步进行储存，而 A 算法则使用优先队列。在一般的 A 算法中，优先队列按照每个状态的实际代价和期望代价综合考虑排序。

这样钦定一个合理的优先搜索方向，可以在许多情况下减少不必要的状态数，使得搜索效率大大提高。因此这个算法也广泛运用于游戏 NPC 寻路等场景中。当然在本题的情境中也非常适用。

在本题中，定义一个期望函数 H 来估算到目标状态的距离。按照基本的常识，当所有非空数字到目标状态的j距离越近，可能需要的步数大概也就越少。因此，函数 H_i 定义为 i 状态下，所有非空数字到目标状态的曼哈顿距离之和。

所以，综合考虑每次搜索的实际代价，我们使用 A* 算法，以实际代价和期望代价之和作为关键字，在优先队列进行顺序搜索即可。

需要注意的是，A* 算法并不是严格优于 BFS 等其它搜索算法的。当出现构造特殊数据的情况时，估价函数并不能充分发挥作用，它优先队列中自带的 \log 反而会让整体复杂度提升。

本题需要输出每一步操作，而步数不多。使用 vector 储存，每次转移即可。

时间复杂度：O(S\Epsilon \log \Epsilon)，其中 \Epsilon 表示期望状态数，S 表示期望步数。

程序如下：

#include<cstdio>
#include<unordered_map>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int N=20,P=137;
const int dx[]={0,1,-1,0,0};
const int dy[]={0,0,0,1,-1};
const char ch[]={0,'D','U','R','L'};
int T,cntstep;
struct NODE{
    int a[N],zx,zy,zplace;
    unsigned long long hs;
    void gethash(){
        hs=0;
        for(int i=1;i<=16;i++){//哈希状态（ull自然溢出）
            hs=hs*P+a[i];
            if(a[i]==0){
                zx=(i-1)/4+1;
                zy=i%4==0?4:i%4;
                zplace=i;
            }
        }
    }
}st,ed;
struct QUE{
    NODE x;
    vector<char>g;
    int step,val;
};
bool operator>(QUE x,QUE y){return x.step+x.val>y.step+y.val;}
int abs(int x){return x<0?-x:x;}
unordered_map<unsigned long long,bool>mp;
bool chk(){//判无解，答案是奇数一定无解
    int cntst=0;
    for(int i=1;i<=16;i++){
        if(st.a[i]==0)cntst+=3-(i-1)/4;
        else{
            for(int j=i+1;j<=16;j++)
                if(st.a[j]&&st.a[i]>st.a[j])
                    cntst++;
        }
    }
    return !(cntst&1);
}
int getdis(NODE x,NODE y){//估价函数，算曼哈顿距离之和
    int ret=0,plc[N];
    for(int i=1;i<=16;i++)plc[y.a[i]]=i;
    for(int i=1;i<=16;i++)
        if(x.a[i]!=0){
            int j=plc[x.a[i]];
            int xx,xy,yx,yy;
            xx=(i-1)/4+1;
            xy=i%4==0?4:i%4;
            yx=(j-1)/4+1;
            yy=j%4==0?4:j%4;
            ret+=abs(xx-yx)+abs(xy-yy);
        }
    return ret;
}
vector<char>bfs(){
    priority_queue<QUE,vector<QUE>,greater<QUE> >q;
    vector<char>gg;
    q.push({st,gg,0,getdis(st,ed)});
    while(!q.empty()){//和BFS类似的套路
        NODE u=q.top().x;
        int step=q.top().step,ddis=q.top().val;
        vector<char>g=q.top().g;//记录每一步操作
        q.pop();
        for(int i=1;i<=4;i++){
            int x_new=u.zx+dx[i],y_new=u.zy+dy[i];
            int i_new=(x_new-1)*4+y_new;
            NODE curx=u;
            if(x_new>=1&&x_new<=4&&y_new>=1&&y_new<=4){
                swap(curx.a[i_new],curx.a[u.zplace]);
                curx.gethash();
                g.push_back(ch[i]);
                int curdis=getdis(curx,ed);
                if(mp.find(curx.hs)!=mp.end());
                else if(curx.hs==ed.hs)return g;
                else{
                    q.push({curx,g,step+1,curdis});
                    mp[curx.hs]=true;
                }
                g.pop_back();
            }
        }
        cntstep++;
    }
    return gg;
}
int main(){
    scanf("%d",&T);
    for(int i=1;i<=15;i++)ed.a[i]=i;
    ed.a[16]=0;
    ed.gethash();
    while(T--){
        mp.clear();
        mp.reserve(10000000);
        for(int i=1;i<=16;i++)scanf("%d",&st.a[i]);
        st.gethash();
        if(!chk())printf("This puzzle is not solvable.\n"); 
        else{
            vector<char>tmp=bfs();
            for(auto i:tmp)printf("%c",i);
            puts("");
        }
    }
    return 0;
}

THE END