1. Introduction

What is simulated annealing? (selected from OI Wiki )
Simulated annealing is a randomization algorithm. When the number of schemes of a problem is huge (even infinite) and it is not a unimodal function, we often use simulated annealing to solve it.

2. Realization

Simulated annealing, as the name suggests, is a process of simulated "annealing". When we use the mountain climbing algorithm, it is easy to fall into the suboptimal solution for the case of non unimodal function. Mountain climbing algorithm omits the non optimal solution near the optimal solution, so as to get a better answer, but simulated annealing attempts to accept this solution with a certain probability. The realization of this is called "simulated annealing" algorithm. (bullshit)
Because there are more random selection factors in the annealing process, the probability of obtaining the optimal solution will also increase.

Probability of accepting a new state

To get a new set of solutions, we have two choices: accept or not. Greed tells us to accept if the new state is better, otherwise we won't accept it. However, the simulated annealing algorithm indicates that if the new state is better, it must be accepted; Otherwise, it is accepted with a certain probability.
Specifically, if the current temperature is assumed to be \ (T \), and the difference between the energy of the new state (randomly obtained from the old state, such as exchanging two numbers) and the old state is \ (\ Delta E \ge 0 \), our probability of accepting this state is:

Simulated annealing process

There are \ (3 \) parameters in simulated annealing: initial temperature \ (T \), cooling coefficient \ (d \), termination temperature \ (T '\).

• Generally \ (T \) I take 1919.810, which is a relatively large number.
• \(d \) is a number close to \ (1 \) but less than \ (1 \).
• \(T '\) is a number close to \ (0 \), which is generally set as eps.
  After each random optimal solution, the simulated annealing algorithm ends when the new temperature \ (T \) is assigned to the old temperature \ (T\times d \), \ (T\le T '\).
  In the simulated annealing process, we take the optimal solution of all calculated states.

How to time card

C + + comes with a function clock(), which returns the program running time (in microseconds) divided by CLOCKS_PER_SEC is the number of running seconds. So we can:

while (clock() / (1.0 * CLOCKS_PER_SEC) <= 0.98) solve();

3. Examples

「Luogu2210」Haywire

• Meaning: &... ￥% * @ &... # ￥%
• Practice:
  The initial arrangement is arbitrary, and the cows in two arrangements are selected to exchange each time. The answer is recalculated to judge whether it is better than the current optimal solution and whether it can be transferred.

void solve() {
    double tp = 6000;
    while (tp > eps) {
        int x = rand() % n + 1;
        int y = rand() % n + 1;
        swap(p[x], p[y]);
        int res = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= 3; j++) {
                res += abs(p[i] - p[s[i][j]]);
            }
        }
        res >>= 1;
        if (res < ans) ans = res;
        else if (exp(ans - res) / tp < double(rand()) / RAND_MAX) swap(p[x], p[y]);
        tp *= d;
    }
}

「POI2008」POD-Subdivision of Kingdom

• Given an undirected graph with \ (n \) points \ (m \) edges, you need to find a scheme of combinatorial method, so that the graph is divided into two sets with \ (\ frac{n}{2} \) points, and the number of edges of the two endpoints in different sets is the least. (ensure that \ (n \) is even)
• Practice:
  An exchange scheme similar to the first question.
  At the beginning, the group is arbitrary. At each annealing, one of the two groups is taken out and exchanged. You can calculate the new answer violently, and then judge whether to transfer.

int chk(int x) { return p[x] > md; }
void solve() {
    double tp = 11451.4;
    while (tp > eps) {
        int x = rand() % md + 1;
        int y = rand() % md + md + 1;
        swap(p[t[x]], p[t[y]]);
        swap(t[x], t[y]);
        int res = 0;
        for (int i = 1; i <= m; i++) res += (chk(u[i]) ^ chk(v[i]));
        if (res < ans) {
            ans = res;
            for (int i = 1; i <= md; i++) as[i] = t[i];
        } else if (exp((ans - res) / tp) < double(rand()) / RAND_MAX) {
            swap(p[t[x]], p[t[y]]);
            swap(t[x], t[y]);
        }
        tp *= d;
    }
}

"JSOI2008" spherical space generator

• Given the coordinates of \ (n+1 \) points on a \ (n \) dimensional sphere, determine the center of the sphere.
• Practice:
  For the initial spherical center coordinates of each dimension, the coordinates of each point are averaged. Then calculate the distance between each point and the current ball center. If it is far away, pull to that point, otherwise push in the opposite direction. Different from simulated annealing, the new solution must be accepted, so the change of each dimension can be calculated, multiplied by the annealing temperature \ (T \) and added to the coordinates of each dimension.

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;
double tot, f[maxn][maxn], ans[maxn], cnt[maxn], dis[maxn];
int n;

void check() {
	tot = 0;
	for (int i = 1; i <= n + 1; i++) {
		dis[i] = cnt[i] = 0;
		for (int j = 1; j <= n; j++) dis[i] += (f[i][j] - ans[j]) * (f[i][j] - ans[j]);
		dis[i] = sqrt(dis[i]);
		tot += dis[i];
	}
	tot /= n + 1;
	for (int i = 1; i <= n + 1; i++) {
		for (int j = 1; j <= n; j++) {
			cnt[j] += (dis[i] - tot) * (f[i][j] - ans[j]) / tot;
		}
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n + 1; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%lf", &f[i][j]);
			ans[j] += f[i][j];
		}
	}
	for (int i = 1; i <= n; i++) ans[i] /= n + 1;
	for (double t = 1919.810; t >= 0.0001; t *= 0.99995) {
		check();
		for (int i = 1; i <= n; i++) ans[i] += cnt[i] * t;
	}
	for (int i = 1; i <= n; i++) printf("%.3f ", ans[i]);
	return 0;
}

4. Write it in the back

Simulated annealing true ™ It's a metaphysical thing.
If you are interested, you can do it This list of questions .
I wish you all the answers you wrote in the examination room \ (\ color{lightgreen}{\mathtt{100pts}} \)! (