一、题目
Description
The 15-puzzle has beenaround for over 100 years; even if you don't know it by that
name, you've seenit. It is constructed with 15 sliding tiles, each with a number from 1 to 15 onit, and all packed into a 4 by 4 frame with one tile missing. Let's call themissing tile 'x'; the object of the puzzle is to arrange the tiles so that theyare ordered
as:
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 withwhich it shares an edge. As an example, the following sequence of moves solvesa slightly scrambled puzzle:
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 isswapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd',for right, left, up, and down, respectively.
Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous fordistributing an unsolvable version of the puzzle, and
frustrating many people. In fact, all you have to do to make a regular puzzleinto 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-known8-puzzle, composed of tiles on a three by three
arrangement.
Input
You will receive adescription of a configuration of the 8 puzzle. The description is
just a listof the tiles in their initial positions, with the rows listed from top tobottom, and the tiles listed from left to right within a row, where the tilesare 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 tostandard output either the word ``unsolvable'', if the puzzle has
no solution,or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' thatdescribes a series of moves that produce a solution. The string should includeno spaces and start at the beginning of the line.
Sample Input
2 3
4 1 5
x 7 6 8
Sample Output
ullddrurdllurdruldr
二、分析
题目的意思很明了，我们的做法也很明了，就是搜。因为时间的限制，裸搜会超时，所以在这里用了4种基于宽搜的解决策略。
DBFS（双向搜索），把状态集合降到普搜的平方根号级别。
A*（启发式），有目的地逼近最优解
IDA*（迭代加深+启发式），时间换空间，有目的地逼近最优解
BeFS(best fit search,贪心搜索)，有目的地逼近解，不一定是最优
三、实现
1．节点的设置
所有的搜索树节点都应该包含当前的局面
Charmap[3][3]
在题目要求的情况下，保存到当前节点走过的步数
Intstep或int g（本题不要求输出步数也不要求最优解，可以不用）
为了输出解，保存产生该节点的节点
Intfrom
为了输出解比较方便，保存从上一个节点到此节点走的步子
Charmove
2．判重
遍历已产生节点集合时间效率太低，可以考虑HASH或者二叉查找树，这里使用的是HASH。
第一种，就是一开始自己写的，根据HASH的基本思想，要使关键字的分布尽量松散，所以采用对每个格子加权平方求和取模的方法。冲突用拉链解决。这种方法对15数码依然有效。
第二种，在网上看到的，因为8数码的状态集合只有362880的元素。所以可以做完全散列，大幅提升速度。但是对15数码或更多无效。因为15数码大概有87G+的状态。具体的操作就是把0看做9，把当前局面按行优先写成一维的。然后看每一个数前面有多少比他大的数记为n[i],散列值就是sum(n[i]*fac[i])，
fac[i]为i!，预处理出来。
3．节点扩展
像一般的地图遍历问题一样，按照4个方向向量来生成之后的节点。
4．解的输出
在生成过程中保存了每一步的走法，可以在找到解时第归输出。对于双向搜索来说，输出解是一个问题。首先要判断当前是在哪一个方向，然后对于正向先第归父节点，后输出当前节点，反向反之。
5．启发函数的构造
当然使用最经典的Manhattan距离（h1），对于启发函数h有规定小于h*(实际代价)，并且在满足这个条件的情况下，h越大越好。相比另一个启发函数：不在位的数字个数(h2)。总是有h1>=h2的。因为一个数字不在位的话，他的离家Manhattan距离一定是>=1的。所以h1的启发能力更强。通过对样例的测试，发现h2产生的节点大概是h1的9倍。
当然还有其他的启发函数，构造相当复杂，可以搜索其他资料。因为在上面构造中，把空格和其他数字是放在同一种地位的，都看成是某一个数字。但根据人玩这个游戏的分析，空格是可以主动移动的（或者说空格周围的四个数字是可以主动移动的），所以每一个数字对解的产生的功效显然是不一样的。
四．比较
下面是四个程序的基本说明：
AC1：
用的双向BFS
判重用的自己随便做的HASH
AC2:
A*
启发函数用Manhattan距离
判重用的是全排列HASH
AC3:
IDA*
启发函数同AC2
判重的HASH同AC2
判重的时候不是将appeared置简单的bool值，而是置上当前的maxf
这样保证了当前搜索不出现重复节点，也节省了把appeared全部初始化的时间
（不加判重大概要产生30+W个节点，很恐怖）
AC4:
BeFS(best fit search)
就是在A*的实现过程中把估价函数
f=g+h改为f=h。
这样可能出的不是最优解，但是在一定有解的情况下往往能更快出解
其他部分同AC2完全一样，
对样例的测试中显示出了惊人的效果
下面产生的节点数是测样例的节点数，后面是POJ上的数据
AC1(DBFS)
产生了1061
个节点
1140K16MS G++ 4522B
AC2(A*)
产生了 832
个节点
1456K 0MS G++ 3044B
AC3(IDA*)
产生了884
个节点
1108K 32MS G++ 2253B
AC4(BeFS)
产生了67
个节点
708K 0MS G++ 3362B
（对于A*，采用不在位置上的元素个数启发，产生了7506个节点。。只能说比裸搜要好点吧，对解决这个题没啥意义）
1．从对比上来说前三种算法相对普通BFS都是高效的。
IDA*
比A*
慢的地方在于重复计算，从打印的节点个数来看，
IDA*
并没有比A*产生过多的节点，因为ID和BFS的渐进复杂度是一样的。
这个题在POJ上提交的时候IDA*的内存比A*的内存减小得不明显。
因为主要的内存用在判重数组上（有1M+）。
2．以上的代码长度跟真实的代码长度是有出入的，因为里面有很多注释嘛，大家知道中文字是（2B）的，所以看起来会比较长。。。只要拍一下就熟悉了。
3．在实现过程中用到的队列和堆，我是自己写的，这样可以有选择性地使用部分特性，不用完全实现。
4．因为本题比较特殊，BeFS是最佳解决策略，但是对于ACM中大多数要求最优解的题，还是应该用前三种来写。
5．仿照BeFS对A*的改造思想，尝试了一下对IDA*的改造，但是失败。分析一下原因。IDA*是在一个限制的maxf之下，进行搜索，当f=g+h的时候，是逼近最优解的，而f=h的时候，就会和深搜差不多，由于最后的f值肯定是为0的，可能会在较小的maxf下出解。这个解有可能是绕行了很多步的。在对样例的测试中，产生了大概10行的移动步子。。。虽然用自己写的SPJ可以检验是正确的，但是可以想象，当数据的最优解就得好几行的时候，这个东西输出的解可能会很长很长。。
代码：
#include <iostream>
#include <string.h>
using namespace std;
//节点总数
#define MAXQ 40000
//HASH表长度
#define MAXT 12289
//X坐标为从上到下，Y坐标为从左到右
const char movename[2][4]={{'u','d','l','r'}, //正向移动的名字
{'d','u','r','l'}}; //反向移动的名字
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
typedef struct hnode_type{
char q; //记录哪个队列产生
int pos; //记录在该队列中的位置
char map[3][3]; //记录局面
hnode_type *next; //下一个节点
}HNODE; //HASH表节点类型
typedef struct node_type{
char map[3][3]; //当前局面
int step; //所用步数
char move; //从上一个局面到当前所走的方向
int from; //上一个局面的编号
}NODE; //队列节点类型
//q[0]正向队列，q[1]反向队列
NODE q[2][MAXQ];
int head[2],tail[2];
HNODE *table[MAXT]; //拉链法HASH
HNODE space[MAXQ],*spacehead; //HASH空间的分配，new 太慢
int sqr(int n){
return n*n;
}
int hash(char map[3][3]){//这个HASH是自己随便写的，主要思想是按照格子加权平方和取模
//实际使用的时候可以换成一个完全散列的HASH会更快
//如那个求逆序对的，对所有全排列问题适用的HASH
int t=0,i,j;
for (i=0;i<3;i++)
for (j=0;j<3;j++)t+=sqr(map[i][j]*(1<<(i+j)));
return t%MAXT;
}
//将节点加入HASH表中
void putin(char map[3][3],char q,int pos){ //局面，队列号，队中位置
int key,i,j;
HNODE *hn;
key=hash(map);
hn=spacehead++;
for (i=0;i<3;i++)for (j=0;j<3;j++)hn->map[i][j]=map[i][j];
hn->q=q;
hn->pos=pos;
hn->next=table[key]; //头插法插入节点
table[key]=hn;
}
//节点判等
bool isequal(char m1[3][3],char m2[3][3]){
int i,j;
for (i=0;i<3;i++)
for (j=0;j<3;j++)
if (m1[i][j]!=m2[i][j])return false;
return true;
}
//判断节点是否在HASH表中
bool isin(char map[3][3]){
int key;
HNODE *p;
key=hash(map);
p=table[key];
while (p){
if (isequal(p->map,map))return true;
p=p->next;
}
return false;
}
//判断节点所在队列
int getq(char map[3][3]){
int key;
HNODE *p;
key=hash(map);
p=table[key];
while (p){
if (isequal(p->map,map))return p->q;
p=p->next;
}
//这里不可到达！！
cout<<"impossible!!!"<<endl;
}
//判断节点所在位置
int getpos(char map[3][3]){
int key;
HNODE *p;
key=hash(map);
p=table[key];
while (p){
if (isequal(p->map,map))return p->pos;
p=p->next;
}
//这里不可到达！！
cout<<"impossible!!!"<<endl;
}
void init(){
int i,j;
char ch;
NODE curnode;
spacehead=space; //HASH空间头地址
memset(&curnode,0,sizeof(NODE));
for (i=0;i<3;i++)for (j=0;j<3;j++){
cin>>ch;
if (ch=='x')curnode.map[i][j]=0;
else curnode.map[i][j]=ch-'0';
}
q[0][1]=curnode;head[0]=1;tail[0]=2; //放置正向队列节点
putin(curnode.map,0,1);
for (i=0;i<3;i++)for (j=0;j<3;j++)curnode.map[i][j]=i*3+j+1;
curnode.map[2][2]=0;
q[1][1]=curnode;head[1]=1;tail[1]=2; //放置逆向队列节点
putin(curnode.map,1,1);
}
void output(int curq,int pos){
if (curq==0){
if (q[curq][pos].from!=0)output(curq,q[curq][pos].from);
if (q[curq][pos].move){
cout<<q[curq][pos].move;
}
// 这里注释的两行是打印出每步走了之后的局面
// 题目仅要求了走的步子，就不用了
// cout<<curq<<' '<<pos<<' '<<endl;
// dbg1(q[curq][pos].map);
}else{
// cout<<curq<<' '<<pos<<' '<<endl;
// dbg1(q[curq][pos].map);
if (q[curq][pos].move){
cout<<q[curq][pos].move;
}
if (q[curq][pos].from!=0)output(curq,q[curq][pos].from);
}
}
int main(){
int i,x,y,xx,yy,curq;
NODE curnode,newnode;
init();
if (isequal(q[0][1].map,q[1][1].map))return 0;
while (head[0]<tail[0]&&head[1]<tail[1]){ //队列非空
if (tail[1]-head[1]<tail[0]-head[0])curq=1; //选取节点较小的一边扩展
else curq=0;
curnode=q[curq][head[curq]]; //取头节点
curnode.step++;
curnode.from=head[curq];
head[curq]++;
for (xx=0;xx<3;xx++)for (yy=0;yy<3;yy++)
if (!curnode.map[xx][yy]){
x=xx;y=yy;
break;
}//找到空格
for (i=0;i<4;i++){
newnode=curnode;
xx=x+dx[i];yy=y+dy[i]; //新的走法
if (xx>=0&&xx<3&&yy>=0&&yy<3){
swap(newnode.map[x][y],newnode.map[xx][yy]);
if (!isin(newnode.map)){ //新节点
newnode.move=movename[curq][i];
putin(newnode.map,curq,tail[curq]);
q[curq][tail[curq]++]=newnode;
}else{
if (getq(newnode.map)==1-curq){ //已达到目标
newnode.move=movename[curq][i]; //这一步很重要，开始没写这个WA了两个小时
if (curq==0){ //第归打印
output(0,newnode.from);
cout<<newnode.move;
output(1,getpos(newnode.map));
}
else{
output(0,getpos(newnode.map));
cout<<newnode.move;
output(1,newnode.from);
}
return 0;
}
//否则新节点在自己这一边，丢弃，不处理
}
}
}
}
cout<<"unsolvable";
return 0;
}