據(jù)說(shuō)不作此題人生不完整。好吧。很久以前就做過(guò)了，寫過(guò)BFS，A*，和雙搜。A*用了200+ms,汗，BFS都比他快。正好這幾天在看搜索估價(jià)函數(shù)之類的東西，就把這道經(jīng)典題拿出來(lái)，再做一遍，突然發(fā)現(xiàn)，估價(jià)函數(shù)+迭代加深搜索就是IDA*算法，好吧。以前傻傻看黑書的時(shí)候，理解不了A* ，覺得巨麻煩（現(xiàn)在也覺得挺麻煩），現(xiàn)在寫起來(lái)IDA*，覺得還挺簡(jiǎn)潔，并且比較通用，而且這玩意又好寫又比較通用，就詳細(xì)研究了一下。看了別人的一個(gè)IDA*的算法，覺得寫的很簡(jiǎn)潔很工整，就參詳了一下，然后改造成了自己的，A掉了1077題。樓教主寫的那個(gè)百度之星的版本的Allyes.com，還沒有詳細(xì)看，覺得有點(diǎn)復(fù)雜。有機(jī)會(huì)要好好研究下。
我感覺IDA*的主要的價(jià)值在于，在深度搜索的時(shí)候，可以把問(wèn)題的條件放寬，只要找到一個(gè)接近并且小于實(shí)際解的估價(jià)函數(shù)，就可以非?？斓牡玫浇饬?。而尋求估價(jià)函數(shù)的過(guò)程，非常的有意思，可以轉(zhuǎn)換成各種經(jīng)典問(wèn)題。下面是代碼，我覺得還算工整吧。
#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) //如果啟發(fā)函數(shù)比較好(很靠近結(jié)果并且小于結(jié)果)，基本上很少次迭代就可以出結(jié)果。時(shí)間浪費(fèi)在迭代次數(shù)上
{
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;
}