博主表示比较懒，说明什么的就直接粘过来啦。
第一个A*搜索，A*是一种启发式搜索，g为已花代价，h为估计的剩余代价，而A*是根据f=g+h作为估价函数进行排列，也就是优先选择可能最优的节点进行扩展。
对于八数码问题，以下几个问题需要知道
1.判断有无解问题：根据逆序数直接判断有无解，对于一个八数码，依次排列之后，每次是将空位和相邻位进行调换，研究后会发现，每次调换，逆序数增幅都为偶数，也就是不改变奇偶性，所以只需要根据初始和目标状态的逆序数正负判断即可。
2.HASH问题：根据的是康托展开，具体证明请找网上资料
3.以及估价函数H：是根据与目标解的曼哈顿距离，也就是每个数字与目标位置的曼哈顿距离之和。
以了以上的基础，便可以通过A*解决八数码问题。
对于这题，实验了下，优先队列第一关键字为f，第二关键字为h，耗时2s+,第一关键字为f，第二关键字为g，耗时1s+，第一关键字为h，第二关键字为g，耗时450ms左右。在搜索过程中，加上判断是否有解，时间变化不大。POJ上0ms
学习了一下A*算法以及了解了一下经典8数码问题。
具体的需要自己学一下的。
嗯，两个优化都很重要，判断有无解（也就是传说中的八数码问题）以及A*算法以及康托展开缺一个都不可以。不得不说确实不得了这题。
待我先学习这3个东西(✪ω✪)。
后面是我写的代码。
#include <cstdio>
#include <queue>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
const int inf = 1e8;
const int MAXN = 4e5;
int n,m;
int temp[10];
char step[4] = {'l','r','d','u'};
int dx[4] = {0,0,1,-1};
int dy[4] = {-1,1,0,0};
int fac[9]= {1,1,2,6,24,120,720,5040,40320}; //康拖展开判重
bool vis[MAXN];
//得到状态
int get_state(int *s)
{
int sum=0;
for(int i=0; i<9; i++)
{
int num=0;
for(int j=i+1; j<9; j++)
if(s[j]<s[i])num++;
sum+=(num*fac[8-i]);
}
return sum;
}
//得到估价
int get_h(int *s)
{
int ans = 0;
for(int i = 0 ;i < 3 ; ++i)
for(int j = 0 ; j < 3 ; ++j)
{
ans+=abs(i - (s[i*3+j] - 1) / 3)+abs(j - (s[i*3+j] - 1) % 3);
}
return ans;
}
struct node
{
int num[9];//8数码
int state;//状态
int pos;//0 x的位置
string step;//路径
int g,h;//g表示已经花费的代价，h是估计剩余要花的代价 很明显这东西也就是这种顺序好的才能用上啊
//inf f; f = g+h;表示总估价 按照从小到大排序。
bool operator < (const node &a)const
{
return h!=a.h ? h>a.h : g>a.g;
}
};
//判断是否有解
bool isok(int *s)
{
int ans = 0;
for(int i=0; i<9; i++)
{
for(int j=i+1; j<9; j++)if(s[i]&&s[j])
{
if(s[j]<s[i])ans++;
}
}
return !(ans&1);
}
void bfs(node x)
{
memset(vis,0,sizeof(vis));
priority_queue<node>q;
q.push(x);
vis[x.state] = 1;
while(!q.empty())
{
node u = q.top();
q.pop();
if(u.state == 46233)
{
cout<<u.step<<endl;
return ;
}
//4种交换
int x = u.pos/3;
int y = u.pos%3;
for(int i = 0 ; i < 4; ++i)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < 3 && ny >= 0 && ny < 3)
{
node v = u;
swap(v.num[u.pos],v.num[nx*3+ny]);
v.state = get_state(v.num);
if(!vis[v.state])
{
v.pos = nx*3+ny;
v.step = u.step + step[i];
v.g++;
v.h = get_h(v.num);
vis[v.state] = 1;
q.push(v);
}
}
}
}
}
int main()
{
node u;
char s[2];
while(~scanf("%s",s))
{
if(s[0] == 'x')
{
u.num[0] = 0;
u.pos = 0;
}
else u.num[0] = s[0] - '0' ;
for(int i = 1 ; i < 9; ++i)
{
scanf("%s",s);
if(s[0] == 'x')
{
u.num[i] = 0;
u.pos = i;
}
else u.num[i] = s[0] - '0' ;
}
//判断有无解
if(!isok(u.num))puts("unsolvable");
else //否则就直接搜索
{
u.state = get_state(u.num);
u.g = 0;
u.h = get_h(u.num);
bfs(u);
}
}
}