题解：P2538 [SCOI2008] 城堡

· · 题解

模拟退火写法

前言：

重温曾经的黑题，当今的紫题。由于该题的官方知识点是动态规划 DP,搜索，但对本蒟蒻来说太难，于是咱们就从随机化算法之模拟退火来入手。

蒟蒻的第一篇题解不好请见谅。

前往我的博客食用效果更佳。

题目大意

给定 n 个城市（编号 0 至 n-1），每个城市 i 与城市 r_i 之间有一条长度为 d_i 的双向道路。初始有 m 个城市已有城堡。你可以在不超过 k 个无城堡的城市中新建城堡，使得所有城市到其最近城堡的最大距离最小。求该最小值。

算法思路

从爬山算法说起

爬山算法是一种简单的局部搜索算法：从随机解出发，每次尝试微调（做一些微小的扰动），若新解更优则接受。但它的缺陷是容易陷入局部最优，无法跳出当前区域去寻找全局更优解。

::::info[就像我学这个算法的时候老师所说的：] ::::

如下图（最优解为 绿色箭头，而爬山算法可能找到的最优解为 红色箭头。

（图片来源于 OI-Wiki）

模拟退火：以概率跳出局部最优

模拟退火受金属退火过程启发，通过引入“温度”参数控制搜索过程：

::::info[什么是退火？（选自 百度百科）] 退火是一种金属热处理工艺，指的是将金属缓慢加热到一定温度，保持足够时间，然后以适宜速度冷却。目的是降低硬度，改善切削加工性；消除残余应力，稳定尺寸，减少变形与裂纹倾向；细化晶粒，调整组织，消除组织缺陷。准确的说，退火是一种对材料的热处理工艺，包括金属材料、非金属材料。而且新材料的退火目的也与传统金属退火存在异同。 ::::

其核心在于Metropolis准则：若新解更差，以概率 P = e^{-\frac{\Delta E}{T}} 接受它，其中 \Delta E 为目标函数差值，T 为当前温度。

不过此处需要介绍一个概念，或者说是戏称。

玄学调参

模拟退火的效果很大程度上取决于参数的选择，这通常需要多次尝试，因此也被戏称为“玄 学调参”。

关键参数包括：初始温度、降温速率 delta （我这里用的是 alpha ）、终止温度 T_end，以及每次循环的次数。

经验所得的降温系数：0.97 或 0.997。

本题应用以及主要思路

代码实现

#include<bits/stdc++.h>
using namespace std;
int mp[105][105];
int n,m,k;
int r[105],vis[105];
vector<int>a,b;
// 计算当前方案下的最大最小距离
int check(){
    int ans=0;
    for(int i=0;i<b.size();i++){
        int mi=1e9;
        for(int j=0;j<a.size();j++){
            mi=min(mi,mp[a[j]][b[i]]);
        }
        ans=max(ans,mi);
    }
    return ans;
}
//祖传自定义随机数
int rnd(int x){
    return ((1ull*rand()*rand()+rand())^rand())%x;
}
int SA(){
    double T=1e9,alpha=0.997;//祖传模拟退火系数
    int now=check();
    if(k==0) return now;
    if(m+k==n) return 0;
    while(T>1e-4){
        int x=rand()%k+m,y=rand()%(n-m-k);
        swap(a[x],b[y]);
        int nxt=check();
        if(nxt<now || nxt>=now && rnd(10000000)<10000000*exp(-(nxt-now)/T)){//概率P
            now=nxt;
        }else{
            swap(a[x],b[y]);
        }
        T*=alpha;//降温
    }
    return now;
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>r[i];
    }
    memset(mp,0x3f,sizeof(mp));
    for(int i=1;i<=n;i++){
        int d;
        cin>>d;
        r[i]+=1;
        mp[i][r[i]]=mp[r[i]][i]=min(mp[i][r[i]],d);
        mp[i][i]=0;
    }
    //此处用dij复杂度更优，但Floyd更好写（
    for(int x=1;x<=n;x++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                mp[i][j]=min(mp[i][j],mp[i][x]+mp[x][j]);
            }
        }
    }
    for(int i=1;i<=m;i++){
        int x;cin>>x;
        a.push_back(x+1);
        vis[x+1]=1;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            if(a.size()<m+k) a.push_back(i);
            else b.push_back(i);
        }
    }
    clock_t sta=clock();
    int ans=SA();
    while((clock()-sta)*1.0/CLOCKS_PER_SEC<0.75){
        ans=min(ans,SA());
    }
    cout<<ans;
    return 0;
}

复杂度分析

不过模拟退火仅限于，题目实在超出你的能力范围，且模拟退火能拿到分时才慎用。