• LOGOUT

Time Limit: 10000MS

64bit IO Format: %lld & %llu

  

Description

 

思路：

      既然做到这道题了，就详细的写写IDA*的精髓。方便自己，也方便别人。

     做这道题的时候首先看了一下刘汝佳老师的分析(详见紫书P208)，需要利用IDA*算法进行分析，之后上网查了一下关于IDA*算法的介绍，大体意思就是：首先将初始状态结点的H值设为阈值maxH，然后进行深度优先搜索，搜索过程中忽略所有H值大于maxH的结点；如果没有找到解，则加大阈值maxH，再重复上述搜索，直到找到一个解。

关于这IDA*的减枝策略，每遍历一个深度的时候，进行判断：

当前局面的估价函数值 + 当前深度 > 预定义最大搜索深度 

的时候进行减枝。

就能这道题而言，假如我们定义一个数字是不是位置正确：这个数 x 是否 等于 这个数 后面的 数 y - 1，也就是

x =? y - 1，如果等于，说明这个数位置正确，如果不等于，说明这个数位置错误，位于最后一个位置的数的时候，判断他是不是等于n，比如：4,5,6,1,2,3 这个序列存在2个不正确位置数，分别是6（后面是1）和3（3不等于6）。

下面进行这道题的减枝的分析（也叫做启发函数），当你改变一个区间的位置，你会改变3个数的位置的正确性

比如 1,2,3,4,5,6.序列，你把2,3移动到6后面，那么1的后面变成了5, 而 6的后面编程了2,而3的后面变成 空了，所以每次移动一个区间，最多可以改变3个数的正确性，也就是说，对于这道题

如果遍历到了一个深度， （还能遍历的深度 - 当前深度） *３　< 不正确数字的个数，那么就没有必要继续遍历了，因为往后你就是全把这些数字该对了也无法达到理想状态。

知道这个之后时间复杂度的问题就得到解决了，下面我们只需要每次枚举该步的所有移动就可以了。

移动的话，实际就是2个相邻区间的交换，比如A B C D（字母代表区间），将A移动到C后面，也可以看成A 和（BC）互换，所以实质就是相邻区间的互换。

具体的话大家独立思考一下，再看代码吧。

AC代码：

 

#include
     
      #include
      
       using namespace std;const int N=10;int n,cas,a[N];int query(){    int cnt=0;    for(int i=1;i
       
        0) cnt++;    return cnt;}bool success(){    for(int i=1;i
        
         =start&&z
         
          =start&&z
          
           3*maxd) return 0; if(success()) return 1; int tmp[N]; memcpy(tmp,a,sizeof a); for(int i=0;i
           
            =i&&k<=j){k=j;continue;} create(i,j-i,k);//把k到i范围内的数组移动到j的后面 if(dfs(d+1,maxd)) return 1; memcpy(a,tmp,sizeof a); } } } return 0;}int solve(){ if(success()) return 0; for(int k=1;k<5;k++) if(dfs(0,k)) return k; return 5;}int main(){ while(scanf("%d",&n)==1&&n){ for(int i=0;i