【算法系列学习三】[kuangbin带你飞]专题二搜索进阶之 A-Eight 反向bfs打表和康拓展开

[kuangbin带你飞]专题二搜索进阶之 A-Eight

这是一道经典的八数码问题。首先，简单介绍一下八数码问题：

八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后，状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。

八数码问题有多种解法，BFS，双向BFS,A*等等，可以参考八数码的八境界，多种方法求解八数码问题.

求解这道题我用了两种方法：BFS+HASH（这种方法会TLE）;改进之后的反向BFS打表+HASH。

整体思路：用BFS搜索，搜索过程中要保存当前棋盘状态，3*3的棋盘有9！中状态，可以考虑用康拓展开来压缩空间（ 康托展开是一个全排列到一个自然数的映射，常用于构建哈希表时的空间压缩。康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。）目标状态（1 2 3 4 5 6 7 8 0）对应的自然数是46233。

方法一：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<string>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<cmath>
  7 #include<queue>
  8 //目标状态对应的自然数 
  9 #define END 46233
 10 using namespace std;
 11 //9! 
 12 const int maxn=362882;
 13 //初始状态对应的自然数 
 14 int flag_star;
 15 //判重 
 16 struct
 17 {
 18     int flag;//指向上一个状态 
 19     char dir;//从上一状体到这一状态的方向 
 20 }vis[maxn];
 21 //阶乘，以求康拓展示开 
 22 int fact[10];
 23 //记录当前棋盘状态和x的位置 
 24 struct node
 25 {
 26     int a[10];//当前棋盘的状态 
 27     int x;//x所在的位置 
 28 };
 29 
 30 //递归输出路径 ，从目标状态往初始状态推 ，从初始状态往目标状态输出 
 31 void Print(int n)
 32 {
 33     if(n!=flag_star)
 34     {
 35         Print(vis[n].flag);
 36         printf("%c",vis[n].dir); 
 37     }
 38  } 
 39 //求阶乘 
 40 void Init()
 41 {
 42     fact[1]=1;
 43     for(int i=2;i<10;i++)
 44     {
 45         fact[i]=fact[i-1]*i;
 46     }
 47 }
 48 //康拓展示 
 49 int Hash(int a[])
 50 {
 51     int ans=0;
 52     for(int i=0;i<9;i++)
 53     {
 54         int temp=0;
 55         for(int j=i+1;j<9;j++)
 56         {
 57             if(a[j]<a[i])
 58             {
 59                 temp++;
 60             }
 61         }
 62         ans+=temp*fact[8-i];
 63     }
 64     return ans;
 65 }
 66 //str和dir是相对应的 
 67 char str[5]="udlr";
 68 int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
 69 
 70 int bfs(node star)
 71 {
 72     queue<node> Q;
 73     Q.push(star);
 74     while(!Q.empty())
 75     {
 76         node q=Q.front();
 77         Q.pop();
 78         int flag=Hash(q.a); 
 79         if(flag==END)
 80         {
 81             return flag;
 82         }
 83         int pos=q.x;
 84         for(int i=0;i<4;i++)
 85         {
 86             int xpos=q.x/3;
 87             int ypos=q.x%3;
 88             int xx=xpos+dir[i][0];
 89             int yy=ypos+dir[i][1];
 90             if(xx>=0&&xx<3&&yy>=0&&yy<3)
 91             {
 92                 int now=xx*3+yy;
 93                 swap(q.a[now],q.a[pos]);
 94                 q.x=now;
 95                 int v=Hash(q.a);
 96                 if(v==END)
 97                 {
 98                     vis[v].dir=str[i];
 99                     vis[v].flag=flag;
100                     return v;
101                  } 
102                 if(vis[v].flag==-1)
103                 {
104                     vis[v].dir=str[i];
105                     vis[v].flag=flag;
106                     Q.push(q);
107                 }
108                 //回退 
109                 q.x=pos;
110                 swap(q.a[now],q.a[pos]);
111             }
112         }
113      } 
114      return maxn;
115 }
116 
117 int main()
118 {
119     Init();
120     char c[3];
121 
122     while(~scanf("%s",c))
123     {
124         for(int i=0;i<maxn;i++)
125         {
126             vis[i].flag=-1;
127         }
128         node star; 
129         if(c[0]=='x')
130         {
131             star.a[0]=0;
132             star.x=0;
133         }
134         else
135         {
136             star.a[0]=c[0]-'0';
137          } 
138         for(int i=1;i<9;i++)
139         {
140             scanf("%s",c);
141             if(c[0]=='x')
142             {
143                 star.x=i;
144                 star.a[i]=0;
145             }
146             else
147             {
148                 star.a[i]=c[0]-'0';
149             }
150         }
151         //初始状态 
152         flag_star=Hash(star.a);
153         //特判，如果已经到达最后状态 
154         if(flag_star==END)
155         {
156             printf("
");
157             continue;
158         }
159         int f=bfs(star);
160         if(f==END)
161         {
162             Print(f);
163             printf("
");
164         }
165         else
166         {
167             printf("unsolvable
");
168         }
169     }
170     return 0;
171  }

直接BFS

方法二：

因为有多个输入，直接BFS会T，所以可以反向BFS预处理，以目标状态为起点搜出所以可以到达的状态。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<string>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<cmath>
  7 #include<queue>
  8 //目标状态对应的自然数 
  9 #define END 46233
 10 using namespace std;
 11 //9! 
 12 const int maxn=362882;
 13 //初始状态对应的自然数 
 14 int flag_star;
 15 //判重 
 16 struct
 17 {
 18     int flag;//指向上一个状态 
 19     char dir;//从上一状体到这一状态的方向 
 20 }vis[maxn];
 21 //阶乘，以求康拓展示开 
 22 int fact[10];
 23 //记录当前棋盘状态和x的位置 
 24 struct node
 25 {
 26     int a[10];//当前棋盘的状态 
 27     int x;//x所在的位置 
 28 };
 29 
 30 //递归输出路径 ，从目标状态往初始状态推 ，从初始状态往目标状态输出 
 31 void Print(int n)
 32 {
 33     if(n!=END)
 34     {
 35         printf("%c",vis[n].dir); 
 36         Print(vis[n].flag);
 37     }
 38 } 
 39 //求阶乘 
 40 void Init()
 41 {
 42     fact[1]=1;
 43     for(int i=2;i<10;i++)
 44     {
 45         fact[i]=fact[i-1]*i;
 46     }
 47 }
 48 //康拓展示 
 49 int Hash(int a[])
 50 {
 51     int ans=0;
 52     for(int i=0;i<9;i++)
 53     {
 54         int temp=0;
 55         for(int j=i+1;j<9;j++)
 56         {
 57             if(a[j]<a[i])
 58             {
 59                 temp++;
 60             }
 61         }
 62         ans+=temp*fact[8-i];
 63     }
 64     return ans;
 65 }
 66 //str和dir是相对应的 
 67 //char str[5]="udlr";
 68 char str[5]="durl";
 69 int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
 70 
 71 void bfs()
 72 {
 73     node star;
 74     //以目标状态（1 2 3 4 5 6 7 0）为起点 
 75     for(int i=0;i<8;i++)
 76     {
 77         star.a[i]=i+1;
 78     }
 79     star.a[8]=0;
 80     star.x=8;
 81     queue<node> Q;
 82     Q.push(star);
 83     while(!Q.empty())
 84     {
 85         node q=Q.front();
 86         Q.pop();
 87         int flag=Hash(q.a); 
 88         int pos=q.x;
 89         for(int i=0;i<4;i++)
 90         {
 91             int xpos=q.x/3;
 92             int ypos=q.x%3;
 93             int xx=xpos+dir[i][0];
 94             int yy=ypos+dir[i][1];
 95             if(xx>=0&&xx<3&&yy>=0&&yy<3)
 96             {
 97                 int now=xx*3+yy;
 98                 swap(q.a[now],q.a[pos]);
 99                 q.x=now;
100                 int v=Hash(q.a);
101                 if(vis[v].flag==-1)
102                 {
103                     vis[v].dir=str[i];
104                     vis[v].flag=flag;
105                     Q.push(q);
106                 }
107                 //回退 
108                 q.x=pos;
109                 swap(q.a[now],q.a[pos]);
110             }
111         }
112      } 
113 }
114 
115 int main()
116 {
117     Init();
118     char c[3];
119     for(int i=0;i<maxn;i++)
120     {
121         vis[i].flag=-1;
122     }
123     bfs(); 
124     while(~scanf("%s",c))
125     {
126         
127         node star; 
128         if(c[0]=='x')
129         {
130             star.a[0]=0;
131             star.x=0;
132         }
133         else
134         {
135             star.a[0]=c[0]-'0';
136          } 
137         for(int i=1;i<9;i++)
138         {
139             scanf("%s",c);
140             if(c[0]=='x')
141             {
142                 star.x=i;
143                 star.a[i]=0;
144             }
145             else
146             {
147                 star.a[i]=c[0]-'0';
148             }
149         }
150         //初始状态 
151         flag_star=Hash(star.a);
152         //特判，如果已经到达最后状态 
153         if(flag_star==END)
154         {
155             printf("
");
156             continue;
157         }
158         if(vis[flag_star].flag!=-1)
159         {
160             Print(flag_star);
161             printf("
");
162         }
163         else
164         {
165             printf("unsolvable
");
166         }
167     }
168     return 0;
169  }

View Code

有几点要注意的地方：

1.因为以目标状态为起点，方向正好反了

1 //char str[5]="udlr";
2 char str[5]="durl";
3 int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

方向要变

2.输出要变，直接从当前状态外目标状态推

 1 void Print(int n)
 2 {
 3 //    if(n!=flag_star)
 4 //    {
 5 //        Print(vis[n].flag);
 6 //        printf("%c",vis[n].dir); 
 7 //    }
 8     if(n!=END)
 9     {
10         printf("%c",vis[n].dir); 
11         Print(vis[n].flag);
12     }
13 }

View Code

3.判断是否有解是输入状态是否在bfs的时候被经过。

1 if(vis[flag_star].flag!=-1)
2         {
3             Print(flag_star);
4             printf("
");
5         }
6         else
7         {
8             printf("unsolvable
");
9         }

View Code

方法三：参考别人的代码。A*算法。

最关键的部分是估价函数和判断逆序是否为偶数的剪枝

估价函数，是根据与目标解的曼哈顿距离，也就是每个数字与目标位置的曼哈顿距离之和。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 #include<cmath>
  6 using namespace std;
  7 
  8 struct node     //状态
  9 {
 10     int a[10];
 11     int f, h, g;
 12     int x;      //x在的位置
 13 
 14 //    bool operator<(const node n1)const{     //优先队列第一关键字为h,第二关键字为g
 15 //        return h!=n1.h?h>n1.h:g>n1.g;
 16 //    }
 17     friend bool operator < (node a, node b)
 18     {
 19         return a.f > b.f;
 20     }
 21 };
 22 
 23 priority_queue<node>que;
 24 int fac[10];
 25 //46233
 26 struct
 27 {
 28     int father;
 29     char dir;
 30 }vis[362881];
 31 
 32 int get_h(int a[])
 33 {
 34     int h = 0;
 35     for(int i = 0; i < 8; i++)
 36     {
 37         if(a[i])
 38             h += fabs((a[i]-1)/3 - i/3) + fabs((a[i]-1)%3 - i%3);
 39     }
 40     return h;
 41 }
 42 
 43 int Hash(int a[])
 44 {
 45     int ans = 0;
 46     for(int i = 0; i < 9; i++)
 47     {
 48         int tmp = 0;
 49         for(int j = i+1; j < 9; j++)
 50         {
 51             if(a[i] > a[j]) tmp++;
 52         }
 53         ans += tmp*fac[8-i];
 54     }
 55     return ans+1;
 56 }
 57 
 58 void prin(int n)
 59 {
 60 //    printf("n=%d
", n);
 61     if(vis[n].father!=-1)
 62     {
 63         prin(vis[n].father);
 64         printf("%c", vis[n].dir);
 65     }
 66 }
 67 
 68 void SWAP(int &x, int &y)
 69 {
 70     int t = x;
 71     x = y;
 72     y = t;
 73 }
 74 
 75 int dir[4][2] = { {1, 0}, {-1, 0}, {0, -1}, {0, 1} };
 76 char dd[] = "dulr";
 77 
 78 bool is(int a[])
 79 {
 80     int ans = 0;
 81     for(int i = 0; i < 9; i++)
 82     {
 83         if(a[i])
 84         for(int j = i+1; j < 9; j++)
 85         {
 86             if(a[i] > a[j] && a[j])
 87                 ans++;
 88         }
 89     }
 90     return !(ans&1);
 91 }
 92 
 93 void debug(int a[])
 94 {
 95     for(int i = 0; i < 3; i++)
 96     {
 97         for(int j = 0; j < 3; j++)
 98         {
 99             printf("%d ", a[i*3+j]);
100         }
101         printf("
");
102     }
103     printf("
");
104 }
105 
106 int bfs(node star)
107 {
108     while(!que.empty()) que.pop();
109     que.push( star );
110     star.h = get_h( star.a );    star.g = 0;
111     star.f = star.g + star.h;
112     vis[ Hash( star.a ) ].father = -1;
113     while(!que.empty())
114     {
115         node tmp = que.top();
116         que.pop();
117         int father = Hash(tmp.a);
118 
119 //        printf("father=%d
", father); debug(tmp.a);
120 
121         for(int i = 0; i < 4; i++)
122         {
123             int x = dir[i][0] + tmp.x/3;
124             int y = dir[i][1] + tmp.x%3;
125             if(0 <= x && x < 3 && 0 <= y && y < 3)
126             {
127                 node s = tmp;
128                 s.x = x*3+y;
129                 SWAP( s.a[ tmp.x ], s.a[ s.x ] );
130                 s.g++;
131                 s.h = get_h( s.a );
132                 s.f = s.h + s.g;
133                 int son = Hash(s.a);
134 //                printf("tmp.x =%d s.x=%d
", tmp.x, s.x);
135 //                printf("son=%d
", son); debug(s.a);
136                 if(son == 46234)
137                 {
138                     vis[ son ].father = father;
139                     vis[ son ].dir = dd[i];
140                     prin(46234);printf("
");
141                     return 0;
142                 }
143                 if(!vis[ son ].father && is(s.a))
144                 {
145                     vis[ son ].father = father;
146                     vis[ son ].dir = dd[i];
147                     que.push( s );
148                 }
149             }
150         }
151     }
152     return 1;
153 }
154 
155 
156 int main(void)
157 {
158     int i;
159     fac[1] = 1;
160     for(i = 2; i < 10; i++) fac[i] = fac[i-1]*i;
161     node star;
162     char in[2];
163 //    freopen("ou.txt", "w", stdout);
164     while(~scanf("%s", in))
165     {
166         memset(vis, 0, sizeof(vis));
167         if(in[0] == 'x')
168         {
169             star.a[0] = 0;
170             star.x = 0;
171         }
172         else star.a[0] = in[0] - '0';
173         for(i = 1; i < 9; i++)
174         {
175             scanf("%s", in);
176             if(in[0] == 'x')
177             {
178                 star.a[i] = 0;
179                 star.x = i;
180             }
181             else star.a[i] = in[0] - '0';
182         }
183         if(!is(star.a))
184         {
185             printf("unsolvable
");continue;
186         }
187         if(Hash(star.a) == 46234) {printf("
"); continue;}
188         if(bfs(star))
189         {
190             printf("unsolvable
");
191         }
192     }
193     return 0;
194 }

【算法系列学习三】[kuangbin带你飞]专题二 搜索进阶 之 A-Eight 反向bfs打表和康拓展开

[kuangbin带你飞]专题二 搜索进阶 之 A-Eight

【算法系列学习三】[kuangbin带你飞]专题二搜索进阶之 A-Eight 反向bfs打表和康拓展开

[kuangbin带你飞]专题二搜索进阶之 A-Eight