POJ 3460 Booksort IDA*

제목: 최소 조작 횟수를 통해 이 서열을 단조롭게 늘릴 수 있도록 N (N <=15) 길이의 서열을 제공합니다.허용되는 작업은 연속된 구간을 선택하고 원래 시퀀스에서 꺼낸 다음 임의의 위치에 삽입하는 것입니다.
사고방식: 우선 우리는 가장 많은 조작 횟수가 N회라는 것을 알 수 있다. 즉, 매번 우리는 한 개의 숫자를 정확한 위치에 놓는 것이다.그러나 가장 적은 조작 횟수는 어떻게 계산해야 합니까?
왜냐하면 우리는 서로 다른 서열에 대해 그 조작 방법이 뚜렷한 규칙성이 없다는 것을 알아차렸기 때문에 우리는 검색으로 이 문제를 완성해야 한다. 그리고 앞에서 조작 횟수의 상계를 언급했기 때문에 IDA* 알고리즘이 좋은 선택이다.
IDA* 알고리즘의 관건은 계발식 함수 h, 즉 현재 상태에서 최종 상태까지의 하계를 설계하는 것이다.여기서 우리는 h로 후계가 정확하지 않은 숫자의 개수를 표시하면 성질을 얻을 수 있다. 매번 조작할 때마다 h의 값이 최대 3 감소한다.그럼 자연스러운 가지치기는 3d+h>3maxd입니다.즉, 현재 상태의 h에 대해 나머지 (maxd-d) 동작을 0으로 만들 수 없으면 가지를 잘라낸다.
코드는 다음과 같습니다.

#include 
#include 
#include 

using namespace std;

const int MAX = 20;

int T,N;
int a[20];
int sa[20];

bool judge()
{
    for(int i = 0; i < N; ++i)
        if(sa[i] != a[i]) return false;
    return true;
}

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

bool dfs(int d, int maxd)
{
    if(judge()) return true;
    if(3 * d + h() > 3 * maxd) return false;
    int olda[20];
    int b[20],tot;
    memcpy(olda,a,sizeof(a));
    for(int i = 0; i < N; ++i){
        for(int j = i; j < N; ++j){
            tot = 0;
            for(int k = i; k <= j; ++k)
                b[tot++] = olda[k];
            for(int k = 0; k < N; ++k){
                memcpy(a,olda,sizeof(olda));
                if(k < i){// k       
                    for(int u = 0; u < i - k; ++u)
                        a[j - u] = a[i - u - 1];
                    for(int u = 0; u < tot; ++u)
                        a[k + u] = b[u];
                    if(dfs(d+1,maxd)) return true;
                }
                else if(k > j){// k       
                    for(int u = 0; u < k - j; ++u)
                        a[i + u] = a[j + u + 1];
                    for(int u = 0 ; u < tot; ++u)
                        a[i + k - j + u] = b[u];
                    if(dfs(d+1,maxd)) return true;
                }
            }
        }
    }
    return false;
}

int IDAstar()
{
    if(judge()) return 0;
    for(int i = 1; i <= 4; ++i)
        if(dfs(0,i)) return i;
    return 5;
}

int main(void)
{
    //freopen("input.txt","r",stdin);
    scanf("%d", &T);
    while(T--){
        scanf("%d",&N);
        for(int i = 0; i < N; ++i){
            scanf("%d",&a[i]);
            sa[i] = a[i];
        }
        sort(sa,sa+N);
        int ans = IDAstar();
        if(ans <= 4)
            printf("%d
",ans);
        else
            puts("5 or more");
    }
    return 0;
}