模拟退火 — 平衡点 / 吊打 XXX

模拟退火 (Simulate Anneal,SA) 是一种随机化算法。和爬山法不一样的地方在于拥有一个跳出去的概率以避免陷入局部最优解的情况。

模拟退火

从维基借一张图

过程

对于平衡点 / 吊打 XXX这道题，我们以坐标平均值作为初始点。

根据当前点随机出一个新的解，如果它更接近最优解就接受它（即更新全局最优解）
如果不满足接近最优解的条件，就以一定的概率接受这个解。

概率的计算公式：设当前点与最优解的差为 $\Delta E$，当前温度为 $T$，则这个概率为 $e^{\frac{\Delta E}{kT}}$。
其中 $k$ 为一个随机数。在 C++ 中，计算 $e^k$ 的函数为 exp(k)。

先从初始温度 $T_0$ 开始，每次降温时让当前温度 $T = T\cdot\Delta$，其中 $\Delta$ 是一个略小于 1 的数。显然 $\Delta$ 越小降温幅度越大，得到最优解的概率越小，但运行的时间也最短。
设定一个终止温度 $T_k$，当 $T>T_k$ 时降温。

关于调参

要先设定随机数种子。（srand() 函数）这个随机数种子在一定程度上决定您是否能够 AC 这道题。

建议多跑几遍模拟退火过程以获得最优解。

可以调大 $\Delta$ 的值以小幅度降温，获得最优解的概率也越高。(相应地，运行时间会变长)

技巧

在时间限制内多跑几遍模拟退火。其中 TIME_LIMIT 是自定义的一个常数。
clock() 函数能够返回程序已运行的时间，可以利用这个东西卡时限。

while ((double)clock() / CLOCKS_PER_SEC < TIME_LIMIT)
    simulateAnneal();

代码与注释

#include <bits/stdc++.h>
using namespace std;
const int maxN = 1005;
const long long INF = 1e18;
const double Tk = 1e-14;    // 终止温度
const double Delta = 0.99;    // 降温系数
struct node {
    int x, y, weight;        // 结点坐标和重量
} point[maxN];
int n, sumX, sumY;                    // 点的个数，横坐标和纵坐标和
double ansX, ansY, ans = INF;        // 全局最优解坐标和全局最优解
double calc(double x, double y) {    // 计算整个系统的势能
    double energy = 0;
    for (int i = 1; i <= n; i++) {
        double deltaX = x - point[i].x, deltaY = y - point[i].y;
        energy += sqrt(deltaX * deltaX + deltaY * deltaY) * point[i].weight;
        // 整个系统的势能就是偏移量乘物体重量，势能越小越接近最优解
    }
    return energy;
}
void simulateAnneal() {                        // 模拟退火过程
    double x = ansX, y = ansY, t = 2000;    // 当前点和初始温度
    while (t > Tk) {
        double nowX = x + ((rand() << 1) - RAND_MAX) * t; // 随机一个坐标（偏移量与温度相关）
        double nowY = y + ((rand() << 1) - RAND_MAX) * t;
        double now = calc(nowX, nowY), delta = now - ans;
        if (delta < 0) x = nowX, y = nowY, ans = now, ansX = x, ansY = y;
        // 如果更接近最优解，更新当前点和全局最优解
        else if (exp(-delta / t) * RAND_MAX > rand()) x = nowX, y = nowY;
        // 根据概率公式，以一定概率接受
        t *= Delta;    // 降温
    }
}
void solve() {
    srand(time(NULL));        // 初始化随机数种子（可以不用时间，用喜欢的数就行）
    ansX = (double) sumX / n, ansY = (double) sumY / n; // 利用所求的和求平均值
    // 从平均值开始跑模拟退火过程，多跑两次以更加接近最优解
    simulateAnneal();
    simulateAnneal();
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &point[i].x, &point[i].y, &point[i].weight); // 读入
        sumX += point[i].x; sumY += point[i].y;                // 计算横纵坐标和
    }
    solve();
    printf("%.3lf %.3lf\n", ansX, ansY);                    // 输出
    return 0;
}