题解 P1379 【八数码难题】

niiick · 2018-08-01 14:19:23 · 题解

怎么所有dalao写的都是双向bfs， 蒟蒻写了一发IDA*， 本以为会T，结果其实跑得还挺快？

迭代加深的A*算法

所谓迭代加深就是每次限制搜索深度， 这样可以在整个搜索树深度很大而答案深度又很小的情况下大大提高效率

使k从1开始不断加深枚举， 作为最大步数进行迭代加深搜索判断，而对于不用移动的情况可以一开始直接特判

在这里我们的*A估价函数**设置为

当前状态还有多少个位置与目标状态不对应

若当前步数+估价函数值>枚举的最大步数 则直接返回

当然这只是基本思路，搜索还可以有很大优化

我们在搜索中再加入最优性剪枝， 显然当前枚举下一个状态时如果回到上一个状态肯定不是最优， 所以我们在枚举下一状态时加入对这种情况的判断

将状态数组对称排列会很方便进行这一操作

int nxtx[]={0,1,-1,0};
int nxty[]={1,0,0,-1};

//niiick
#include<iostream>
#include<string>
#include<map>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long lt;

int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

char ss[15];
int ans[4][4]=
{{0,0,0,0},
 {0,1,2,3},
 {0,8,0,4},
 {0,7,6,5}};
int a[5][5],k,judge;
int nxtx[]={0,1,-1,0};
int nxty[]={1,0,0,-1};

int check()
{
    for(int i=1;i<=3;++i)
    for(int j=1;j<=3;++j)
    if(ans[i][j]!=a[i][j])return 0;
    return 1;
}

int test(int step)
{
    int cnt=0;
    for(int i=1;i<=3;++i)
    for(int j=1;j<=3;++j)
    if(ans[i][j]!=a[i][j]){ if(++cnt+step>k) return 0;}
    return 1;
}

void A_star(int step,int x,int y,int pre)
{
    if(step==k){ if(check())judge=1; return;}达到当前限制的最大深度
    if(judge) return;
    for(int i=0;i<4;++i)
    {
        int nx=x+nxtx[i],ny=y+nxty[i];
        if(nx<1||nx>3||ny<1||ny>3||pre+i==3) continue;//加入了上述最优性剪枝
        swap(a[x][y],a[nx][ny]);
        if(test(step)&&!judge) A_star(step+1,nx,ny,i);//A*估价合法再向下搜索
        swap(a[x][y],a[nx][ny]);
    }
}

int main()
{
    int x,y;
    scanf("%s",&ss);
    for(int i=0;i<9;++i)
    {
        a[i/3+1][i%3+1]=ss[i]-'0';
        if(ss[i]-'0'==0)x=i/3+1,y=i%3+1;
    }
    if(check()){printf("0");return 0;}//特判不用移动
    while(++k)//枚举最大深度
    {
        A_star(0,x,y,-1);
        if(judge){printf("%d",k);break;}
    }
    return 0;
}