据说不作此题人生不完整。好吧。很久以前就做过了，写过BFS，A*，和双搜。A*用了200+ms,汗，BFS都比他快。正好这几天在看搜索估价函数之类的东西，就把这道经典题拿出来，再做一遍，突然发现，估价函数+迭代加深搜索就是IDA*算法，好吧。以前傻傻看黑书的时候，理解不了A* ，觉得巨麻烦（现在也觉得挺麻烦），现在写起来IDA*，觉得还挺简洁，并且比较通用，而且这玩意又好写又比较通用，就详细研究了一下。看了别人的一个IDA*的算法，觉得写的很简洁很工整，就参详了一下，然后改造成了自己的，A掉了1077题。楼教主写的那个百度之星的版本的Allyes.com，还没有详细看，觉得有点复杂。有机会要好好研究下。
我感觉IDA*的主要的价值在于，在深度搜索的时候，可以把问题的条件放宽，只要找到一个接近并且小于实际解的估价函数，就可以非常快的得到解了。而寻求估价函数的过程，非常的有意思，可以转换成各种经典问题。下面是代码，我觉得还算工整吧。
#include <cstdio>
#include <cstring>
char board[3][3];
int dest_goal[9][2] = {{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2}};
int val[4][2] = {{0,1},{1,0},{-1,0},{0,-1}}; //r,l,d,u
char op[4] ={'r','d','u','l'};
char solution[100];
int find;
int testdata,low_bound;
int abs(int i)
{
if(i>0) return i; return -i;
}
void swap(char& a,char& b)
{
char c = a; a= b;b = c;
}
int getH()
{
int i,j;
int nRet = 0;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
if(board[i][j] != 'x')
nRet += abs(i - dest_goal[board[i][j] - '1'][0]) + abs(j - dest_goal[board[i][j] - '1'][1] );
}
return nRet;
}
int bound(int x,int y)
{
if(x<0||y<0||x>=3||y>=3) return 0;
return 1;
}
int min(int a,int b)
{
if(a>b) return b; return a;
}
int dfs(int x,int y,int step,int maxstep)
{
if(getH() == 0 || find == 1)
{
find = 1;
return step;
}
if(step + getH() > maxstep)
return step + getH();
int i;
int now_bound = 100000;
for(i=0;i<4;i++)
{
int nx = x + val[i][0];
int ny = y + val[i][1];
if(bound(nx,ny))
{
swap(board[x][y],board[nx][ny]);
solution[step] = op[i];
int next_bound = dfs(nx,ny,step+1,maxstep);
now_bound = min(now_bound,next_bound);
if(find == 1)
return now_bound;
swap(board[x][y],board[nx][ny]);
}
}
return now_bound;
}
int main()
{
freopen("in_1077.txt","r",stdin);
freopen("out.txt","w",stdout);
int i,j,sx,sy;
char c;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
while(scanf("%c",&board[i][j]) && board[i][j] == ' ')
NULL;
if(board[i][j] == 'x')
{
sx = i;
sy = j;
}
}
find = 0;
low_bound = getH();
while(low_bound < 100 && !find) //如果启发函数比较好(很靠近结果并且小于结果)，基本上很少次迭代就可以出结果。时间浪费在迭代次数上
{
low_bound = dfs(sx,sy,0,low_bound);
}
if(find)
{
solution[low_bound] = '\0';
printf("%s\n",solution);
}
else if(find == 0)
printf("unsolvable\n");
return 0;
}