题解 P2534 【[AHOI2012]铁盘整理】

NKU_AI_HMX · 2021-01-30 03:12:06 · 题解

写在前面：管理大大审核辛苦了，这篇题解代码吸氧26ms左右。

正文

1. 看完本篇题解你能收获什么？

如果您和我一样是萌新呢？可以了解什么是 A^{* } ， IDA^{* } ，并且文后笔者会推荐几道题给您练习，并且除此之外，可以和笔者交流这题的思路，或者说思考过程，虽然说结论很简单，但是我相信，如果完全独立地，并且在一定时间内得出来还是不易的。

如果您是大佬，过来简单看看代码，建议您直接跳至第四点，或者代码框。

2. 啥是 A^{* } ， IDA^{* }

因为关于 A^{* } ， IDA^{* } 的介绍网络上已经很多了，笔者在这就用自己的语言，加以自己的理解来介绍一下这两种算法。

相信来大家一定都很熟悉搜索， DFS， BFS。一个一搜到底，一个一层层搜过去。但无疑这两种搜索方式都是地毯式搜索，不管长啥样都搜，这样就会带来一些问题，数据很大的时候这样搜就会面临爆时间和内存的问题，所以我们搜索的时候应该有一些判断标准，稍微带一点智力地搜，不能一股脑的随意搜。

其实这就像我们找东西，家里落了一个东西，不知道在哪，我们又不记得上次放哪了。我们就要找它，我们一定不会先把床移开，看看是不是在床下，或者首先到你家布满灰尘的储物间去找。我们会先找那些更可能的地方，比如桌子上？书下面？等等。而你之所以做出这样的选择就是基于我们自己的“判断函数”，只不过这个判断函数不单单和可能性相关，但可能性一定是我们判断的重要因素。

所以 A^{* } ， IDA^{* } 实际上分别是 BFS， DFS 的“升级版”。前者用一个优先队列（或者其他的结构）存储准备搜索的点，而队列中排序的标准正是我们用评估函数赋予的某一个点的值，所以我们每次搜索新的点时选择的都是队列中 key 值最大的那个，这样让我们可以更容易更快搜索到我们的目标点。而后者是 DFS 的“升级版”我们知道 DFS 不搜到底不知道回头，这样我们虽然达到了深度，但是广度是远远不够的，所以我们就人为给他设置了一个深度，并且同样加了一个估价函数，如下

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

以上是这一题用到的估价函数，这个函数是我们预估从当前状态走到末状态最少需要多少步（注意！我们的估价函数得出的步数一定要小于等于实际最小步数，因为我们如果估计小了，无非多搜索一些点，但是估计大了那就会遗失很多情况，很可能就导致了错误答案。）我们得到函数以后，我们每到一个点就估计当前状态到最终状态还剩的最少步数，如果当前已经走的步数 step 加上估计还需步数 evaluate 大于我们限定的最大搜索步数 maxstep 我们就直接不搜这个点，直接返回，这样我们就可以节省很多时间，而最大步数 maxstep 我们如何确定呢？我们通常从0一直递增遍历给 maxstep 赋值，对每个 maxstep 都一样的搜索，直到搜到为止，所以我们其实会发现所谓的 IDA^{* } 其实是每次 maxstep 递增时我们搜索的范围是逐层递增的，可以理解为，每次都比上个 maxstep 值时多搜索的一层。所以我们会在其中发现 BFS 的影子，所以并不难理解不对吗？

那么这两个算法难在哪里呢？

答案是：估价函数的确定

这里给大家拓展一下思维，其实大家会发现估价函数的确定是一件很玄乎的事儿，没有一个定式，靠感觉，或者经验，而且对于有些估价函数你并不好确定它和理想估价函数是不是有相同趋势，可以理解为：我们不好判断这个估价函数是不是在所有情况下都很好。而正是它这玄乎的一点让它有了“智能”，因为它可以选择性搜索，而不完全是盲目的了。

人工智能算法里面一个很重要的领域是强化学习，其实我们会发现它的一套体系最开始也是基于一个类似估值函数的东西，只不过它会在每次和环境交互之后根据结果来反向传播，修改原有参数，让这个函数更加贴近理想函数。而慢慢的单一函数的局限性也就成为了人工智能发展的一个瓶颈，所以我们后来就创造了神经网络，我们可以理解其为很多层很多个估值函数的组合，最后我们也会根据环境的反馈反向传播，修改各个神经元的数值，也就是修改估值函数的参数（了解泰勒展开的同学应该知道基本上所有函数都可以用多项式表示，只不过系数不同而已，这也就给了神经网络一个极其复杂的“估值函数”）

