原题链接

八数码

题意非常简单，给你一个八数码，如果其有解，输出一个最优解并且给出路径；如果没有则输出unsolvable。

思路

本题是一道好题目，涉及到了以下几个知识点：

  1. 如何优化盲目搜索（A*算法）
  2. 如何有效存取数码（康托散列）
  3. 如何输出路径

其中后两点不是这篇博文的主要话题，感兴趣的读者可以自行阅读代码理解或者查阅其他文章，本文主要就题谈谈简单的A*算法。

什么是A*算法？

一言以蔽之，就是基于优先队列的BFS算法，其中排序的依据是自定义的一个启发函数。问题来了，怎么定义启发函数？好的启发函数显然能够让状态空间大大缩小，但代价函数也不应该过于复杂。但无论如何，

启发函数估算出的代价一定不能大于真实的代价。

如果没有这样的约束，那么我们可能错误估计一个真实最优状态的代价，从而导致在错误分支上搜索。

就八数码问题而言，曼哈顿距离是一个不错的代价函数。一来，每个位置上的元素与其应该在的距离确实衡量了其与目标状态的距离，并且这样的估值是显然小于真实估值的。

为什么？

思考如下的一种情况

1
2
3
4
|---|
|3 2|
|1 0|
|---|

通过曼哈顿距离，计算出的估值是2（1,3不在原位），也就是对应两个节点直接交换——而这是不允许的。最好情况下，曼哈顿距离恰好与真实值相等，但往往是小于真实值的。

仅仅如此，够了吗？

有了状态，我们还需要去考虑如何保留状态。最简单的想法，我们直接使用一个字符串记录当前的状态，每次使用的时候还原即可。换而言之，基于map。实际上，有一种叫做康托散列的方法，可以快速计算（平方时间，不过此处可以当做常数）一个排列的散列，确切地说，是将其映射到1-N!之间。

实现

搜索题算法实现往往比较复杂，我在写本题的时候因为如下原因wa多次：

  1. typo
  2. 实现错误
  3. 效率不够

最终AC算法如下（Acwing 10个点，共耗时136ms）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <bits/stdc++.h>
using namespace std;

struct rec{
    // l: 当前地图中0的位置
    // dist: 实际已经走的距离 + 预测还要走的距离
    // m: 地图表示的字符串
    int l;
    int dist;
    string m;
    rec(int l_,string m_, int dist_):l(l_),m(m_), dist(dist_){
    }
};

bool operator<(const rec& a,const rec& b){
        return a.dist > b.dist;
}

typedef pair<int,int> pii;
// d: <序列化值对应, 到当前状态的最小距离>
// f: <序列化值, 上一步>
// go: <序列化值, 对应的cmd>
// q: A*状态的优先队列
const int N = 362886;
int d[N];
int f[N];
int go[N];
priority_queue<rec> q;


// 模拟`x`运动
int dx[] = {-1, 1,0,0};
int dy[] = {0,0,-1,1};
char cmd[] = {'u','d','l','r'};

// cantor hash
int fac[11];
void initFac(){
    fac[0] = fac[1] = 1;
    for(int i = 2 ;i<=10;i++){
        fac[i] = i*fac[i-1];
    }
}

// 使用cantor散列法求出排列的散列值
int cantor(const string& s){
    int len = s.size();
    int res = 1;
    for(int i=0;i<len;i++){
        int temp = 0;
        for(int j = i+1;j<len;j++){
            if(s[j]<s[i])temp++;
        }
        res += (temp) * fac[len-i-1];    
    }

    return res;
}

inline int evaluate(const string& s){
    int ret = 0;
    int len = s.size();
    
    for(int i = 0;i<len;i++){
        int x = i/3, y = i%3;
        int cur = s[i]-'0';
        if(cur==0) ret+= abs(x-2)+abs(y-2);
        else{
            int fx = (cur-1)/3, fy = (cur-1)%3;
            ret += abs(x-fx)+abs(y-fy);
        }
    }
    
    return ret;
}

int bfs(int l,const string& start, int dist, const string& e){
    memset(f,-1,sizeof f);
    memset(go,-1,sizeof go);
    memset(d,-1,sizeof d);
    q.push(rec(l, start, dist));
    d[cantor(start)] = 0;
    
    while(q.size()){
        
        rec cur = q.top();q.pop();
        if(cur.m==e){
            return d[cantor(cur.m)];
        }
        pii pos(cur.l/3,cur.l%3);
        int val = cantor(cur.m);
        for(int i = 0; i<4; i++){
            int x = pos.first + dx[i], y = pos.second + dy[i];
            string m = cur.m;
            if(x>=0 && x<3 && y>=0 && y<3){
                int pos_to_swap = x*3 + y;
                swap(m[cur.l],m[pos_to_swap]);
                int dumpVal = cantor(m);
                if(d[dumpVal]==-1 || d[dumpVal]>d[val]+1){
                    d[dumpVal] = d[val]+1;
                    f[dumpVal] = val;
                    go[dumpVal] = i;
                    q.push(rec(pos_to_swap,m,d[dumpVal]+evaluate(m)));
                }
            }
        }
    }
    
    return -1;
}

void print(int val){
    if(f[val]==-1){
        return;
    }
    print(f[val]);
    putchar(cmd[go[val]]);
}

int main(){
    initFac();
    string e = "123456780";
    
    string start;
    int l ;
    for(int i=0;i<9;i++){
        char tem;cin>>tem;
        if(tem=='x')tem='0', l = i;
        start.append(1,tem);
    }
    
    
    // 判断是否理论上不可行
    int cnt = 0;
	for (unsigned i = 0; i < start.size(); i++)
		if (start[i] != '0')
			for (unsigned int j = 0; j < i; j++)
				if (start[j] != '0' && start[j] > start[i]) ++cnt;
	if (cnt & 1) {
		cout << "unsolvable" << endl;
		return 0;
	}
	
    auto ret = bfs(l,start,evaluate(start),e);
    
    if(ret){
        print(cantor(e));
    }else{
        cout<<"unsolvable\n";
    }
    
    return 0;
}


// 5 3 x 7 8 2 4 6 1
// 6 4 7 8 5 x 3 2 1
// 4 7 x 1 3 6 8 5 2