POJ1077，经典的八数码问题，百度到一个地方说是不做这道题目人生是不完整的- -然后我做了三天……貌似还不止三天……
找这道题目完全是为了练A*。
一开始我不知死活的先写了一个限制深度的DFS……结果……无限TLE中- -
然后写了个BFS，网上有说BFS能够AC的，但是我写出来的TLE不解释……代码质量不太好估计……（后来发现其实hash方式影响很大）
于是再写一个双向BFS，华丽的60MS，这道题目算是过了……60MS这个里面用了大量的STL，MAP啥的，看来双向宽搜果然是很暴力的啊……貌似这是这辈子写的第二个双向宽搜，上一个大概- -4年前刚学搜索的时候吧- -
写了这么多都还没有涉及A，回头，写A去了。
一开始用自己写的100多行的一个堆，然后大量STL写了个A，结果TLE了……备受打击啊……ATLE了……
一不做，二不休，干脆把所有的map全部改成了哈希表，900多MS……泪奔……
无限百度各种八数码代码，找到这么个地方
http://www.cnblogs.com/liyongmou/archive/2010/07/19/1780861.html
里面写着，BFS500多MS,A30+，IDA10+MS……感觉很不可思议……
于是乎把代码复制下来在POJ提交了一下……确认了……确实有这么快……泪奔……
于是开始研究那代码……
发现A*里面有个地方利用priority_queue的时候的技巧是错误的，于是找CFY讨论- -又找作者讨论- -最后发现确实有点问题……难道还是得用自己的那个恶心的堆吗……这时候那个网页的作者告诉了我一个冗余的办法……确实很漂亮……很好的解决了那个办法- -
重写不解释，然后发现我那个哈希表也花费了大量的时间，于是更改编码方式，用变进制数（刚学的- -）来搞，搞出来,AC了，不过时间还是有点悲剧，200+MS
然后又用IDA写了一个，话说IDA好东西啊，代码只有A*长度的一半- -速度还一点都不含糊，100+MS……
不过感觉跟30+，10+还是差很多啊，于是各种想办法改，先是发现以一些无关痛痒的地方，最后发现启发函数有点问题，于是改了一下启发函数，瞬间飙到60MS,40MS……还是有点差距……不过……感觉差不多了……不写了……三天了……哥累了……
总结一下收获- -
1、利用冗余法从而可以直接用STL的堆，降低A*的编写复杂度- -
2、启发函数很重要啊很重要啊很重要！
3、IDA*很欢乐啊很欢乐啊很欢乐
4、STL的速度……有时候挺快的，有时候还真挺蛋疼……终于体会到为什么要慎用了……常数是大了点- -
5、看别人代码收获很大啊……
贴下代码吧……把A的贴上……至少用了冗余法……IDA那个……算了……
#include
const int MAXN = 362880 + 100;
using namespace std;
struct CStatus
{
int a[9];
int zero_pos;
};
int Encode(CStatus &sts)
{
int a[9];
for(int i=0; i<9; ++i){
a[i] = 0;
for(int j=i+1; j<9; ++j)
if(sts.a[i] > sts.a[j])
++a[i];
}
int k = 0;
for(int i=0; i<9; ++i){
k = k*(9-i)+a[i];
}
return k;
}
void Decode(int k, CStatus &sts)
{
int a[9];
a[8] = 0;
for(int i=2; i<=9; ++i){
a[9-i] = k % i;
k /= i;
}
for(int i=0; i<9; ++i)
sts.a[i] = 10;
for(int i=0; i<9; ++i){
int nb = 0;
for(int j=0; j<9; ++j){
if(sts.a[j] < i)
nb++;
else if(a[j] + nb == i){
sts.a[j] = i;
break;
}
}
}
for(int i=0; i<9; ++i)
if(sts.a[i] == 0){
sts.zero_pos = i;
return;
}
}
struct CNode{
int key, val;
CNode(int _k, int _v):key(_k), val(_v){}
};
inline bool operator < (CNode const &n1, CNode const &n2)
{
return n1.val > n2.val;
}
CStatus stsStart, stsGoal;
priority_queue
inline int abs(int a)
{
return a >= 0?a:-a;
}
/int CalcH(CStatus &sts)
{
int k = 0;
for(int i=0; i<8; ++i)
k += abs(sts.a[i]/3 - (i+1)/3) + abs(sts.a[i] %3-(i+1)%3);
return k;
}/
int CalcH(CStatus &sts)
{
int k = 0;
for(int i=0; i<9; ++i){
//if(sts.a[i] != i+1)
//k++;
if(sts.a[i] == 0)
continue;
k += abs(sts.a[i]/3 - (i+1)/3) + abs(sts.a[i] %3-(i+1)%3);
}
return k;
}
bool AStar()
{
for(int i=0; i<MAXN; ++i){
f[i] = g[i] = h[i] = -1;
}
h[start] = CalcH(stsStart);
g[start] = 0;
f[start] = g[start] = h[start];
open.push(CNode(start, f[start]));
while(!open.empty()){
CNode now = open.top();
open.pop();
if(now.key == goal)
return true;
if(f[now.key] != now.val)
continue;
CStatus stsNow;
Decode(now.key, stsNow);
int x = stsNow.zero_pos / 3;
int y = stsNow.zero_po
s % 3;
for (int i = 0; i < 4; ++i) {
int xx = x + sx[i], yy = y + sy[i];
if (xx <= 2 && xx >= 0 && yy <= 2 && yy >= 0) {
stsNow.a[x * 3 + y] = stsNow.a[xx * 3 + yy];
stsNow.a[xx * 3 + yy] = 0;
int hash = Encode(stsNow);
//没有出现过，说明不在open表也不在Close表
if (g[hash] == -1) {
g[hash] = g[now.key] + 1;
h[hash] = CalcH(stsNow);
f[hash] = g[hash] + h[hash];
open.push(CNode(hash, f[hash]));
pre[hash] = now.key;
step[hash] = i;
//出现过，说明在open表或者close表，直接更新
} else if (g[hash] > g[now.key] + 1) {
g[hash] = g[now.key] + 1;
f[hash] = g[hash] + h[hash];
open.push(CNode(hash, f[hash]));
pre[hash] = now.key;
step[hash] = i;
}
stsNow.a[xx * 3 + yy] = stsNow.a[x * 3 + y];
stsNow.a[x * 3 + y] = 0;
}
}
}
return false;
}
void print_ans()
{
string ans;
int k = goal;
while(k != start){
ans = step_char[step[k]] + ans;
k = pre[k];
}
printf(“%s\n”, ans.c_str());
}
int main()
{
char s[10];
stsGoal.a[8] = 0;
stsGoal.zero_pos = 8;
for(int i=0; i<8; ++i)
stsGoal.a[i] = i+1;
goal = Encode(stsGoal);
for(int i=0; i<9; ++i){
scanf(“%s”, s);
if(s[0] == ‘x’){
stsStart.zero_pos = i;
stsStart.a[i] = 0;
}else{
stsStart.a[i] = s[0]-‘0’;
}
}
start = Encode(stsStart);
if(AStar()){
print_ans();
}else{
printf(“unsolvable”);
};
return 0;
}