学习笔记--八数码问题

题目链接

https://www.luogu.org/problemnew/show/P1379

分析

经典的八数码问题,有双向BFS和\(IDA*\)的方法，这里使用的是\(A*\)启发式搜索.

简要介绍一下\(A*\),就是对于搜索的每一个状态设计一个评估函数\(f(state)\),表示当前状态\(state\)到目标状态所需代价的估计值;还有一个\(g(state)\),表示当前状态\(state\)到目标状态实际需要的最小代价,\(A*\)中必须保证\(f(state)<=g(state)\)才能确保在目标状态第一次被取出时就是最优解（实际一点,比如最少的步数）并且在搜索中每个状态只需扩展一次，设计的估价函数\(f(stste)\)越接近\(g(state)\)效率越高.

我们这里用曼哈顿距离设计估价函数，也就是\(f(state)=\)$\sum^9_{i=1} (|posx_i-goalx_i|+|posy_i-goaly_i|) $

\(posx_i\)表示\(i\)这个数字在九宫格中的横坐标,\(posy_i\)也就类似的。注意,我们不能统计\(0\)，否则这样\(f(state)\)可能会大于实际代价

为了确保每个状态都被拓展一次，我们可以采用康托展开(将\(1-n\)的全排列映射成\(1-n!\)中的一个数)或是哈希表(unordered_map/pb_ds::gp_hash_table/map)

同时还要注意,八数码问题有时候是没有解的,我们将九宫格除空格之外的数按从左到右,再从上到下的顺序排成一列数来表示每一个状态，如果初始状态和目标状态的逆序对个数奇偶性不同的话是无解的,可以提前判断一下是否有解来提高效率

题目:

P1379 八数码难题

题目链接：https://www.luogu.org/problemnew/show/P1379

非常简单,甚至不用判断无解

代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <utility>
#include <cmath>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define ll long long 
#define ri register int 
#define ull unsigned long long 
using std::pair;
using std::swap;
using std::abs;
using std::priority_queue;
using namespace __gnu_pbds;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c==‘-‘;
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;return ;
}
const int maxn=5;
const int inf=0x7fffffff;
const int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
int sta[maxn][maxn];
ll st,goal;
gp_hash_table <ll,bool>g;
pair<int,int>pos[10];
struct Sta{
    ll a;
    int s,f;
    Sta(){;}
    Sta(ll _a,int _s,int _f){a=_a,s=_s,f=_f;}
    bool operator <(const Sta &b)const{
        return f>b.f;
    }
};
int bx,by;//0位置 
inline int get_f(){//估价函数
    int ans=0;
    for(ri i=1;i<=3;i++){
        for(ri j=1;j<=3;j++){
            if(state[i][j])ans+=abs(i-pos[sta[i][j]].first)+abs(j-pos[sta[i][j]].second);
        }
    }
    return ans;
}
inline ll turn_num(){//转为数字
    ll ans=0;
    for(ri i=1;i<=3;i++){
        for(ri j=1;j<=3;j++){
            ans=ans*10+sta[i][j];
        }
    }
    return ans;
}
inline void turn_sta(ll num){//转为九宫格
    for(ri i=3;i>=1;i--){
        for(ri j=3;j>=1;j--){
            sta[i][j]=num%10;
            num=num/10;
            if(!sta[i][j])bx=i,by=j;
        }
    }
    return ;
}
inline void astar(){
    ll now,nxt;
    int x,y,z;
    Sta tmp;
    priority_queue<Sta>q;
    while(q.size())q.pop();
    turn_sta(st);
    q.push(Sta(st,0,get_f()));  
    g[st]=1;
    while(q.size()){
        tmp=q.top();q.pop();
        now=tmp.a,z=tmp.s;
        if(now==goal){
            printf("%d\n",z);
            return ;
        }
        turn_sta(now);
        for(ri i=0;i<4;i++){
            x=bx+dx[i],y=by+dy[i];
            if(x>=1&&x<=3&&y>=1&&y<=3){
                swap(sta[bx][by],sta[x][y]);
                nxt=turn_num();
                if(g[nxt]){
                    swap(sta[bx][by],sta[x][y]);
                    continue;
                }
                g[nxt]=1;
                q.push(Sta(nxt,z+1,z+1+get_f()));
                swap(sta[bx][by],sta[x][y]);
            }
        }
    }
    puts("unsolvable");
    return ;
}
int main(){
    /*230187546*/
    int x,y,z;
    pos[0].first=2,pos[0].second=2;
    pos[1].first=1,pos[1].second=1;
    pos[2].first=1,pos[2].second=2;
    pos[3].first=1,pos[3].second=3;
    pos[4].first=2,pos[4].second=3;
    pos[5].first=3,pos[5].second=3;
    pos[6].first=3,pos[6].second=2;
    pos[7].first=3,pos[7].second=1;
    pos[8].first=2,pos[8].second=1;
    read(st);
    goal=123804765;
    astar();
    return 0;
}

