模拟退火入门——POJ 2420

「爱情、让人受尽委屈。」 2022-05-08 13:14 210阅读 0赞

题目链接：  
[POJ 2420][]

题目大意：  
给出平面上N（<=100）个点，你需要找到一个这样的点，使得这个点到N个点的距离之和尽可能小。输出这个最小的距离和（四舍五入到最近的整数）

解题思路：  
如果下午不是马原课无聊，学习了一下模拟退火的思想，大概看到这题也没太多想法，不过是真的神奇啊，先放上我觉得讲得很简单的模拟退火算法的一个讲解  
[大白话解析模拟退火算法][Link 1]

看完之后，总结就是，每次把下一个状态和当前状态对目标答案进行比较，如果比当前更优或者其exp(dE/T) 在（0，1）之间，则进行退火（即T乘以某个不大于1的正数），然后不断更新下一状态，直到T小于某个T\_min（一般比较小，1e-3这样吧，具体看题目，或者经验也是很重要感觉2333，包括上面对T退火的那个数也有讲究，多练吧！）  
最后就有很可能得到最优解了！！！

回到本题，初始状态的话，当然是所有点的平均位置的那个点，目标答案是和其他点的距离和，这里我们每次随机生成一个角度，然后用当前点坐标和T得到下一个状态的坐标。计算各到其他点的距离和，记录最小值，然后不断退火，就可以很大概率得到最优解

AC代码：

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    
    #define INF 1e17
    #define EPS 1e-3
    #define PI acos(-1)
    #define FIRE(x) (x *= 0.99)
    using namespace std;
    
    struct Point{
        double x,y;
        Point(){}
        Point(double _x, double _y):x(_x),y(_y){}
        void operator +=(const Point t){
            x += t.x; y += t.y;
        }
    };
    
    Point p[150],now;
    
    int n;
    double ans;
    double getDist(double x,double y){
        double ret = 0;
        for(int i=0; i<n; ++i){
            ret += sqrt((p[i].x-x)*(p[i].x-x)*1.0 + (p[i].y-y)*(p[i].y-y)*1.0);
        }
        if(ret < ans) ans = ret;
        return ret;
    }
    
    double Rand(){
        return (rand()%1000+1)/1000.0;
    }
    
    void solve(){
        double T = 100000.0,alpha,sub;
        while(T > EPS){
            alpha = 2.0*PI*Rand();
            Point tmp(now.x + T*cos(alpha), now.y + T*sin(alpha));
            sub = getDist(now.x,now.y) - getDist(tmp.x,tmp.y);
            if(sub >=0 || exp(sub/T) >= Rand()) now = tmp;
            FIRE(T);
        }
       
    }
    
    int main(){
        srand(100233);
        scanf("%d",&n);
        for(int i=0; i<n; ++i){
            scanf("%lf%lf",&p[i].x,&p[i].y);
            now += p[i];
        }
        ans = 0x3f3f3f3f;
        now.x /=n; now.y /=n;
        solve();
        printf("%.f\n",ans);
        return 0;
    }

[POJ 2420]: https://cn.vjudge.net/contest/208694#problem/A
[Link 1]: http://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html