欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-03 21:10:09
...

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的情况,有三种剪切粘贴的方式

IDA*——迭代加深搜索 (UVa11212)
可以发现,我们设置的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;
}