题解 P2210 【Haywire】

· · 题解

今天刚讲模拟退火，就来发篇题解水积分

众所周知退火是一种玄学的随机算法，不过写得好+rp高会水过很多题

先看一个问题：求一个函数f最大点。

解决这个问题有种方法：爬山法

顾名思义就是想爬山一样爬。先随便找个方向走，如果增高则接着走，不然直接换方向。

这样爬山会走到最近的一个峰值，但不会得到最优解。

模拟退火其实就是爬山法优化。在不增高的时候，以一定的概率选择走下去或换方向。

一般设当前最优解为ans，得到的解为k，设一个因子t，当：

e^{k-ans\over t}>{rand()\over RANDMAX}

时换方向。（至于为什么我也不知道）。

至于t,因为越到后面答案越精确，t也会不断缩小。具体范围和缩小程度依题而定、

来张wikepedia的图，退火的过程大概就是这样的：

由于是随机算法，退火的值有很大概率不准，rp差一点还会爆0.但由于他的时间复杂度低且具有随机性，我们可以跑几千甚至上万次退火得到答案。

回到这道题，用换金币的套路，每次退火交换两个奶牛的位置统计答案即可。至于其他具体的东西就见代码吧。

于是我们有水过了一道黑题:

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

using namespace std;

int n, fr[13][4], pos[13], ans = 0x3f3f3f3f;

inline void SA() {
    double beg = 5000, end = 1e-10, tt = 0.9112;
    for (double t = beg; t > end; t *= tt) {
        int x = (rand() % n) + 1, y = (rand() % n) + 1, mmm = 0;
        swap(pos[x], pos[y]);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= 3; ++j)
                mmm += abs(pos[i] - pos[fr[i][j]]);
        if (mmm < ans) ans = mmm;
        else if (exp((ans - mmm) / t) > (double)rand() / (double)RAND_MAX) swap(pos[x], pos[y]);
    }
}

int main() {
    srand((unsigned)time(NULL)); scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        pos[i] = i;
        for (int j = 1; j <= 3; ++j)
            scanf("%d", &fr[i][j]);
    }
    int t = 5000;
    while (t--) SA();
    printf("%d", ans / 2); //我的做法每队是统计了两遍，这里要注意
    return 0;
}