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

ACM模版

描述

题解

传说中和八皇后一样过分经典的搜索问题，所以网上一查，各种强势题解一大堆，更有丧心病狂者，写了《八数码的八境界》这种深度剖析此问题的 blog，让我不敢再多言此题，毕竟我想不了那么系统，所以，我也就只剩下拿着该大牛的 blog 一饱眼福的任务了……

这个问题核心就是搜索，不过问题的优化十分多样化，对于这道题，我的选择是 反向bfs + 打表 + hash，成功 AC，对于其他丧心病狂的解法儿，略懂一二，但是没有耐心全部写一遍了，毕竟那样就太强了，不是我的风格。

这个问题的一个拓展是15-puzzle，对于这个题，用我上边的方法就不行了，简单的搜索优化已经不足以对付其庞大的状态数，需要根据曼哈顿距离进行迭代加深启发式搜索，一般是 A* 算法和 IDA* 算法，具体可以看看《挑战程序设计竞赛2算法和数据结构》最后一章-启发式搜索，有详细代码可以参考，写得十分不错哦~~~

代码

#include <iostream> #include <cstdio> #include <queue> using namespace std; const int MAXN = 362882 + 10; // 9! + 10 int sta_contor; int end_contor; int target[10] = {1, 2, 3, 4, 5, 6, 7, 8, 0}; struct { int next; char dir; } vis[MAXN]; int fac[10]; // 记录当前棋盘状态和x的位置 struct node { int a[10]; int x; }; // hash-康拓展开式 int hash_cantor(int a[]) { int ans = 0; for (int i = 0; i < 9; i++) { int temp = 0; for (int j = i + 1; j < 9; j++) { if (a[j] < a[i]) { temp++; } } ans += temp * fac[8 - i]; } return ans; } char str[5] = "durl"; int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; void bfs(node end) { queue<node> Q; Q.push(end); while (!Q.empty()) { node n = Q.front(); Q.pop(); int n_contor = hash_cantor(n.a); int pos = n.x; for (int i = 0; i < 4; i++) { int x = n.x / 3; int y = n.x % 3; int x_ = x + dir[i][0]; int y_ = y + dir[i][1]; if (x_ >= 0 && x_ < 3 && y_ >= 0 && y_ < 3) { int cnt = x_ * 3 + y_; swap(n.a[cnt], n.a[pos]); n.x = cnt; int v = hash_cantor(n.a); if (vis[v].next == -1 && v != end_contor) { vis[v].dir = str[i]; vis[v].next = n_contor; Q.push(n); } n.x = pos; swap(n.a[cnt], n.a[pos]); } } } } void init() { fac[0] = fac[1] = 1; for (int i = 2; i < 10; i++) { fac[i] = fac[i - 1] * i; } for (int i = 0; i < MAXN; i++) { vis[i].next = -1; } node end; swap(end.a, target); end.x = 8; end_contor = hash_cantor(end.a); bfs(end); } void printRes(int n) { while (vis[n].next != -1) { printf("%c", vis[n].dir); n = vis[n].next; } } int main() { init(); char s[3]; while (~scanf("%s", s)) { node star; if (s[0] == 'x') { star.a[0] = 0; star.x = 0; } else { star.a[0] = s[0] - '0'; } for (int i = 1; i < 9; i++) { scanf("%s", s); if (s[0] == 'x') { star.x = i; star.a[i] = 0; } else { star.a[i] = s[0] - '0'; } } sta_contor = hash_cantor(star.a); if (sta_contor == end_contor) { printf("\n"); } else if (vis[sta_contor].next != -1) { printRes(sta_contor); printf("\n"); } else { printf("unsolvable\n"); } } return 0; }

参考

《八数码的八境界》