设为首页 加入收藏

TOP

POJ 2286 The Rotation Game 迭代搜索深度 + A* == IDA*
2015-07-24 05:46:02 来源: 作者: 【大 中 小】 浏览:7次
Tags：POJ 2286 The Rotation Game 搜索 深度 IDA

感觉这种算法还是比较局限的吧，重复搜索是一个不好的地方，而且需要高效的估值函数来进行强剪枝，这点比较困难。

迭代搜索深度是一个比较炫酷的搜索方式，不过有点拿时间换空间的感觉。

首先迭代深度比较搓的写法是，首先设置一个阀值MaxH，初始为最小值。

当在搜索深度Depth <= MaxH时找到解则此时为最优解，否则MaxH++,继续深搜。

另外一种比较吊的写法是二分搜索深度，若搜到则减小阀值，否则增大阀值。

总之，迭代深度搜索就是通过改变深搜的深度来寻找最优解，这样做的好处是省掉了BFS中状态标记所有的空间花销。

对于这种算法掌握的并不透彻，就不多说了。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-8) #define LL long long #define ULL unsigned long long #define _LL __int64 #define _INF 0x3f3f3f3f #define Mod 6000007 using namespace std; int num[25]; int order[8][7] ={ { 1, 3, 7,12,16,21,23}, { 2, 4, 9,13,18,22,24}, {11,10, 9, 8, 7, 6, 5}, {20,19,18,17,16,15,14}, {24,22,18,13, 9, 4, 2}, {23,21,16,12, 7, 3, 1}, {14,15,16,17,18,19,20}, { 5, 6, 7, 8, 9,10,11} }; int MaxH; int Cal(int *num) { int mark[] = {0,0,0,0,0}; for(int i = 7;i <= 9; ++i) mark[num[i]]++; for(int i = 12;i <= 13; ++i) mark[num[i]]++; for(int i = 16;i <= 18; ++i) mark[num[i]]++; return min(8-mark[1],min(8-mark[2],8-mark[3])); } int sta[1000]; int Top; int anw; bool dfs(int *num,int ans) { int temp = Cal(num); if(temp == 0) { anw = num[8]; return true; } if(temp + ans > MaxH) return false; int tn[25]; int i,j; for(i = 0;i < 8; ++i) { sta[Top++] = i; for(j = 1;j <= 24; ++j) tn[j] = num[j]; for(j = 0;j < 7; ++j) tn[order[i][j]] = num[order[i][(j+1)%7]]; if(dfs(tn,ans+1)) return true; Top--; } return false; } int main() { int i; while(scanf("%d",&num[1]) && num[1]) { for(i = 2;i <= 24; ++i) scanf("%d",&num[i]); if(Cal(num) == 0) { printf("No moves needed\n"); printf("%d\n",num[7]); continue; } MaxH = 1; Top = 0; while(dfs(num,0) == false) { MaxH++; } for(i = 0;i < Top; ++i) printf("%c",sta[i]+'A'); printf("\n%d\n",anw); } return 0; }

【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：ACM：归并排序，以及利用归并排序.. 下一篇：UVA 766 - Sum of powers(伯努利..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: