0%

「洛谷P2210」 Haywire - 模拟退火

模拟退火板子题。 为啥这题是黑题啊

题意

Luogu

有 $n(n\le 12)$ 只奶牛,每只奶牛有 $3$ 个朋友。现在要把这 $12$ 只奶牛排成一列,使得每只奶牛与它的朋友的距离之和最小。

题解

模拟退火

模拟退火是一个非常玄学的算法。它可以避免像爬山法一样陷入局部最优解的情况,它的解决方法是:以一定的概率接受一个不那么优的解。温度越高,则接受的概率也就越高。当温度逐渐降低时,解便趋于稳定,接受的概率也就变低。

模拟退火的大体步骤:

  1. 给定初始温度 $T_0$、最终温度 $T_1$、降温速度 $\Delta$。
  2. 在当前的解的基础上随机扰动,产生一个新解,并计算新解与原解函数值的差 $\Delta E_k$。
  3. 根据 Metropolis 准则判断是否接受新解。
  4. $T = T \times \Delta$,重复步骤 3,直到 $T < T_0$。

Metropolis 准则:若 $\Delta E_k \leq 0$,则接受新解;否则,以概率 $e^{\frac{-\Delta E_k}{T}}$ 接受新解。

一般 $T_0$ 要比较大,$T_1$ 要比较小,$\Delta$ 为接近 $1$ 的常数,迭代次数要足够多。

过不了怎么办?多改改参数就过了。

本题

直接跑模拟退火,每次随机交换两只奶牛的位置就行了。

Code

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
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 12 + 5;
const double delta = 0.995;

int n, a[N][4], p[N], pos[N], ans = 1e9;

int Calc(int x, int y)
{
int ans = 0;
for (int i = 1; i <= n; i++) pos[p[i]] = i;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= 3; j++)
ans += abs(pos[i] - pos[a[i][j]]);
return ans;
}

void Simulate_Anneal()
{
double T = 5000;
while (T > 1e-14)
{
int x = rand() % n + 1, y = rand() % n + 1;
while (x == y) x = rand() % n + 1;
swap(p[x], p[y]);
int now = Calc(x, y);
double dE = now - ans;
if (dE < 0)
{
ans = now;
}
else if (exp(-dE / T) * RAND_MAX > rand()) ;
else swap(p[x], p[y]);
T *= delta;
}
}

int main()
{
srand(time(NULL));
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= 3; j++)
scanf("%d", &a[i][j]);
for (int i = 1; i <= n; i++) p[i] = i;
while ((double)clock()/CLOCKS_PER_SEC < 0.9) Simulate_Anneal();
printf("%d\n", ans / 2);
return 0;
}