IDA*

Acwing 算法提高课 IDA*

IDA*的基本思路

通常与迭代加深相结合, 本质是利用估价函数来做一个剪枝

具体地, 当当前估价值加上真实距离超过了迭代加深的最深深度则可以直接回溯

I. 估价函数的设计

对于有序序列 $\overline{12345}$ 每一个数的后继都是确定的,而每次操作都会至多改变三个后继,
所以我们可以记录一下初始序列有误后继数量 $tot$ , 则估价 $f() = \lfloor tot \rfloor = \lceil tot + 2 \rceil$

II. 本题每次搜索时间复杂度的计算-->为什么选择IDA

长度为 $n$ 的序列每次对于长度为 $i$ 的序列有 $n-i+1$ 个,可插入的空位有 $n - i$ 个，
同时对于一个序列向右插入和右边一个序列向左插入是等效的所以总体应除2
即 $\frac{sum_{i = 1}^{n}(n - i)(n - i + 1)}{2}$
此处有通项公式 $=\frac{(n - 1) \times n \times (n + 1)}{6}$
当 $n=15$ 每次搜索复杂度为 $560$ 所以四次搜索复杂度为 $560^4$ 考虑IDA双向bfs等来优化
相对来讲,dfs的代码复杂度短很多,故使用IDA

//2/11 WA dep从0开始，可能起点和终点重合
//2/11 AC

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 20;

int n, a[N], bp[7][N], dep, T;

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

void print(){
    for(int i = 1; i <= n; i ++)
        cout << a[i] << " ";
    puts("");
}

bool dfs(int u){
    if(!f()) return true;    
    if(u + f() - 1 > dep) return false;
    // cout << u << endl;
    // print();   
    for(int len = n; len >= 1; len --){
        for(int l = 1; l + len - 1 <= n; l ++){
            int r = l + len - 1;
            for(int k = r + 1; k <= n; k ++){
                memcpy(bp[u], a, sizeof a);
                int x = l;
                for(int y = r + 1 ; y <= k; x ++, y ++) a[x] = bp[u][y];
                for(int y = l; y <= r; x ++, y ++) a[x] = bp[u][y];
                if(dfs(u + 1)) return true;
                memcpy(a, bp[u], sizeof bp[u]);
            }
        }
    }
    return false;
}

int main(){
    cin >> T;
    while(T --){
        scanf("%d", &n);
        for(int i = 1; i <= n; i ++)
            scanf("%d", &a[i]);
        dep = 0;
        while(dep < 5 && !dfs(1)) dep ++;
        if(dep <= 4) printf("%d\n", dep);
        else puts("5 or more");
    }
    
    return 0;
}