POJ1077 Eight

题目链接:http://poj.org/problem?id=1077

要打印方案,我用了一个\(naive\)的方法,就是记录每个状态是从哪个状态转移过来的(\(A*\)保证扩展到每一个状态时一定是花费最少的步数)，同时再用一个哈希表记录它是进行哪个操作转移过来的，最后递归打印即可

当然还有其他方法这里不赘述.由于POJ好像不资瓷pbds和unordered_map,只好用map

代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <utility>
#include <cmath>
#include <map> 
#define ll long long 
#define ri register int 
#define ull unsigned long long 
using namespace std;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c==‘-‘;
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;return ;
}
const int maxn=5;
const int inf=0x7fffffff;
const int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
const char ch[4]={‘u‘,‘l‘,‘r‘,‘d‘};
int sta[maxn][maxn];
ll st,goal;
map <ll,ll> pre;
map <ll,int> dir;
pair<int,int>pos[10];
struct Sta{
    ll a;
    int s,f;
    Sta(){;}
    Sta(ll _a,int _s,int _f){a=_a,s=_s,f=_f;}
    bool operator <(const Sta &b)const{
        return f>b.f;
    }
};
int bx,by;//0位置 
inline int get_f(){
    int ans=0;
    for(ri i=1;i<=3;i++){
        for(ri j=1;j<=3;j++){
            if(sta[i][j]==0)continue;
            ans+=abs(i-pos[sta[i][j]].first)+abs(j-pos[sta[i][j]].second);
        }
    }
    return ans;
}
inline ll turn_num(){
    ll ans=0;
    for(ri i=1;i<=3;i++){
        for(ri j=1;j<=3;j++){
            ans=ans*10+sta[i][j];
        }
    }
    return ans;
}
inline void turn_sta(ll num){
    for(ri i=3;i>=1;i--){
        for(ri j=3;j>=1;j--){
            sta[i][j]=num%10;
            num=num/10;
            if(!sta[i][j])bx=i,by=j;
        }
    }
    return ;
}
void print(ll x){
    /*234150768*/
    if(x==st)return ;   
    print(pre[x]);
    putchar(ch[dir[x]]);
    return ;
}
inline void astar(){
    ll now,nxt;
    int x,y,z;
    Sta tmp;
    priority_queue<Sta>q;
    while(q.size())q.pop();//puts("wtf");
    turn_sta(st);
    q.push(Sta(st,0,get_f()));  
    while(q.size()){
        tmp=q.top();q.pop();
        now=tmp.a,z=tmp.s;
        if(now==goal){
            //printf("%d\n",z);
            //printf("%lld***\n***",pre[st]);
            print(goal);
            return ;
        }
        //printf("*%lld\n",now);
        turn_sta(now);
        for(ri i=0;i<4;i++){
            x=bx+dx[i],y=by+dy[i];
            if(x>=1&&x<=3&&y>=1&&y<=3){
                swap(sta[bx][by],sta[x][y]);
                nxt=turn_num();
                if(!pre[nxt]){
                    pre[nxt]=now;
                    dir[nxt]=i;
                    q.push(Sta(nxt,z+1,z+1+get_f()));
                }
                swap(sta[bx][by],sta[x][y]);
            }
        }
    }
    puts("unsolvable");
    return ;
}
int main(){
    int num[10];
    char x[2];
    pos[0].first=3,pos[0].second=3;
    pos[1].first=1,pos[1].second=1;
    pos[2].first=1,pos[2].second=2;
    pos[3].first=1,pos[3].second=3;
    pos[4].first=2,pos[4].second=1;
    pos[5].first=2,pos[5].second=2;
    pos[6].first=2,pos[6].second=3;
    pos[7].first=3,pos[7].second=1;
    pos[8].first=3,pos[8].second=2;
    //read(st);
    st=0;
    for(ri i=1;i<=9;i++){
        scanf("%s",x);
        if(x[0]==‘x‘)st=st*10,num[i]=inf;
        else st=st*10+x[0]-‘0‘,num[i]=x[0]-‘0‘;
    }
    //printf("%lld\n",st);
    int cnt=0;
    for(ri i=1;i<=9;i++){
        if(num[i]==inf)continue;
        for(ri j=i+1;j<=9;j++){
            if(num[j]<num[i]){cnt++;}
        }
    }
    //printf("%d\n",cnt);
    if(cnt%2==1){
        puts("unsolvable");
    }
    else{
        pre[st]=19260817;
        goal=123456780;
        astar();
    }
    return 0;
}

