ACWING 179. 八数码（A*算法）

本文主要是介绍ACWING 179. 八数码（A*算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在一个3×3的网格中，1~8这8个数字和一个“X”恰好不重不漏地分布在这3×3的网格中。

例如：

1 2 3
X 4 6
7 5 8
在游戏过程中，可以把“X”与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 X
例如，示例中图形就可以通过让“X”先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1 2 3 1 2 3 1 2 3 1 2 3
X 4 6 4 X 6 4 5 6 4 5 6
7 5 8 7 5 8 7 X 8 7 8 X
把“X”与上下左右方向数字交换的行动记录为“u”、“d”、“l”、“r”。

现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

输入格式
输入占一行，将3×3的初始网格描绘出来。

例如，如果初始网格如下所示：
1 2 3

x 4 6

7 5 8

则输入为：1 2 3 x 4 6 7 5 8

输出格式
输出占一行，包含一个字符串，表示得到正确排列的完整行动记录。如果答案不唯一，输出任意一种合法方案即可。

如果不存在解决方案，则输出”unsolvable”。

输入样例：
2 3 4 1 5 x 7 6 8
输出样例
ullddrurdllurdruldr

思路：
设初始状态为$start$，终点状态为$end$。
$f(state)$代表转移到$state$这个状态所需的最小花费，$h(state)$代表从$state$状态出发到达终点状态的预估最小花费（估价函数）。

$A\ast$算法就是用一个堆，每次取出对应$f(state)+h(state)$最小的状态，用这个状态去松弛其他状态。如果$f(state)$始终为0，那么就退化为$dijkstra$。个人感觉就是带估价函数优化过的优先队列$bfs$。

不过如果本身就无解的话，那么无论怎么优化，都会遍历所有状态，那么复杂度会变得很高。查询资料可得，当起点和终点的八数码状态展开成一维向量后的逆序数奇偶性不同，就无解。

简要证明的话：每次移动，如果是左右移动，那么逆序数不变。如果是上下移动，就等于把一个数前移（或后移）两步，逆序数±2或者不变。所以不管怎么移动，奇偶性都不变。

具体证明可以参考：链接

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
using namespace std;typedef pair<int,string>PIS;
unordered_map<string,int>dist;
unordered_map<string,pair<string,char>>pre;
priority_queue<PIS,vector<PIS>,greater<PIS>>heap;
string ed = "12345678x";
char dir[] = "rlud";
int dirx[] = {0, 0,-1,1};
int diry[] = {1,-1, 0,0};int f(string state) {int cnt = 0;for(int i = 0;i < 9;i++) {if(state[i] != 'x') {int t = state[i] - '1';cnt += abs(t / 3 - i / 3) + abs(t % 3 - i % 3);}}return cnt;
}
string bfs(string start) {dist[start] = 0;heap.push({f(start),start});while(!heap.empty()) {string state = heap.top().second;heap.pop();if(state == ed) break;int step = dist[state];int t = state.find('x');int x = t / 3,y = t % 3;string source = state;for(int i = 0;i < 4;i++) {int dx = x + dirx[i],dy = y + diry[i];if(dx < 0 || dy < 0 || dx >= 3 || dy >= 3) continue;swap(state[x * 3 + y],state[dx * 3 + dy]);if(!dist.count(state) || dist[state] > step + 1) {dist[state] = step + 1;heap.push({dist[state] + f(state),state});pre[state] = {source,dir[i]};}swap(state[x * 3 + y],state[dx * 3 + dy]);}}string ans;while(ed != start) {ans += pre[ed].second;ed = pre[ed].first;}reverse(ans.begin(),ans.end());return ans;
}
int main() {string start,seq;for(int i = 0;i < 9;i++) {char c;cin >> c;start += c;if(c != 'x') seq += c;}int cnt = 0;for(int i = 0;i < 8;i++) {for(int j = i + 1;j < 8;j++) {if(seq[i] > seq[j]) cnt++;}}if(cnt & 1) cout << "unsolvable" << endl;else cout << bfs(start) << endl;return 0;
}

这篇关于ACWING 179. 八数码（A*算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---