题目描述
二维平面有若干点,寻找一个点到所有点的距离之和最短
样例
输入
4
0 0
0 10000
10000 10000
10000 0
输出
28284
模拟退火 $O(nlog{t})$
一次模拟退火中温度$t$需要覆盖数据范围的3倍,比如题目中[0, 1e4],当t=1e4时新的x或y
的范围是$[x-t, x+t] = [-1e4,2e4]$区间范围是3e4,这大概是因为这符合正态分布$3\delta$覆盖了
绝大部分(大概$96\%$)数据范围.
时间复杂度
每一个t计算距离和$O(n)$,每次t都乘$0.9$,所以总的时间复杂度是$O(nlog{t})$.
由于一次模拟退火时间复杂度很小故而进行多次模拟退火选取最小的距离作为答案
参考文献
y总代码
C++ 代码
代码中注释辅助理解
#include<bits/stdc++.h>
using namespace std;
#define pdd pair<double, double>
vector<pdd> a;
const double inf = 2e6; // 极限距离和是100* sqrt(2) * 1e4 = sqrt(2)*e6,这里取2e6
double ans = inf;
double getd(pdd& x, pdd& y){
double dx = x.first - y.first;
double dy = x.second - y.second;
return sqrt(dx * dx + dy * dy);
}
double getsum(pdd& x){
double re = 0;
for(auto& p : a){
re += getd(x, p);
}
ans = min(ans, re);
return re;
}
double rand(double l, double r){
return (double)rand() / RAND_MAX * (r - l) + l;
}
void sa(){
pdd p(rand(0, 1e4), rand(0, 1e4));
for(double t = 1e4; t > 1e-4; t *= 0.9){
pdd np(rand(p.first - t, p.first + t), rand(p.second - t, p.second + t));
double dt = getsum(np) - getsum(p);
// 如果新点得到的距离和小于原来点得到的距离和,dt < 0,-dt/t > 0,exp(-dt/t)
// 范围 > 1,原来点一定更新为新点
// 如果新点得到的距离和大于原来点得到的距离和,dt > 0,-dt/t < 0,exp(-dt/t)
// 范围(0, 1)中间,此时随缘更新原来的点为新点
// 模拟退火的退火就在与即便新点效果没有原来的佳,也有一定概率接受这个新点
if(exp(-dt/t) > rand(0, 1)){
p = np;
}
}
}
int main(){
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int n;
cin >> n;
a.resize(n);
srand((unsigned)time(NULL));
for(int i = 0; i < n ;++i){
cin >> a[i].first >> a[i].second;
}
for(int i =0 ; i < 100; ++i) sa();
cout << round(ans) << "\n";
}