注册 登录  
 加关注

网易博客网站关停、迁移的公告:

将从2018年11月30日00:00起正式停止网易博客运营
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj 2286 The Rotation Game 迭代加深  

2011-04-12 11:37:22|  分类: 搜索 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://poj.org/problem?id=2286
今天又做了个迭代加深,不错继续努力!!
     移动八根线中任一根,移法为头的数移到线的尾,其它的数向头进一位。求最少要移多少次才能使中间的八个数相等。
本题若用广搜,空间需求量非常大,空间不足。深搜的话,深度很难控制,容易陷入死循环。在这个时候就要用到迭代加深的深搜方法。

所谓迭代加深,就是在深度无上限的情况下,先预估一个深度(尽量小)进行搜索,如果没有找到解,再逐步放大深度搜索。这种方法虽然会导致重复的遍历 某些结点,但是由于搜索的复杂度是呈指数级别增加的,所以对于下一层搜索,前面的工作可以忽略不计,因而不会导致时间上的亏空。

这种方法,可以算作是DFS和BFS的结合。适合大树而可行解不是很深的题目。

#include<stdio.h>
int ff[8][7]={0,2,6,11,15,20,22,
            1,3,8,12,17,21,23,
            10,9,8,7,6,5,4,
            19,18,17,16,15,14,13,
            23,21,17,12,8,3,1,
            22,20,15,11,6,2,0,
            13,14,15,16,17,18,19,
            4,5,6,7,8,9,10};
int aim[8]={6,7,8,11,12,15,16,17};
int rev[8]={5,4,7,6,1,0,3,2};
int map[25],ans[20],DEPTH;
int least(){
    int i,count[3]={0,0,0},ans=0;
    for(i=0;i<8;++i)++count[map[aim[i]]-1];
    for(i=0;i<3;++i)if(ans<count[i])ans=count[i];
    return 8-ans;
}
int change(int dir){
    int i,temp=map[ff[dir][0]];
    for(i=0;i<6;++i)
        map[ff[dir][i]]=map[ff[dir][i+1]];
    map[ff[dir][6]]=temp;
}
int dfs(int depth){
    int i,temp;
    for(i=0;i<8;++i){
        change(i);
        if((temp=least())==0){
            ans[depth]=i;
            return depth+1;
        }
        if(depth+temp<DEPTH){
            ans[depth]=i;
            if(dfs(depth+1))return depth+1;
        }
        change(rev[i]);
    }
    return 0;
}
int main(){
    int i;
    while(scanf("%d",&map[0]),map[0]){
        for(i=1;i<24;++i)scanf("%d",&map[i]);
        if(least()==0){
            puts("No moves needed");
            printf("%d\n",map[6]);
            continue;
        }
        for(DEPTH=1;!dfs(0);++DEPTH);
        for(i=0;i<DEPTH;++i)printf("%c",ans[i]+'A');printf("\n");
        printf("%d\n",map[6]);
    }
    return 0;
}
  评论这张
 
阅读(356)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018