UVA 10228 Star not a Tree?：模擬退火求費馬點

UVA 10228 Star not a Tree?：模擬退火算法求幾何中位數

題意：給定平面上 N ≤ 100 個點，求一點使其到所有給定點的歐氏距離和最小。此點稱為 費馬點（或幾何中位數/Weber point）。

為何選擇模擬退火

• 目標凸但非處處可導（絕對值/距離函數）。
• 無解析解公式（三角形有解，多點無通用閉式解）。
• 梯度下降易陷入平坦區域；模擬退火能跳出局部最優，全局搜索能力強。
• N=100 計算單次目標函數 O(N) 極快，適合大量迭代。

模擬退火核心流程

1. 初始化：多個隨機起始點（或質心），步長 step = 1e4（坐標範圍）。
2. 鄰域搜索：8 方向（或隨機角度）嘗試 new = cur + step * dir。
3. 接受準則：若 f(new) < f(cur) 則移動；否則以機率 exp(-(f(new)-f(cur))/T) 接受（本題簡化為僅接受更優解，因凸函數無局部極小值）。
4. 降溫：step *= 0.9（或 0.8），直到 step < 1e-4（精度要求）。
5. 多重啟動：重複 10-20 次取最優，提高穩健性。

完整 AC 代碼（C++）

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

const int MAXN = 105;
const double EPS = 1e-4;
const double DECAY = 0.85;
const int DIRS[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

struct Point { double x, y; } p[MAXN];
int N;

double distSum(Point u) {
    double sum = 0;
    for (int i=0; i EPS) {
            bool improved = false;
            for (int d=0; d<8; d++) {
                Point nxt = { cur.x + DIRS[d][0]*step, cur.y + DIRS[d][1]*step };
                double val = distSum(nxt);
                if (val < curVal) {
                    curVal = val; cur = nxt; improved = true;
                }
            }
            if (!improved) step *= DECAY;
        }
        best = min(best, curVal);
    }
    return best;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        for (int i=0; i

參數調優建議

初始步長：坐標最大範圍（題目隱含 ≤ 10000）。
降溫係數：0.8~0.95，越大搜索越細但越慢。
終止精度：1e-3 ~ 1e-4 足夠輸出整數四捨五入。
多起點數：10-30 次平衡精度與時間。


替代方案：Weiszfeld 算法
費馬點的經典迭代公式：

x_{k+1} = (Σ x_i / d_i) / (Σ 1/d_i), y_{k+1} = (Σ y_i / d_i) / (Σ 1/d_i)

其中 d_i = sqrt((x_k-x_i)²+(y_k-y_i)²)。收斂快但需處理 d_i=0 奇異點。模擬退火實現更簡單、魯棒性更強。
本題是模擬退火解決幾何優化問題的經典入門例題，展示了啟發式算法在無解析解問題中的實用價值。