八数码难题

_Sein · 2018-12-26 14:00:58 · 题解

A* 做法

• 什么为A*

  如果给定一个“目标状态”（如八数码中的目标状态），需要求出从出台到目标状态的最小代价。那么BFS甚至优先队列BFS都不够完善，多余的状态多过，导致程序过慢，TLE。一个状态的当前代价最小，但不意味着以后这个状态都保持最优，其他状态可能会成为最优解。这时候我们就可以用到估计函数来求求解了，保持现在最优以及未来估计最优。这就是所谓的A*算法。

• 基本准则

  因为A*实际上是一种启发式算法，所以没有什么固定的套路。

  但有基本准则： 设当前状态state到目标状态所需代价的估计值为f(state)。

  设在未来搜索中，实际求出的从当前状态state到目标状态的最小代价为g(state).

  对于任意的state，应有f(state)≤g(state)。

  证明请参照lyd的算法进阶指南。

• 思路

  就是当前移动次数dis+当前状态下每一个点的位置到目标状态的位置的曼哈顿距离,每次取出堆顶(以堆顶的估计函数+dis为关键项)，就可以求出最短次数了。

• 代码比较冗杂（请轻喷)

  #include<cstdio>
  #include<cstring>
  #include<algorithm>
  #include<queue>
  using namespace std;
  const int dx[4]={0,1,-1,0};
  const int dy[4]={1,0,0,-1};
  int d[9];
  void pre()
  {
  d[0]=1;for(int i=1;i<=8;i++)d[i]=d[i-1]*i;
  }
  struct node
  {
  int dis,f,k,x,y,ans;
  int a[5][5];
  node(){dis=k=f=0;memset(a,0,sizeof(a));x=y=0;}
  bool operator <(const node &a)const{return f==a.f?dis>a.dis:f>a.f;}//重构小根堆 
  inline void kt()//康托展开 
  { 
      k=0;
      int b[20],len=0;
      for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)b[++len]=a[i][j]+1;//相当于将一个3*3的图排成一行； 
      bool bo[20];memset(bo,false,sizeof(bo));//初始化 
      //统计当前这个是第几个康托排列 
      for(int i=1;i<=9;i++)
      {
          for(int j=1;j<b[i];j++)
          {
              if(bo[j]==false)
              {
                  k+=d[9-i];
              }
          }
          bo[b[i]]=true;
      } 
  }
  inline void find_f(const node &ed)//A*的估计函数f 
  {
      int x1=1,y1=1;bool ap[10];memset(ap,false,sizeof(ap));
      f=dis;
      while(x1<=3)
      {
          if(y1==4)x1++,y1=1;
          bool bk=true;
          for(int i=1;i<=3;i++)
          {
              for(int j=1;j<=3;j++)
              {
                  if(ap[ed.a[i][j]])continue;
                  if(ed.a[i][j]==a[x1][y1])
                  {
                      f+=abs(x1-i)+abs(y1-j);ap[a[x1][y1]]=true;
                      y1++;
                      bk=false;
                      break;
                  }
              }
              if(bk==false)break;
          }
      }
  }
  };
  node st,ed;
  priority_queue<node>q;
  bool v[510000];
  int main()
  {
  pre();
  memset(v,false,sizeof(v));
  for(int i=1;i<=3;i++)
  {
      for(int j=1;j<=3;j++)
      {
          char c=getchar();
          st.a[i][j]=c-'0';if(st.a[i][j]==0){st.x=i,st.y=j;}
      }
  }
  ed.a[1][1]=1;ed.a[1][2]=2;ed.a[1][3]=3;
  ed.a[2][1]=8;ed.a[2][2]=0;ed.a[2][3]=4;
  ed.a[3][1]=7;ed.a[3][2]=6;ed.a[3][3]=5;
  ed.x=2,ed.y=2;
  st.kt();ed.kt();
  if(st.k==ed.k){printf("0\n");return 0;}
  v[st.k]=true;st.dis=0;st.find_f(ed);
  q.push(st);
  while(!q.empty())
  {
      node t=q.top();
      q.pop(); 
      for(int i=0;i<4;i++)
      {
          node now=t;
          int x=now.x+dx[i],y=now.y+dy[i];
          if(x<1||x>3||y<1||y>3)continue;
          int tw=now.a[now.x][now.y];now.a[now.x][now.y]=now.a[x][y];now.a[x][y]=tw;
          now.x=x,now.y=y;
          now.dis++;
          now.kt();
          if(v[now.k])continue;
          now.find_f(ed);
          v[now.k]=true;
          if(now.k==ed.k){printf("%d\n",now.dis);return 0;}
          q.push(now);
      }
  }
  return 0;
  }

  AC:189ms