• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆-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ǎ崽 閱讀(1941) 評論(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百科網
            久久66热人妻偷产精品9| 久久国产亚洲高清观看| 少妇被又大又粗又爽毛片久久黑人 | 久久综合中文字幕| 婷婷久久精品国产| 久久久久人妻一区精品性色av| 国产成人久久久精品二区三区 | 久久亚洲日韩精品一区二区三区| 欧美激情精品久久久久| 久久SE精品一区二区| 久久青青草原国产精品免费| 久久久久久久波多野结衣高潮| 久久99热狠狠色精品一区| 亚洲综合久久夜AV | 久久亚洲国产精品一区二区| A级毛片无码久久精品免费| 久久99精品久久久久久不卡 | 国产高潮国产高潮久久久91| 国内精品久久久久影院日本 | 久久精品这里只有精99品| www.久久99| 国产产无码乱码精品久久鸭| 欧美亚洲国产精品久久高清| 日韩亚洲国产综合久久久| 一本久久久久久久| 久久99国产精品久久久| 久久免费的精品国产V∧| 国产69精品久久久久APP下载| 久久综合五月丁香久久激情| 国产午夜精品理论片久久| 精品久久久久中文字| 国产99久久九九精品无码| AA级片免费看视频久久| 日本精品久久久中文字幕| 伊人色综合久久天天| 香蕉久久一区二区不卡无毒影院| 国产一区二区精品久久 | 国产免费久久精品99re丫y| 久久强奷乱码老熟女网站| 久久人人爽人人爽人人片AV高清| 久久久久久久免费视频|