跳转至

模拟退火

流程与爬山算法类似，在基础上加入退火操作。

如爬山里的图绿色部分所示，兔子有一定概率朝更矮的方向跳，这使它在不是最高的山上也有可能跳到最高的山上。

过程

如果新状态更优就更新状态，否则以一定概率更新。

定义当前温度为 \(T\)，新状态 \(S'\) 与已知状态 \(S\)（新状态由已知状态通过随机的方式得到）之间的能量（值）差为 \(\Delta E\)（ \(\Delta E\geqslant 0\)），则不优情况下更新解的概率为 \(e^\frac{-\Delta E}{T}\)。

下面是一个比较形象的演示动图：

一些细节

  1. 温度和计算状态的参数对结果影响很大，可以对拍来调参数。
  2. 为保证准确性，可以多执行几次模拟退火。
  3. 即使如此，也可能一次提交无法通过，可以换随机种子多次尝试。

例题一

P2503 [HAOI2006] 均分数据

已知 \(n\) 个正整数 \(a_1,a_2 ... a_n\) 。要将它们分成 \(m\) 组，使得各组数据的数值和最平均，即各组数字之和的均方差最小。

对于一种给定的顺序，一个很容易想到的操作方案是将 \(a\) 插进当前和最小的一组。

实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
double ask()
{
    memset(b, 0, sizeof(b));
    b[0] = 2e9;
    for (int i = 1; i <= n; i++)
    {
        int x = 0;
        for (int j = 1; j <= m; j++)
            if (b[j] < b[x]) x = j;
        b[x] += a[i];
    }
    double num2 = 0;
    for (int i = 1; i <= m; i++) num2 += (num1 - b[i]) * (num1 - b[i]);
    return sqrt(num2 / m);
}

其实卡时+每次随机一个排列就可以过了。

每次随机选择两个位置并交换，如果所得的结果更优则更新数组，否则有一定概率更新。

实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
#define urd uniform_real_distribution
int n, m, a[25], b[25];
double num1, ans = 2e9;
mt19937 rnd(1919810);
double ask()
{
    memset(b, 0, sizeof(b));
    b[0] = 2e9;
    for (int i = 1; i <= n; i++)
    {
        int x = 0;
        for (int j = 1; j <= m; j++)
            if (b[j] < b[x]) x = j;
        b[x] += a[i];
    }
    double num2 = 0;
    for (int i = 1; i <= m; i++) num2 += (num1 - b[i]) * (num1 - b[i]);
    return sqrt(num2 / m);
}
void sa()
{
    for (double st = 3000; st > 0.00000001; st *= 0.95)
    {
        int x = rnd() % n + 1, y = rnd() % n + 1;
        swap(a[x], a[y]);
        double now = ask(); // 省略
        if (now < ans)
            ans = now;
        else if (urd<>(0, 1)(rnd) > exp((now - ans) / st))
            swap(a[x], a[y]);
    }
}
int main(void)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        num1 += a[i];
    }
    num1 /= m;
    const clock_t st = clock();
    while (1) // 卡时
    {
        rnd = mt19937(rnd());
        sa();
        const clock_t ed = clock();
        const int time_limit = 950;
        if (double(ed - st) * 1000 / CLOCKS_PER_SEC >= time_limit) break;
    }
    printf("%.2lf", ans);
    return 0;
}

例题二

P5544 [JSOI2016] 炸弹攻击1

平面上有 \(n\) 个建筑（可视为圆）与 \(m\) 个敌人。你可以在任意位置放置半径不超过 \(R\) 的圆，其范围内不能有任何建筑，求其能包含的最多的敌人数。

该题中答案为整数且范围很小，如果只以答案为状态，函数不平滑，而且有很多位置受建筑影响答案为 \(0\)，这使得函数被分成很多段。 考虑在状态中加入新成分。经过思考可以想到将所有答案为 \(0\) 的位置的状态设为「当前圆为碰到第一个敌人还需增大的半径」，再通过尝试可以找到一个合适的系数。

