IDA*——迭代加深搜索 (UVa11212)

IDA*

迭代加深搜索：从小到大枚举搜索深度上限maxd，每次执行只考虑深度不超过maxd的节点。只要解的深度有限，能够快速找到最优解

其实设置深度上限就是为了剪枝，有的情况下每种情况都有上万个分支，最差情况下要得到最优解会非常慢，但是这些分支又是不可避免的，所以我们可以通过限制向下迭代的层数，逐渐放宽搜索区域直到找到结果

那么IDA*问题的关键就是如何限制迭代的层数，换种说法是至少还要多少步才能得到解。设深度为maxd，当前节点深度为d，乐观估价函数为h(n)，那么当在一次搜索中遇到d+h(n)>maxd时显然应该退出搜索，因此问题的关键变成了乐观估价函数如何设计

乐观估价函数需要根据题意来设计，并没有唯一标准。只有多加练习，才能找到设计函数的技巧，下面以一道紫书上的IDA*入门题为例讲解

例题

题目链接

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.

1.题意简明，这里不再概述。先推算搜索结束的条件——每个数的后继都比它大一（或者每个数的前驱都比他小一）考虑到最坏的情况：987654321，那么如果一个数一个数复制粘贴，我们最多需要8步就能得到正确结果

2.接下来的终点是设计估价函数，对于一段序列a,b,c,d…每次复制粘贴最多改变三个数的后继状态，我们设乐观估价函数h(n)为整个序列后继不正确的个数。那么每次h最多就会减少3。那么此时最坏的情况d+h(n)/3>maxd，也就是3*d+h(n)>3maxd

3.如何实现剪切粘贴过程呢，我们以序列54321为例，那么我们可以设置一个双重循环，枚举每一个子序列，这里我们还需要两个辅助数组当“剪切板”和“剩余板”，对于下面的i和j的情况，有三种剪切粘贴的方式

可以发现，我们设置的i，j保存的剪切段是从前向后枚举的，也就是每一个前驱我们后会粘贴到后面remain里，因此上面图片的第一种可以剪枝不考虑

4.我的代码参考了这个博客，感谢博主的分享。另外由于序列长度最多为9，那么考虑最坏的情况987654321，我们可以得出最多需要五次交换（LRJ老师也是这么写的，我目前还没看出来）因此如果在我们设置的迭代范围内没有找到，直接返回5即可（貌似都会得到结果）

5.刘汝佳老师还介绍了几种剪枝方式（三种策略），大家有时间的话可以优化一下代码。策略一：每次只剪一段连续的序列；策略二：假设剪切片段的第一个数字为a，最后一个数字为b，要么把这个片段粘贴到a-1的下一个位置，要么粘贴到b+1的上一个位置；策略三：永远不要破坏一个连续的片段（感觉和策略一意思一样）

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,a[15];

bool check(){
    for(int i=1;i<=n;i++){
        if(a[i]!=i) return false;
    }
    return true;
}

int h(){
    int tot=0;
    for(int i=1;i<=n;i++){
        if(a[i]!=a[i-1]+1) tot++;
    }
    return tot;
}

bool dfs(int d,int maxd){
    if(3*d+h()>3*maxd) return false;
    if(check()) return true;
    int old[15],paste[15];
    memcpy(old,a,sizeof a);
    for(int i=1;i<=n;i++){ //起点
        for(int j=i;j<=n;j++){ //终点
            int cnt=1;
            for(int k=1;k<=n;k++) //剪切
                if(k<i || k>j) paste[cnt++]=old[k];
            //在k前插入
            for(int k=1;k<cnt;k++){
                int num=1;
                for(int x=1;x<=k;x++) a[num++]=paste[x];
                for(int x=i;x<=j;x++) a[num++]=old[x];
                for(int x=k+1;x<cnt;x++) a[num++]=paste[x];
                if(dfs(d+1,maxd)) return true;
            }
        }
    }
    return false;

}

int solve(){
    if(check()) return 0;
    for(int i=1;i<5;i++)
        if(dfs(0,i)) return i;
    return 5; //最多需要5步
}



int main()
{
    int kase=1;
    while(~scanf("%d",&n)){
        if(n==0) break;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        printf("Case %d: %d\n",kase++,solve());
    }
    return 0;
}