模拟退火 get ！

· · 个人记录

模拟退火大法好！

简单介绍一下模拟退火：（摘自大佬的讲义）

模拟退火算法来源于固体退火原理，
将固体加温至充分高，再让其徐徐冷却。
加温时，固体内部粒子随温升变为无序状，内能增大，
而徐徐冷却时粒子渐趋有序，
在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。
根据Metropolis准则，粒子在温度T时趋于平衡的概率为 e-ΔE/(kT) 
其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。
模拟退火实际上就模拟了这个过程。

模拟退火适用于解决 TSP 问题， 其特点在于有一定几率接受一个较差解，以减小陷入局部最优解的概率。

入门：

codevs 1344

翻到隔壁 codevs 去做了道模板题，利用结构体存连接顺序，不断的找较优解

int n;
double tot=0x3f3f3f3f;
double x[30],y[30];
double map[30][30];

struct Path{
    int path[30];
    Path(){
        for(int i=1;i<=n;i++)   path[i] = i;
    }
    Path(const Path &p){
        memcpy(path,p.path,sizeof(path) );
        swap(path[rand()%n+1],path[rand()%n+1]);
    }
    double dist()
    {
        double len=0;
        for(int i=1;i<n;i++)
            len += map[path[i]][path[i+1]];
        return len;
    }
};

bool accept(double delta, double temp)
{
    if(delta <= 0)  return 1;
    return rand()<=exp((-delta)/temp)*RAND_MAX;
}

double solve()
{
    Path p;
    const double Tem = 100;
    const double del = 0.99;
    double ans = 0x3f3f3f3f;
    double tempre = Tem;
    while(tempre >= 0.01)
    {
        Path p2(p);
        if(accept(p2.dist()-p.dist(),tempre))
            p = p2;
        tempre *= del;
    }
    return p.dist();
}

int main(void)
{
    srand(time(NULL));
    cin >> n;
    for(int i=1;i<=n;i++)
        cin >> x[i] >> y[i];
    for(int i=1;i<n;i++)
    for(int j=i+1;j<=n;j++)
    {
        map[i][j] = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
        map[j][i] = map[i][j];
    }
    for(int i=1;i<=355;i++)
        tot = min(tot,solve());
    printf("%.2lf",tot);
    return 0;
}