前排提示：LZ是个菜比，有可能有讲的不对的地方，请在评论区指出qwq

0.基本思想

模拟退火其实没有那么高大上。说白了就是初始化一个“温度”。每次随机乱选一个方案，如果比以前的方案优那么就要，否则就以一定的概率要或者不要。当前方案越狗屎就越不想要，“温度”越低越不想要。然后把温度降低一些，反复循环，直到温度为0为止。

1.照本宣科实现

Fuck CCF(小声

呃，就以臭名昭著著名的TSP问题举例子吧。

什么？你不知道TSP？这个就是->点我。

其实正解是搜索，但是\(O(n!)\)的时间复杂度实在伤不起（除了像本题一样\(n\le15\)），所以考虑模拟退火。

首先，初始化一个初始”温度“。越高越好，但是过高会让程序变慢，至于为什么以后再说。

const double T0=1e5/*初始温度*/,T_end=1e-4/*结束温度（由于非常接近0可以看作0）*/;

void SA(){

    double T=T0;//当前温度

    while(T>T_end){//对应”反复循环，直到温度为0为止。“这句话

    }

}

然后胡乱生成一个解：

double calc(){//意思是查询当前解的代价，具体到问题里就是按照当前顺序访问要走多远

    double ret=0.0;

    for(int i=1;i<=n;i++){

        ret+=g[ans[i-1]][ans[i]];//g数组的意思是从一个点到另一个点要走多少

    }

    return ret;

}

int random_disp(int l,int r){//意思是在区间[l,r]内随机生成一个数

    srand(time(NULL));

    static std::mt19937 random_engine(rand());

    if(l>r)swap(l,r);

    uniform_int_distribution<int> u(l,r);

    return u(random_engine);

}

const double T0=1e5/*初始温度*/,T_end=1e-4/*结束温度（由于非常接近0可以看作0）*/;

void SA(){

    double T=T0;//当前温度

    while(T>T_end){//对应”反复循环，直到温度为0为止。“这句话

        int u=random_disp(1,n),v=random_disp(1,n);

        swap(ans[u],ans[v]);

        double new_sol=calc();//随机交换两个数，就相当于乱生成一个

        //ans数组的意义是访问的顺序

    }

}

判断是否要这个解：

inline bool CBP(double x){//Choose by probability.

                          //以概率x返回 true或者false

    if(x>=1.0)return true;

    if(x<=0.0)return false;

    srand(time(NULL));

    static std::mt19937 random_engine(rand());

    uniform_real_distribution<double> u(0.0,1.0);

    return u(random_engine)<=x;

}

double calc(){//意思是查询当前解的代价，具体到问题里就是按照当前顺序访问要走多远

    double ret=0.0;

    for(int i=1;i<=n;i++){

        ret+=g[ans[i-1]][ans[i]];//g数组的意思是从一个点到另一个点要走多少

    }

    return ret;

}

int random_disp(int l,int r){//意思是在区间[l,r]内随机生成一个数

    srand(time(NULL));

    static std::mt19937 random_engine(rand());

    if(l>r)swap(l,r);

    uniform_int_distribution<int> u(l,r);

    return u(random_engine);

}

const double T0=1e5/*初始温度*/,T_end=1e-4/*结束温度（由于非常接近0可以看作0）*/;

void SA(){

    double T=T0;//当前温度

    while(T>T_end){//对应”反复循环，直到温度为0为止。“这句话

        int u=random_disp(1,n),v=random_disp(1,n);

        swap(ans[u],ans[v]);

        double new_sol=calc();//随机交换两个数，就相当于乱生成一个

        //ans数组的意义是访问的顺序

        if(new_sol<old_sol){//如果撞到狗屎运，随机乱搞一个都比以前的解好

            old_sol=new_sol;//那么更新

        }else if(CBP(exp(double(old_sol-new_sol)/T))){//否则以概率决定是否更新

            old_sol=new_sol;

        }else{

            swap(ans[u],ans[v]);//换回来，交换两次等于没换

        }

    }

}

等等，exp(double(old_sol-new_sol)/T)是什么意思？

这个我当初也蒙了半天（我太蔡了），尽量讲的明白一点

先把它翻译成数学语言：

\[e^{\frac{\Delta f}{T}}
\]

再翻译成人话：

\(e\) (是个常数，大约是2.7) 的 (以前解 - 当前解 )除以当前温度次方

(以前解 - 当前解 )，也就是\(\Delta f\)，一定是个负数，为什么看看代码就知道了。

那么，\(\Delta f\)越小（也就是绝对值越大），也就是当前解越狗屎，\(\frac{\Delta f}{T}\)就越小。当\(T\)越小，也就是温度越小，\(\frac{\Delta f}{T}\)的绝对值也就越大，\(\frac{\Delta f}{T}\)也就越小。\(\frac{\Delta f}{T}\)越小，\(e^{\frac{\Delta f}{T}}\)也就越小（但一定大于0），正好对应了”当前方案越狗屎就越不想要，“温度”越低越不想要。“这句话。

^通读三遍再往下看

降低温度并记录遇到的最优解：

inline bool CBP(double x){//Choose by probability.

                         //以概率x返回 true或者false

   if(x>=1.0)return true;

   if(x<=0.0)return false;

   srand(time(NULL));

   static std::mt19937 random_engine(rand());

   uniform_real_distribution<double> u(0.0,1.0);

   return u(random_engine)<=x;

}

double calc(){//意思是查询当前解的代价，具体到问题里就是按照当前顺序访问要走多远

   double ret=0.0;

   for(int i=1;i<=n;i++){

       ret+=g[ans[i-1]][ans[i]];//g数组的意思是从一个点到另一个点要走多少

   }

   return ret;

}

int random_disp(int l,int r){//意思是在区间[l,r]内随机生成一个数

   srand(time(NULL));

   static std::mt19937 random_engine(rand());

   if(l>r)swap(l,r);

   uniform_int_distribution<int> u(l,r);

   return u(random_engine);

}

const double T0=1e5/*初始温度*/,T_end=1e-4/*结束温度（由于非常接近0可以看作0）*/;

void SA(){

   double T=T0;//当前温度

   while(T>T_end){//对应”反复循环，直到温度为0为止。“这句话

       int u=random_disp(1,n),v=random_disp(1,n);

       swap(ans[u],ans[v]);

       double new_sol=calc();//随机交换两个数，就相当于乱生成一个

       //ans数组的意义是访问的顺序

       if(new_sol<old_sol){//如果撞到狗屎运，随机乱搞一个都比以前的解好

           old_sol=new_sol;//那么更新

       }else if(CBP(exp(double(old_sol-new_sol)/T))){//否则以概率决定是否更新

           old_sol=new_sol;

       }else{

           swap(ans[u],ans[v]);//换回来，交换两次等于没换

       }

       ans_val=min(ans_val,old_sol);

       ans_val=min(ans_val,new_sol);//记录最优解

       T*=0.997;//缓缓降低

   }

}

然后，不停循环，直到温度为0为止。

Code：

#include <bits/stdc++.h>

using namespace std;

#define MAXN 20

int n,ans[MAXN],st=clock();

double g[MAXN][MAXN],x[MAXN],y[MAXN],ans_val=1e10;

double euc_dis(double x1,double y1,double x2,double y2){

   return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

}

inline bool CBP(double x){//Choose by probability

   if(x>=1.0)return true;

   if(x<=0.0)return false;

   srand(time(NULL));

   static std::mt19937 random_engine(rand());

   uniform_real_distribution<double> u(0.0,1.0);

   return u(random_engine)<=x;

}

int random_disp(int l,int r){

   srand(time(NULL));

   static std::mt19937 random_engine(rand());

   if(l>r)swap(l,r);

   uniform_int_distribution<int> u(l,r);

   return u(random_engine);

}

double calc(){

   double ret=0.0;

   for(int i=1;i<=n;i++){

       ret+=g[ans[i-1]][ans[i]];

   }

   return ret;

}

const double T0=1e5,T_end=1e-4,DT=0.997;

void SA(){

   double T=T0,old_sol=calc();

   while(T>T_end){

       int u=random_disp(1,n),v=random_disp(1,n);

       swap(ans[u],ans[v]);

       double new_sol=calc();

       if(new_sol<old_sol){

           old_sol=new_sol;

       }else if(CBP(exp(double(old_sol-new_sol)/T))){

           old_sol=new_sol;

       }else{

           swap(ans[u],ans[v]);

       }

       ans_val=min(ans_val,old_sol);

       ans_val=min(ans_val,new_sol);

       T*=DT;

   }

}

int main(){

   srand(time(NULL));

   scanf("%d",&n);

   for(int i=1;i<=n;i++){

       scanf("%lf %lf",x+i,y+i);

   }

   for(int i=0;i<=n;i++){

       for(int j=0;j<=n;j++){

           g[i][j]=euc_dis(x[i],y[i],x[j],y[j]);

       }

   }

   for(int i=1;i<=n;i++){

       ans[i]=i;

   }

   while(clock()-st<0.95*CLOCKS_PER_SEC){//只要还没超时就不停退火

       SA();

   }

   printf("%.2lf\n",ans_val);

   return 0;

}

以上代码能够ACP1433，也就是例题。

3.一些注意事项

由于模拟退火是个概率算法，所以除非你想不出正解最好不要用。
由于模拟退火是个概率算法，所以最好多跑几遍。
由于模拟退火是个概率算法，所以要仔细调整几个参数——初始温度、结束温度、变化率。
由于模拟退火是个概率算法，所以时间复杂度是\(O(玄学)\)。初始温度越高，温度变化率越接近1，跑得越慢，也越精确。
由于模拟退火是个概率算法，所以LZ想不出来怎么继续队形了qwq。
由于模拟退火是个概率算法，所以能给LZ点一个赞吗qwq

巴特西

模拟退火详解&P1433题解

0.基本思想

1.照本宣科实现

Fuck CCF(小声

这个我当初也蒙了半天（我太蔡了），尽量讲的明白一点

^通读三遍再往下看

3.一些注意事项

完结撒花~

完结撒CCF~

最新文章

热门文章

巴特西

模拟退火详解&P1433题解

0.基本思想

1.照本宣科 实现

Fuck CCF(小声

这个我当初也蒙了半天（我太蔡了），尽量讲的明白一点

^通读三遍再往下看

3.一些注意事项

完结撒花~

完结撒CCF~

最新文章

热门文章

1.照本宣科实现