UVA652 Eight

题目链接: https://cn.vjudge.net/problem/UVA-652

这道题由于多组数据发现各个\(A*\)好像不太行,于是就先一遍BFS扩展出所有状态同时记录路径,这一次没用哈希表用了康拓展开，然而不知道为何WA掉了。。。

代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <utility>
#include <iostream>
#define ll long long 
#define ri register int 
#define ull unsigned long long 
using namespace std;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c==‘-‘;
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;return ;
}
const int maxn=5;
const int inf=0x7fffffff;
const int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
const char ch[4]={‘u‘,‘l‘,‘r‘,‘d‘};
const int fac[10]={1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int sta[maxn][maxn];
ll st,goal;
struct Sta{
    ll a;int v;
    Sta(){;}
    Sta(ll _a,int _v){a=_a,v=_v;}
};
int bx,by;//0位置 
int num[10],len[500005];
char path[500005][75];
inline ll turn_num(){
    ll ans=0;
    for(ri i=1;i<=3;i++){
        for(ri j=1;j<=3;j++){
            ans=ans*10+sta[i][j];
            num[(i-1)*3+j]=sta[i][j];
        }
    }
    return ans;
}
inline int cal_cantor(){
    int sml=0,x=0;
    for(ri i=1;i<=9;i++){
        sml=0;
        for(ri j=i+1;j<=9;j++){
            if(num[j]<num[i])++sml;
        }
        x+=fac[9-i]*sml;
    }
    return x+1;
} 
inline void turn_sta(ll p){
    for(ri i=3;i>=1;i--){
        for(ri j=3;j>=1;j--){
            sta[i][j]=p%10;
            p=p/10;
            if(sta[i][j]==9)bx=i,by=j;
        }
    }
    return ;
}
bool vis[500005];
inline void bfs(){
    ll now,nxt;
    int x,y,z,pre_val,val;
    Sta tmp;
    queue<Sta>q;
    while(q.size())q.pop();//puts("wtf");   
    turn_sta(goal);
    z=turn_num();
    val=cal_cantor();
    vis[val]=1;
    q.push(Sta(goal,val));  
    while(q.size()){
        tmp=q.front();q.pop();
        now=tmp.a,pre_val=tmp.v;
        turn_sta(now);
        for(ri k=0;k<4;k++){
            x=bx+dx[k],y=by+dy[k];
            if(x>=1&&x<=3&&y>=1&&y<=3){
                swap(sta[bx][by],sta[x][y]);
                nxt=turn_num();
                val=cal_cantor();               
                //printf("%d %d %lld %d %d\n",x,y,nxt,val,pre_val);
                if(!vis[val]){
                    vis[val]=1;
                    for(ri i=1;i<=len[pre_val];i++){
                        path[val][i]=path[pre_val][i];
                    }
                    len[val]=len[pre_val];
                    path[val][++len[val]]=ch[k];
                    q.push(Sta(nxt,val));
                }
                swap(sta[bx][by],sta[x][y]);
            }
        }
    }
    return ;
}
int main(){
    /*234150768*/
    /*123456780*/
    /*
    2   
    2 3 4 1 5 x 7 6 8   
    2 3 4 1 5 x 7 6 8
    */
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int t,val;
    char kkk;
    read(t);
    goal=123456789;
    memset(vis,0,sizeof(vis));
    bfs();
    while(t--){
        st=0;
        for(ri i=1;i<=9;i++){
            cin>>kkk;//scanf("%s",x);
            if(kkk==‘x‘)st=st*10,num[i]=9;
            else st=st*10+kkk-‘0‘,num[i]=kkk-‘0‘;
        }
        val=cal_cantor();
        //printf("%d %d\n",val,len[val]);
        if(!vis[val]){
            puts("unsolvable");
        }
        else{
            for(ri i=len[val];i>=1;i--)putchar(path[val][i]);
            puts("");
        }
        if(t)puts("");
    }
    return 0;
}

学习笔记--八数码问题

原文：https://www.cnblogs.com/Rye-Catcher/p/9539351.html