| UVA - 11212
Editing a Book
Description 
|
uDebug思路：
既然做到这道题了，就详细的写写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<cstdio> #include<cstring> using namespace std; const int N=10; int n,cas,a[N]; int query(){ int cnt=0; for(int i=1;i<n;i++) if(a[i-1]+1!=a[i]) cnt++; if(cnt>0) cnt++; return cnt; } bool success(){ for(int i=1;i<n;i++) if(a[i-1]+1!=a[i]) return 0; return 1; } void create(int start,int len,int k){//将a~b范围内的数移动到c的后面,也就是[a,b]与(b,c]互换 int olda[N]; memcpy(olda,a,sizeof a); int i=0; for(int z=0;z<k;z++){ if(z>=start&&z<start+len){z+=len-1;continue;} a[i++]=olda[z]; } for(int z=0;z<len;z++) a[i++]=olda[start+z]; for(int z=k;z<n;z++){ if(z>=start&&z<start+len){z+=len-1;continue;} a[i++]=olda[z]; } } bool dfs(int d,int maxd){ int h=query(); if(3*d+h>3*maxd) return 0; if(success()) return 1; int tmp[N]; memcpy(tmp,a,sizeof a); for(int i=0;i<n;i++){ for(int j=i+1;j<=n;j++){ for(int k=0;k<=n;k++){ if(k>=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<n;i++) scanf("%d",a+i); int ans=solve(); printf("Case %d: %d\n",++cas,ans); } return 0; }