随笔-72  评论-126  文章-0  trackbacks-0
http://acm.hdu.edu.cn/showproblem.php?pid=1043

hdu的八数码数据比较的大,一般的广搜会超时,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ǎ崽 阅读(1733) 评论(3)  编辑 收藏 引用

评论:
# re: 八数码的A*算法 2009-02-27 21:06 | fdar
顶!  回复  更多评论
  
# re: 八数码的A*算法 2011-05-10 17:51 | fgd
博主能否具体解释下这个 堆了模拟优先队列是怎么一回事 看不懂呵呵  回复  更多评论
  
# re: 八数码的A*算法 2012-04-24 17:18 | acm百科网

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理