POJ 1379：模擬退火算法求平面點集最大最小距離

POJ 1379：模擬退火求最安全點

給定平面上 n 個已知點，求一點使其到所有已知點的最小距離最大化。即最大化 min_i dist(p, p_i)。

模擬退火流程

1. 隨機生成若干初始解（如 15 個）作為解空間。
2. 設初始溫度 T = max(X, Y)，降溫係數 0.9，終止溫度 eps = 1e-2。
3. 每輪對每個解隨機擴展：隨機角度、步長 T 產生新候選點，若在邊界內且目標函數更優則接受。
4. 降溫 T *= 0.9，重複直到 T < eps。
5. 輸出最優解坐標（保留 1 位小數）。

代碼實現

#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
using namespace std;
#define eps 1e-2
double x[10004], y[10004], qx[10004], qy[10004], X, Y;
int n;
double dist(double x, double y, double xx, double yy) {
    return sqrt((x-xx)*(x-xx) + (y-yy)*(y-yy));
}
double get(double xx, double yy) {
    double mins = 1e9;
    for (int i = 1; i <= n; i++) mins = min(mins, dist(xx, yy, x[i], y[i]));
    return mins;
}
double getr() { return (rand()%10000 + 1.0) / 10000.0; }
int main() {
    srand(time(NULL));
    int ca; scanf("%d", &ca);
    while (ca--) {
        scanf("%lf%lf%d", &X, &Y, &n);
        for (int i = 1; i <= n; i++) scanf("%lf%lf", &x[i], &y[i]);
        for (int i = 1; i <= 15; i++) { qx[i] = X*getr(); qy[i] = Y*getr(); }
        double dd = max(X, Y);
        while (dd > eps) {
            for (int i = 1; i <= 15; i++) {
                double now = get(qx[i], qy[i]);
                for (int j = 1; j <= 30; j++) {
                    double dt = getr() * 2 * acos(-1);
                    double tx = qx[i] + dd * cos(dt), ty = qy[i] + dd * sin(dt);
                    if (tx < 0 || tx > X || ty < 0 || ty > Y) continue;
                    double t = get(tx, ty);
                    if (t > now) { qx[i] = tx; qy[i] = ty; now = t; }
                }
            }
            dd *= 0.9;
        }
        double best = 0; int k = 1;
        for (int i = 1; i <= 15; i++) if (get(qx[i], qy[i]) > best) { best = get(qx[i], qy[i]); k = i; }
        printf("The safest point is (%.1lf, %.1lf).\n", qx[k], qy[k]);
    }
    return 0;
}

模擬退火參數（初始解數、擴展數、降溫速度）需經驗調整，多次提交可緩解 RP 問題。適用於非凸優化問題的近似求解。