http://acm.hdu.edu.cn/showproblem.php?pid=1043hdu的八數碼數據比較的大，一般的廣搜會超時，pku的似乎普通BFS就能搞定
所以在查了一些資料后知道要用A*算法
此題比較特殊，不用輸出最短路徑，只要輸出可以達到的路徑就好
A*算法好像無法得到最優解（我現在想不通怎么A*才能深度最淺）
正好使用這道題目
A*就有個估價函數，所得的值最優的放在隊列前 先搜索
我的估價函數很簡單
就是各點到目標狀態的最小移動距離（然后是理想狀態的）
下圖數組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;
}
我寫了個堆了模擬優先隊列。。
還有hash，可以寫個應為只有9！個狀態，可以寫個hash函數來處理hash沖突
對于這樣的全排列數據，還有一個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ǎ崽 閱讀(1947)
評論(3) 編輯 收藏 引用