M_sea

洛谷1379 八数码难题
Luogu算法IDA*。我们先枚举最大深度(也就是最多能走的步数),然后依次Dfs即可。在Dfs时,需要设计一个估...
扫描右侧二维码阅读全文
06
2018/06

洛谷1379 八数码难题

Luogu

算法

IDA*。

我们先枚举最大深度(也就是最多能走的步数),然后依次Dfs即可。

在Dfs时,需要设计一个估价函数$h()$。它的设计过程如下:

  • 首先,用dis[i][j]表示从第i个到第j格的最少移动次数。这个就是曼哈顿距离。
  • 其次,用p[i]表示i这个数的目前位置,q[i]表示第j个数的目前位置。
  • 最后,h即为当前局面的偏移量之和。

最后回答一下判重的问题。

由于改成了深度优先的方式,与A*比起来,IDA*更实用:1.不需要判重,不需要排序;2.空间需求减少。 ——百度百科

所以判重是完全不必要的。 这样顺便解决了本题最麻烦的问题。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;
const int dx[5]={1,0,-1,0},dy[5]={0,1,0,-1};
const int q[9]={5,1,2,3,6,9,8,7,4}; //目标状态 
int p[9]; //当前状态 
int dis[10][10];
int old[4][4],now[4][4];
int max_deep;
bool f=0;
inline bool check() { for (re int i=1;i<9;i++) if (p[i]!=q[i]) return 0; return 1; }
inline int h() { int rt=0; for (re int i=1;i<9;i++) rt+=dis[p[i]][q[i]]; return rt; } //估价函数
inline int getx(int n) { return (n-1)/3+1; }
inline int gety(int n) { return n%3==0?3:n%3; }
inline void build_dis() {
    for (re int i=1;i<=9;i++)
        for (re int j=i+1;j<=9;j++)
            dis[i][j]=dis[j][i]=getx(j)-getx(i)+abs(gety(i)-gety(j));
}
inline void Dfs(int x,int y,int dep) {
    if (dep+h()>max_deep) return;
    if (check()) { f=1; return; }
    for (re int i=0;i<4;i++) {
        int X=x+dx[i],Y=y+dy[i];
        if (X<1||Y<1||X>3||Y>3) continue;
        swap(p[now[x][y]],p[now[X][Y]]); swap(now[x][y],now[X][Y]);
        Dfs(X,Y,dep+1);
        swap(now[x][y],now[X][Y]); swap(p[now[x][y]],p[now[X][Y]]);
    }
}
int main() {
    build_dis();
    int sx,sy;
    for (re int i=1;i<=9;i++) {
        char c=getchar(); int x=getx(i),y=gety(i);
        old[x][y]=c-'0'; p[c-'0']=i;
        if (c=='0') sx=x,sy=y;
    }
    if (check()) { printf("0\n"); return 0; }
    for (max_deep=1; ;max_deep++) {
        memcpy(now,old,sizeof(now));
        Dfs(sx,sy,0);
        if (f) { printf("%d\n",max_deep); return 0; }
    }
    return 0;
}
最后修改:2018 年 11 月 30 日 09 : 54 PM

发表评论