搜索专题3 | 八数码 HDU - 1043
本搜索专题会参考vjudge上的《kuangbin带你飞》系列题目，前面2篇是基础题，后面会慢慢复杂起来！加油！
前两篇展示了DFS和BFS的基本应用，可能大家觉得比较简单，回顾一下，DFS一般用于求所有解的情况，BFS用于求最短路类型的问题，DFS缺点是容易迷失自己，优点是不用维护队列，省空间。BFS缺点是需要队列在处理寻路这样的问题时比较耗费空间，优点是循序渐进的容易找最优解。
本篇接着看BFS的启发式搜索A*算法。
虽然BFS搜索路径已经不错了，但是每次都是按部就班的从队列里先进先出的取元素，这样有点太古板了。于是在某些情况下可以采用优先队列来替代普通队列，优先队列这个BFS搜索本来打算写一篇文章的，现在直接放在A*里面理解吧。
优先队列是指在搜索解时，选取一条最优路径，比如当前代价最小的路径。然而这样有一个缺点，那就是当前代价小并不代表最终这条路径是最小的。
理想情况下是知道当前消耗和接下来需要消耗的，然而未知路径的消耗只有先知才知道
。
如下图：
于是有人便想到了，虽然不能够确定未知路径的代价H，但是我们可以大概估算一下代价H啊，小学老师就说过，估算是一项非常重要的能力，A*算法里面估算就是核心了（虽然看上去会感觉不靠谱）。
嗯，大概思路就有了，A*算法 = 优先队列 + 未知估值
那么未知估值具体要怎么做呢？
这又是一个类似于DP算法要怎么写呢的问题
只有针对特定的题目，我们才知道要怎么写，适合意会不好言传，还是看题领悟吧。
题目很简单，其实重点是看懂代码。代码其实也很清晰，重点是花点耐心看完~
The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let's call the missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as:
15谜题已经有100多年历史了。即使不知其名，肯定也见过。它由15个滑动块组成，每个滑动块由数字1到15标记，并且被放在4x4大小的框框里面，缺失一个块。缺失的称之为x。谜题的目标就是将这些块有序的整理起来。如下图：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 x
where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:
唯一合法的操作是交换x与相邻的块。
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8
9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12
13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x
r-> d-> r->
The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively.
每一步操作称之为rlud，分别是右移/左移/上移/下移。
Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).
并不是所有的谜题都能被解决，
In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three arrangement.
在这个问题上，你需要写一个8谜题，解决3x3上的问题。
Input
You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle
输入会成为一行。
1 2 3
x 4 6
7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
Output
You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. Do not print a blank line between cases.
如果没有解，输出unsolvable，否则输出路径。
Sample Input
2 3 4 1 5 x 7 6 8
Sample Output
ullddrurdllurdruldr
解题思路：
八数码问题，就是小时候玩的那个小玩具。
重点可以看看A*的大概流程：
1：初始化，将起始位置放入队列
priority_queue<state_t> q; q.push(a);
2：4个方向前进，计算每个方向的估值，这里的估值是计算曼哈顿距离，也就是x/y轴的差值绝对值之和。当前步数作为当前消耗的代价G。放入队列。
3：取队列元素，重复2过程。
解题代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 4e5 + 10;
int ha[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
/*这个ha[9]数组是用来计算hash值的，这个数组中的值分别是0!,1!,2!,3!,4!,5!,6!,7!,8!*/
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
char d[10] = "udlr";
int vis[maxn]; //判重
struct state_t {
int f[3][3]; //当前这个转态每个位置上的值
int x, y;
int g, h;
int hash_num;
// 估值为h+g
bool operator<(const state_t a) const {
return h + g > a.h + a.g; //优先队列保证出队的是估值函数值较小的。
}
};
struct path {
int pre;
char ch;
} p[maxn]; //用于记录路径
// 评估函数，获得评估值
// 计算1~8的数字回到原点需要的步数作为评估值，必定小于实际操作数
int get_h(state_t a) {
int i, j, ans = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (a.f[i][j]) {
// 曼哈顿距离
ans += abs(i - (a.f[i][j] - 1) / 3) + abs(j - (a.f[i][j] - 1) % 3);
}
}
}
return ans;
}
//康托展开
int get_hash(state_t e) {
int a[9], i, j, k = 0, ans = 0;
for (i = 0; i < 3; i++) //将数据排成一排，便于计算
{
for (j = 0; j < 3; j++)
a[k++] = e.f[i][j];
}
for (i = 0; i < 9; i++) //计算hash值
{
k = 0;
for (j = 0; j < i; j++)
if (a[j] > a[i])
k++;
ans += ha[i] * k;
}
return ans;
}
void print(int x) {
if (p[x].pre == -1)
return;
print(p[x].pre);
printf("%c", p[x].ch);
}
void AStar(state_t a) {
memset(vis, 0, sizeof(vis));
int end_ans, xx, yy, k;
state_t vw, vn;
// 最终状态的值
for (int i = 0; i < 9; i++) {
vw.f[i / 3][i % 3] = (i + 1) % 9; //目标转态时各个位置的值
}
end_ans = get_hash(vw); //目标转态时的hash值
a.hash_num = get_hash(a);
a.g = 0; //初始状态到状态a的代价函数
a.h = get_h(a); //从状态a到目标状态的最佳路径的估计代价
vis[a.hash_num] = 1;
p[a.hash_num].pre = -1;
if (a.hash_num == end_ans) {
printf("\n");
return;
}
priority_queue<state_t> q;
q.push(a);
while (!q.empty()) {
a = q.top(), q.pop();
for (int i = 0; i < 4; i++) {
xx = a.x + dir[i][0];
yy = a.y + dir[i][1];
if (xx < 0 || yy < 0 || xx >= 3 || yy >= 3)
continue;
vw = a;
swap(vw.f[a.x][a.y], vw.f[xx][yy]); //交换双方的值
k = get_hash(vw);
if (vis[k])
continue;
vis[k] = 1;
vw.hash_num = k;
// 当前x的位置
vw.x = xx;
vw.y = yy;
// 更新g，增加1
vw.g++;
// 评估距离
vw.h = get_h(vw);
p[k].pre = a.hash_num;
p[k].ch = d[i];
//如果当前状态的hash值等于目标状态的hash值，表示已经到达目标状态
if (k == end_ans)
{
print(k);
printf("\n");
return;
}
q.push(vw);
}
}
}
int main() {
char a[30];
while (gets(a)) {
int i, j, k, n;
// 输入初始状态
state_t e;
n = strlen(a);
for (i = 0, j = 0; i < n; i++) {
if (a[i] == ' ')
continue;
if (a[i] == 'x') {
// x设置为0
e.f[j / 3][j % 3] = 0;
e.x = j / 3;
e.y = j % 3;
} else
e.f[j / 3][j % 3] = a[i] - '0';
j++;
}
// 这边涉及到一个逆序数问题，如果开始状态的逆序数为奇数，那么这个状态只能到达逆序数为奇数的转态，同理偶数逆序数的状态也只能到达逆序数为偶数的状态
// 逆序数：前面的数大于后面的数
for (i = 0, k = 0; i < 9; i++) {
if (e.f[i / 3][i % 3] == 0)
continue;
for (j = 0; j < i; j++) {
if (e.f[j / 3][j % 3] == 0)
continue;
if (e.f[j / 3][j % 3] > e.f[i / 3][i % 3])
k++;
}
}
// 求逆序数
if (k & 1)
printf("unsolvable\n");
else
AStar(e);
}
return 0;
}
有时候用一个庞大的队列来处理状态超级多搜索问题，内存会有点紧张，于是，为了更好的处理这种问题，又由A*的启发式特性，IDA*算法才横空出世。