AcWing 180. 排书

AStar 最坏情况\(O(log_2560 ^ 4)\)

用\(AStar\)算法做了这题，程序跑了\(408ms\)。

相比于\(IDA*\)的\(100ms\)左右要慢上不少。

且\(A*\)由于是\(bfs\)，代码长度也较长。

跑的慢的原因应该有两点：

用了三个\(STL\)，垃圾STL毁我青春
这题的指数暴涨，是\(560\)，所以\(log\)反而比前几次叠加要大。

使用的估价函数是一样的，即：

\(h(n) = \lceil\frac{相邻位置不对的对数}{3}\rceil\)

估价函数详细的证明 & 解释见 y总的题解。

总结了一下应该在何时选择 \(A*\) 或 \(IDA*\)：

需要最小字典序时，状态表示很大，指数增长较快时，使用\(IDA*\)
若状态容易表示，指数增长较慢时，使用\(A*\)（注意需要最小字典序时不能用\(A*\)，因为他不是按照顺序搜索的）。

C++ 代码

#include <cstdio>

#include <iostream>

#include <unordered_set>

#include <queue>

using namespace std;

typedef unsigned long long ULL;

const int N = 15, B = 17;

int n;

struct State{

    //v表示当前的状态，step表示步数，f表示当前估计值（答案）

    int v[N], step, f;

    //重载小于号

    bool operator < (const State &x) const{

        return f > x.f;

    }

}Start;

//检测是否到了目标状态

bool check(State x){

    for(int i = 0; i < n; i++)

        if(x.v[i] != i + 1) return false;

    return true;

}

//用于检测一个状态是否已经访问过了

unordered_set<ULL> s;

priority_queue<State> q;

//hash

ULL get(State x){

    ULL res = 0;

    for(int i = 0; i < n; i++)

        res = res * B + x.v[i];

    return res;

}

int f(State x){

    int res = 0;

    for(int i = 1; i < n; i++)

        if(x.v[i] - 1 != x.v[i - 1]) res++;

    return res % 3 ? res / 3 + 1 : res / 3;

}

int bfs(){

    while(q.size()) q.pop();

    Start.step = 0; Start.f = f(Start);

    q.push(Start); s.insert(get(Start));

    while(!q.empty()){

        State u = q.top(); q.pop();

        if(u.f >= 5) return 5;

        if(check(u)) return u.step;

        for(int l = 1; l < n; l++){

            for(int i = 0; i + l - 1 < n; i++){

                int j = i + l - 1;

                for(int k = i + l; k < n; k++){

                    State v;

                    for(int f = 0; f < n; f++) v.v[f] = u.v[f];

                    for(int f = j + 1, t = i; f <= k; f++, t++)

                        v.v[t] = u.v[f];

                    for(int f = i, t = i + k - j; f <= j; f++, t++)

                        v.v[t] = u.v[f];

                    if(s.count(get(v)) > 0) continue;

                    s.insert(get(v));

                    v.step = u.step + 1;

                    v.f = v.step + f(v);

                    q.push(v);

                }

            }

        }

    }

    return 5;

}

int main(){

    int T; scanf("%d", &T);

    while(T--){

        s.clear();

        scanf("%d", &n);

        for(int i = 0; i < n; i++)

            scanf("%d", &Start.v[i]);

        int res = bfs();

        if(res >= 5) puts("5 or more");

        else printf("%d\n", res);

    }

    return 0;

}

巴特西

AcWing 180. 排书

AStar 最坏情况\(O(log_2560 ^ 4)\)

C++ 代码

最新文章

热门文章