在学习八数码A*搜索问题的时候须要知道下面几个点：
Hash：利用康托展开进行hash
康托展开主要就是依据一个序列求这个序列是第几大的序列。
A*搜索：这里的启示函数就用两点之间的曼哈顿距离进行计算就能够。
减枝：在八数码里。随意交换一个空行和一个位置的数字，这个八数码的逆序数是不变的，这样就能够依据眼下状态推断是否可达终点状态了。
第一次做这个题用的map进行哈希，结果果断超时。之后又写了LRJ书上的hash方法也超时了，最后仅仅能用康托展开了
具体请參考：【八数码的八重境地】 http://www.cnblogs.com/goodness/archive/2010/05/04/1727141.html
/*
康托展开
A* 算法
八数码逆序数性质
*/
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 370015;
//322560
struct State{
int mat[3][3];
int h,g,cvalue;
int posx,posy;
friend bool operator < (State p,State q){
if(p.h != q.h)
return p.h > q.h;
else
return p.g > q.g;
}
}start;
int vis[maxn],fa[maxn],cnt;
//-------------------init----------------------------------
void init(){
memset(vis,-1,sizeof(vis));
memset(fa,-1,sizeof(fa));
cnt = 0;
}
bool isok(State &state){
int temp[9];
for(int i = 0,k = 0; i < 3; i ++)
for(int j = 0; j < 3; j++,k++)
temp[k] = state.mat[i][j];
int ret = 0;
for(int i = 0; i < 9; i++)
for(int j = 0; j < i; j++){
if(temp[i] && temp[j] && temp[j] > temp[i])
ret ++;
}
return (ret & 1) ? 0 : 1;
}
//---------------------------------------------------------
const int Hash[] = {1,1,2,6,24,120,720,5040,40320};
int Cantor(State &stemp){
int temp[9];
for(int i = 0,k = 0; i < 3; i++)
for(int j = 0; j < 3; j++, k++)
temp[k] = stemp.mat[i][j];
int ret = 0;
for(int i = 0; i < 9; i++){
int val = 0;
for(int j = 0; j < i; j++)
if(temp[j] > temp[i]) val ++;
ret += Hash[i] * val;
}
return ret;
}
//----------------------------------------------------------
int get_h(State &temp){
int ret = 0;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++){
ret +=
abs(i - (temp.mat[i][j] - 1)/3) + abs(j - (temp.mat[i][j] - 1) % 3);
}
return ret;
}
//----------------------------------------------------------
//ulldrdrulldrruldlurrd
const char cdir[] = "dlru";
const int dir[4][2] = {{1,0},{0,-1},{0,1},{-1,0}}; //d l r u
void dfs_print(int u){
if(vis[u] < 0)
return;
dfs_print(fa[u]);
printf("%c",cdir[vis[u]]);
}
bool bfs(){
priority_queue<State>q;
start.cvalue = Cantor(start);
start.h = get_h(start);
start.g = 0;
q.push(start);
vis[start.cvalue] = - 2;
State temp;
while(!q.empty()){
State now = q.top(); q.pop();
if(now.cvalue == 322560){
dfs_print(now.cvalue);
puts("");
return true;
}
for(int i = 0; i < 4; i++){
temp = now;
int x = now.posx + dir[i][0];
int y = now.posy + dir[i][1];
temp.posx = x;
temp.posy = y;
if(x >= 0 && x < 3 && y >= 0 && y < 3){
swap(temp.mat[x][y],temp.mat[now.posx][now.posy]);
int cvalue = Cantor(temp);
if(vis[cvalue] == -1 && isok(temp)){
vis[cvalue] = i;
fa[cvalue] = now.cvalue;
temp.h = get_h(temp);
temp.g = now.g + 1;
temp.cvalue = cvalue;
q.push(temp);
if(temp.cvalue == 322560){
dfs_print(cvalue);
puts("");
return true;
}
cnt ++;
}
}
}
}
return false;
}
int main(){
char _in[10][2];
while(scanf("%s",_in[0]) != EOF){
init();
for(int i = 1; i < 9; i++)
scanf("%s",_in[i]);
for(int k = 0,i = 0; i < 3; i++)
for(int j = 0; j < 3; j++,k ++){
if(_in[k][0] == 'x'){
_in[k][0] = '0';
start.posx = i;
start.posy = j;
}
start.mat[i][j] = _in[k][0] - '0';
}
if(!bfs())
printf("unsolvable
");
}
return 0;
}
/*
1
2
6
24
120
720
5040
40320
*/