3. 怎么想到这个估价函数的？

我们回到这道题，因为这道题的估值函数题解也都是一样的，大家也都讲的比较清楚了（不清楚的话，欢迎评论留言，可以探讨）笔者这里就讲讲笔者的思路。

1.套用其他题思路，直接算当前状态到理想状态的“距离”

这种做法在八数码问题里面确实有用，但是在这里我们需要发现我们每一步的操作会影响很多盘的实际位置，那么我们把每个盘子单独拿出来分析就显得有些困难了，所以我们要转换思路，找到每次状态改变的不变量！盘子之间的相对位置关系。

2.算单调序列的个数

这是我最开始的想法，但是用这个的话必然是会 TLE 几个点举个例子：12365这个序列有两个单调序列，如果看作连续函数的话也就是一个极点也就是123递增，但是65递减，这样的话我们必然需要反转至少一次，如果序列是124365，12递增43递减，65递增，我们为了所有序列构成123456单调递增序列我们就至少反转2次（两个极点）。以此类推，但是这样操作不够优。于是我就从这里出发想到了大家的那种函数。（个人觉得这个函数的选取还是挺需要经验的。）

4. 一些其他题解没有的小优化

if (i == x||abs(a[i+1]-a[i])==1)continue;//这里比其他题解多了一句abs(a[i+1]-a[i])==1

因为我们不会在两个已经完美排序的两个盘子间断开，可以把他们看作一个整体了要转动就一起转，所以多加了一个判断。

temp = eva;
        reverse(a+ 1, a + i + 1);
        if (abs(a[i] - a[i + 1]) == 1)  temp = eva - 1;

这里避免了每次都调用一次估值函数来估值，直接找到两层递归间估值函数的联系做转移（能省点时间是一点）。

if (temp + step <= maxstep)
        {
             dfs(i, temp,step + 1);if (d) return;
        }

找到以后立马就返回别再搜了（这个其他题解里面好像也有）

直接给大家上代码吧

#include<bits/stdc++.h>
#define ll long long
using namespace std;
char ch1;
template<class T>
inline void rd(T& x) {
    x = 0; bool w = 0;
    ch1 = getchar();
    while (!isdigit(ch1)) { ch1 == '-' && (w = 1), ch1 = getchar(); }
    while (isdigit(ch1)) { x = (x << 1) + (x << 3) + (ch1 & 15), ch1 = getchar(); }
    w && (x = (~x) + 1);
}
template<class T>
inline void wr(T x)
{
    if (x < 0) x = -x, putchar('-');
    if (x < 10) {
        putchar(x + 48);
        return;
    }
    T L = x / 10;
    wr(L);
    putchar(x - ((L << 1) + (L << 3)) + 48);
}

int n,a[20],b[20],maxstep;
bool d;
int evaluate()//估值函数
{
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (abs(a[i] - a[i + 1]) != 1)cnt++;
    }
    return cnt;
}
void dfs(int x,int eva,int step)
{
    if (step == maxstep)//达到最大步数就返回
    {
        if (!eva)d = 1;
        return;
    }

    int temp;
    for (int i = 2; i<=n; i++)
    {
        if (i == x||abs(a[i+1]-a[i])==1)continue;//这里比其他题解多了一句abs(a[i+1]-a[i])==1，因为我们不会在两个已经完美排序的两个盘子间断开，可以把他们看作一个整体了

        temp = eva;
        reverse(a+ 1, a + i + 1);
        if (abs(a[i] - a[i + 1]) == 1)  temp = eva - 1; 

        if (temp + step <= maxstep)
        {
             dfs(i, temp,step + 1);if (d) return;
        }

        reverse(a+ 1, a + i + 1); 
    }
}

int main()
{
    rd(n);
    for (int i = 1; i <= n; i++)
    {
        rd(a[i]);
        b[i] = a[i];
    }
    a[n + 1]= n + 1;//方便估值函数操作，如果不判断最后一个盘的话会TLE一个点

    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;//离散化

    for (maxstep = 0;; maxstep++)
    {
        dfs(1, evaluate(), 0);
        if (d) { cout << maxstep; return 0; }
    }

}
/*
自己造的数据：
11
6 5 3 7 9 8 1 4 2 10 11
答案：8
13
7 4 5 3 9 6 2 8 1 10 13 11 12
答案：13
*/

推荐题目：骑士精神八数码难题

太久没写洛谷了，橙名都蓝了┬＿┬