http://acm.hdu.edu.cn/showproblem.php?pid=1043hdu的八數(shù)碼數(shù)據(jù)比較的大，一般的廣搜會(huì)超時(shí)，pku的似乎普通BFS就能搞定
所以在查了一些資料后知道要用A*算法
此題比較特殊，不用輸出最短路徑，只要輸出可以達(dá)到的路徑就好
A*算法好像無法得到最優(yōu)解（我現(xiàn)在想不通怎么A*才能深度最淺）
正好使用這道題目
A*就有個(gè)估價(jià)函數(shù)，所得的值最優(yōu)的放在隊(duì)列前 先搜索
我的估價(jià)函數(shù)很簡單
就是各點(diǎn)到目標(biāo)狀態(tài)的最小移動(dòng)距離（然后是理想狀態(tài)的）
下圖數(shù)組a就是3*3的并成一列，我把x處理成9
int mindis(char *a)
{
int sum=0,i,k;
for(i=0;a[i];i++)
{
k = abs(a[i]-'0'-i-1);
sum += k/3 + k%3;
}
return sum;
}
我寫了個(gè)堆了模擬優(yōu)先隊(duì)列。。
還有hash，可以寫個(gè)應(yīng)為只有9！個(gè)狀態(tài)，可以寫個(gè)hash函數(shù)來處理hash沖突
對于這樣的全排列數(shù)據(jù)，還有一個(gè)hash方法，如下
int ku[] = {1,1,2,6,24,120,720,5040,40320};
int caldis(char *a)
{
int sum = 0,cnt;
for(int i=0;a[i];i++)
{
cnt = 0;
for(int j=0;j<i;j++)
{
if(a[j]>a[i])
cnt ++;
}
sum += cnt*ku[i];
}
return sum;
}
接下去就是用一般的bfs方法來解決了
posted on 2009-02-27 20:58
shǎ崽 閱讀(1952)
評論(3) 編輯 收藏 引用