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ǎ崽 阅读(1898)
评论(3) 编辑 收藏 引用