笔记
S:问题的一种状态
h*(S):所求
的最短距离
h(s):S的估价函数
g(s):S之前的代价函数
f(s):s的启发函数
h(s)
有h(s)<=h*(s)
相容
定义:如果h(s)对于任意状态S1,S2都有h(S1)<=h(s2)+C(s1,s2),C(s1,s2)指从状态S1到S2的代价,则有h(s)是相容的。
也就是说,h(s)不能减小得太快。
g(s)
通常用搜索树的深度代表。
f(s)
作为s的启发函数,也就是到达目标的总代价,显然有f(s)=g(s)
+h(s),即已付出的代价加上预估要付出的代价。
==h(s)相容时,f(s)单调递增。==
证明
h(S1)<=h(S2)+C(S1,S2)
h(s1)+g(s1)<=h(S2)+g(S1)+C(S1,S2)
显然有
h(s1)+g(s1)<=h(S2)+g(S2)
即 f(s1)<=f(s2)
You have n equal-length paragraphs numbered 1 to n. Now you want to arrange them in the order
of 1, 2, . . . , n. With the help of a clipboard, you can easily do this: Ctrl-X (cut) and Ctrl-V (paste)
several times. You cannot cut twice before pasting, but you can cut several contiguous paragraphs at
the same time - they’ll be pasted in order.
For example, in order to make {2, 4, 1, 5, 3, 6}, you can cut 1 and paste before 2, then cut 3 and
paste before 4. As another example, one copy and paste is enough for {3, 4, 5, 1, 2}. There are two
ways to do so: cut {3, 4, 5} and paste after {1, 2}, or cut {1, 2} and paste before {3, 4, 5}.
Input
The input consists of at most 20 test cases. Each case begins with a line containing a single integer n
(1 < n < 10), thenumber of paragraphs. The next line contains a permutation of 1, 2, 3, . . . , n. The
last case is followed by a single zero, which should not be processed.
Output
For each test case, print the case number and the minimal number of cut/paste operations.
Sample Input
6
2 4 1 5 3 6
5
3 4 5 1 2
0
Sample Output
Case 1: 2
Case 2: 1
h()函数设计为段落中错位的段数,每次剪贴有可能改变3,不相容..
所以取h()/3作为新的h(),把f,g,h,mxdp都同时扩大三倍。
用DFS的好处就是不用排序(堆白学了的感觉)和判重,再加上迭代加深,比较浅的解可以很快地求出来。
//Writer:GhostCai && His Yellow Duck
#include<iostream>
#include<cstring>
using namespace std;
int n;
int a[20];
bool check(){
for(int i=1;i<n;i++) if(a[i+1]!=a[i]+1) return false;//
return true;
}
int g(int dp){
return dp*3;
}
int h(){
int sum=0,i;
for(i=1;i<n;i++){
if(a[i+1]!=a[i]+1) sum++;//!!
}
return sum;
}
int f(int dp){
return g(dp)+h();
}
bool dfs(int dp,int mxdp){
if(f(dp)>3*mxdp) return false;//
if(check()) return true;
int pre[20],cut[20],cnt;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
while(a[j+1]==a[j]+1) j++;//跳过排好的部分
memcpy(pre,a,sizeof(a));//保存当前状态
cnt=0;
for(int k=1;k<=n;k++){
if(k<i||k>j) cut[++cnt]=a[k];
}
for(int k=1;k<=cnt+1;k++){//+1
int tcnt=0;
for(int t=1;t<k;t++) a[++tcnt]=cut[t];//!!!t<=k
for(int t=i;t<=j;t++) a[++tcnt]=pre[t];
for(int t=k;t<cnt;t++) a[++tcnt]=cut[t];
if(dfs(dp+1,mxdp)) return true;
memcpy(a,pre,sizeof(pre));//回溯
}
}
}
return false;//!!!
}
int main(){
int mycnt=1;
bool flag=0;
while(cin>>n){
if(n==0) return 0;
memset(a,0,sizeof(a));
flag=0;
for(int i=1;i<=n;i++) cin>>a[i];
if(check()){
cout<<"Case "<<mycnt++<<":"<<0<<endl;
continue;
}
for(int i=1;i<=8;i++){//迭代加深 限制深度
if(flag) continue;
if(dfs(0,i)){
cout<<"Case "<<mycnt++<<":"<<i<<endl;
flag=1;
continue;
}
}
}
return 0;
}