A*简介

某点u的距离f(u)定义如下：
$f(u)=g(u)+h(u)$
g(u)：起点到u走的距离
h(u)：u到终点估计的距离，保证 0 ≤ h ( u ) ≤ h ′ ( u ) 0 \\leq h(u) \\leq h'(u) 0≤h(u)≤h′(u)。其中h’(u)是真实距离

和普通BFS不同，A*算法用的是优先队列，根据f从小到大排序（小根堆）。拓展点时只有g(u)变小才进队，终点出队时停止。

性质1

估计距离<=真实距离，保证了终点第一次出队时，一定是最优解。

反证法：
假设终点e第一次出队时距离f(e)不是最优解f(e)'，之后才会由其他点更新进队再出队得到最优解。
由于之后还要再更新，所以最优解路径上总有点会在队列里，不妨设点为u。
那么 g ( u ) + h ( u ) ≤ g ( u ) + h ′ ( u ) = f ( e ) ′ g(u) + h(u) \\leq g(u) + h'(u) = f(e)' g(u)+h(u)≤g(u)+h′(u)=f(e)′。
因为D不是最优解，所以 f ( e ) > f ( e ) ′ f(e) > f(e)' f(e)>f(e)′，故有 f ( e ) > f ( e ) ′ ≥ g ( u ) + h ( u ) = f ( u ) f(e) > f(e)' \\geq g(u) + h(u) = f(u) f(e)>f(e)′≥g(u)+h(u)=f(u)。
那么此时应该出队的是点u，而不是终点，矛盾。

性质2

除了终点以外的点出队，不一定是最优解
假设点u是最优解上的点，起点到u有两条路径a和b，真实距离分别是3和5。假设所有点的h都为0，但是路径a上某点v的h(v)为一个很大的数（但小于到终点的真实距离）。

那么在进队时，走到点v前，会先将路径b上的其他点都进队（因为h(v)很大导致f(v)很大）。并通过路径b更新u的距离5，此时u的最优距离显然是3。

基于这个性质，A*无法判断重复，只能通过终点出队停止。
PS. BFS入队时就可以判断重复，dijkstra出队的时候判断重复。

八数码

题目

题目链接
x表示空位置，每次可以将一个数字移到空位置上，问从给定状态移动到目标状态(1 2 3 4 5 6 7 8 x)至少要几步。
输入初始状态，输出x移动的路径，上下左右对应：u、d、l、r。无解输出unsolvable。

判断是否有解

可以看序列的逆序对的数量，偶数则有解，奇数则无解。

必要性：如果有解则逆序对数量是基数。

如题目所示：
2 3 4
1 5 x
7 6 8
序列为：2 3 4 1 5 x 7 6 8

当移动的数是左右移动时，例如5向右移，不会改变序列的位置，逆序对不变。
当移动的数是上下移动时，例如8向上移。序列变为：2 3 4 1 5 8 7 6 x。可以看到上下移只会导致一个数往前后往后移动两位。那么只有可能改变两个逆序对，这边是新增(8, 7)，(8, 6)，其他情况则是减少两个、或者加一减一。都不会改变逆序对的奇偶性。

充分性证明较复杂，不再赘述。

估计距离函数h

当前状态中各个数的位置，到其目标位置的曼哈顿距离之和。

代码

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;typedef pair<int, string> PIS;void findX(int &x, int &y, string &ts) {for (int i = 0; i < 9; i ++ ) {if (ts[i] == 'x') {x = i / 3;y = i % 3;}}
}int h(string s) {int dis = 0;for (int i = 0; i < 9; i ++ ) {if (s[i] == 'x') continue;int num = s[i] - '1';dis += abs(num / 3 - i / 3) + abs(num % 3 - i % 3);}return dis;
}string bfs(string start) {priority_queue<PIS, vector<PIS>, greater<PIS>> heap;unordered_map<string, int> g;unordered_map<string, PIS> pre;string ans;int dx[4] = {-1, 0, 1, 0};int dy[4] = {0, -1, 0, 1};char ds[5] = "uldr";heap.push({h(start), start});g[start] = 0;while(!heap.empty()) {PIS t = heap.top();heap.pop();string ts = t.second;if (ts == "12345678x") {while(ts != start) {PIS preTs = pre[ts];int i = preTs.first;ts = preTs.second;ans = ds[i] + ans;}return ans;}int x, y;findX(x, y, ts);for (int i = 0; i < 4; i ++ ) {int tx = x + dx[i];int ty = y + dy[i];if (tx > 2 || ty > 2 || tx < 0 || ty < 0) continue;string newS = ts;swap(newS[x * 3 + y], newS[tx * 3 + ty]);if (!g.count(newS) || g[newS] > g[ts] + 1) {g[newS] = g[ts] + 1;heap.push({g[newS] + h(newS), newS});pre[newS] = {i, ts};}}}return "";
}int main() {char ch;string input, invS;for (int i = 0; i < 9; i ++ ) {cin >> ch;input += ch;if (ch != 'x')  invS += ch;}int invCnt = 0;for (int i = 0; i < 9; i ++ ) {for (int j = i + 1; j < 9; j ++ ) {if (invS[i] > invS[j]) {invCnt ++ ;}}}if (invCnt & 1) {printf("unsolvable\\n");}else {string ans = bfs(input);cout << ans << endl;}return 0;
}