连续两天学了一些numerical analysis的方法，昨天是学了一下三分，今天学了一下模拟退火。很早就听说了模拟退火在求费马点上的运用了，只知道一些大概，但是没有深入研究，碰到题目就卡壳了，现在算是补一下这种方法的思路。
模拟退火就是随机一些起点，然后定一个步长，每次在k个方向上去走这个步长，看下哪个方向最优，最优的话则留下来，然后步长*p，p就是控制的系数，然后如此重复。当然退火的含义就是有些时候我们会选择跳出当前的局部最优解，这个概率是预先设定的，在今天这题里貌似也不需要设定这样的概率，感觉有种水过去的感觉，贴一记代码
#pragma warning(disable:4996)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#define maxn 100
#define eps 1e-6
using namespace std; double x[maxn], y[maxn], z[maxn];
int n; double cal(double a, double b, double c)
{
double ans = 0;
for (int i = 0; i < n; i++){
ans += sqrt((x[i] - a)*(x[i] - a) + (y[i] - b)*(y[i] - b) + (z[i] - c)*(z[i] - c));
}
return ans;
} int main()
{
while (cin >> n)
{
for (int i = 0; i < n; i++){
scanf("%lf%lf%lf", x + i, y + i, z + i);
}
double curx, cury, curz;
double nxtx, nxty, nxtz;
curx = cury = curz = 0;
double cur = cal(curx, cury, curz);
double step = 1500;
while (step>eps){
double tmpx = -1, tmpy = -1, tmpz = -1; bool upd = false;
for (int i = -1; i <= 1; i++){
for (int j = -1; j <= 1; j++){
for (int k = -1; k <= 1; k++){
nxtx = curx + step*i;
nxty = cury + step*j;
nxtz = curz + step*k;
double nxt = cal(nxtx, nxty, nxtz);
if (nxt < cur){
tmpx = curx + step*i;
tmpy = cury + step*j;
tmpz = curz + step*k;
cur = nxt;
upd = true;
}
}
}
}
if (upd) {
curx = tmpx; cury = tmpy; curz = tmpz;
}
step *= 0.997;
}
printf("%.3lf %.3lf %.3lf\n", curx, cury, curz);
}
return 0;
}