ZOJ2928 Mathematical contest in modeling(模拟退火)

连续两天学了一些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;
}

转载于:https://www.cnblogs.com/chanme/p/3629583.html