实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
#define urd uniform_real_distribution
mt19937 rnd(12);
int n, m, mxr, ans;
struct node
{
    int x, y, r;
} a[15], b[1005];
double gtds(double x, double y, double xx, double yy)
{
    return (x - xx) * (x - xx) + (y - yy) * (y - yy);
}
double _count(double x, double y)
{
    int num1 = 0;
    double num2 = 1e13, r = mxr;
    for (int i = 1; i <= n; i++)
    {
        double dis = sqrt(gtds(a[i].x, a[i].y, x, y));
        r = min(r, max(dis - a[i].r, 0.0));
    }
    for (int i = 1; i <= m; i++)
    {
        double dis = sqrt(gtds(b[i].x, b[i].y, x, y));
        if (dis <= r) num1++;
        num2 = min(num2, dis - r);
    }
    ans = max(ans, num1);
    return num1 - max(0.0, num2) * 14.14;
}
void sa()
{
    double x = 0, y = 0;
    double ls = _count(x, y);
    for (double st = 1e12; st >= 1e-8; st *= 0.9996)
    {
        double xx = x + urd<>(-10, 10)(rnd) * st;
        double yy = y + urd<>(-10, 10)(rnd) * st;
        double now = _count(xx, yy);
        if (now > ls || urd<>(0, 1)(rnd) <= exp((now - ls) / st))
        {
            x = xx;
            y = yy;
            ls = now;
        }
    }
}
int main(void)
{
    scanf("%d%d%d", &n, &m, &mxr);
    for (int i = 1; i <= n; i++) scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].r);
    for (int i = 1; i <= m; i++) scanf("%d%d", &b[i].x, &b[i].y);
    sa();
    rnd = mt19937(20060617);
    sa();
    sa();
    printf("%d", ans);
    return 0;
}

例题三

P3936 Coloring

按要求在 \(n \times m\) 的格子上染色，求使得相邻格子颜色不同的数量最少的染色方案。

每次随机交换两个格子的颜色，能使答案更优就保留操作，否则概率保留。

实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
#define urd uniform_real_distribution
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
int n, m, c, a[25][25], aa[25][25], ans = 2e9, b[25][25], book[25];
int check(int xa, int ya, int xb, int yb)
{
    if (xa < 1 || xa > n) return 0;
    if (xb < 1 || xb > n) return 0;
    if (ya < 1 || ya > m) return 0;
    if (yb < 1 || yb > m) return 0;
    if (a[xa][ya] != a[xb][yb]) return 1;
    return 0;
}
void sa()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) a[i][j] = aa[i][j];
    int lst = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            lst += check(i, j, i + 1, j) + check(i, j, i, j + 1);
    for (double st = 1; st >= 1e-15; st *= 0.99999)
    {
        if (lst < ans)
        {
            ans = lst;
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++) b[i][j] = a[i][j];
        }
        int xa = rnd() % n + 1, ya = rnd() % m + 1;
        int xb = rnd() % n + 1, yb = rnd() % m + 1;
        int now = lst;
        now -= check(xa, ya, xa - 1, ya) + check(xb, yb, xb - 1, yb);
        now -= check(xa, ya, xa + 1, ya) + check(xb, yb, xb + 1, yb);
        now -= check(xa, ya, xa, ya - 1) + check(xb, yb, xb, yb - 1);
        now -= check(xa, ya, xa, ya + 1) + check(xb, yb, xb, yb + 1);
        swap(a[xa][ya], a[xb][yb]);
        now += check(xa, ya, xa - 1, ya) + check(xb, yb, xb - 1, yb);
        now += check(xa, ya, xa + 1, ya) + check(xb, yb, xb + 1, yb);
        now += check(xa, ya, xa, ya - 1) + check(xb, yb, xb, yb - 1);
        now += check(xa, ya, xa, ya + 1) + check(xb, yb, xb, yb + 1);
        if (now < lst || urd<>(0, 1)(rnd) <= exp((lst - now) / st))
            lst = now;
        else
            swap(a[xa][ya], a[xb][yb]);
    }
}
int main(void)
{
    scanf("%d%d%d", &n, &m, &c);
    int nx = 1, ny = 1;
    for (int i = 1; i <= c; i++)
    {
        int x;
        scanf("%d", &x);
        while (x--)
        {
            aa[nx][ny] = i;
            nx++;
            if (nx > n)
            {
                nx = 1;
                ny++;
            }
        }
    }
    sa();
    sa();
    sa();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++) printf("%d ", b[i][j]);
        putchar('\n');
    }
    return 0;
}