BZOJ3680：吊打XXX

我对模拟退火的理解：https://www.cnblogs.com/AKMer/p/9580982.html

题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=3680

模拟退火在计算几何方面有很大的用处，特别是求费马点一类的问题。

题目意思就是要你找平面上的广义费马点。

所谓费马点，就是在一个\(n\)边形内，这个点如果到\(n\)个顶点距离和最小，那么它就是这个\(n\)边形的费马点。

然后广义费马点就是顶点上带权的费马点，统计的时候距离要乘上这个权值再加起来。

我们灵性的脑补一波就可以发现，这个题目显然不存在局部最优解，所以我们可以大胆爬山。

然后我们再灵性的想一想：首先我们可以把初始点定在\(n\)个点的中心位置，这样可以减少转移次数。再者，一个绳结如果不在最终目标点的话，那么它肯定有往最终目标点移动的趋势。所以我们在温度很高的时候，绳结坐标的跳动距离就设置大一点，就先向趋势所在的方向跳。慢慢的温度低了，我们就跳小一点的步子，慢慢稳定下来，这样子最后甚至可以准确的命中正确答案！

然后因为这个性质，爬山算法就比模拟退火在这道题上优秀得多了。爬山算法可以直接在\(BZOJ\)上\(AC\)，但是模拟退火不行。

毕竟没有局部最优解你还接受更加差的状态就显得很智障了……

时间复杂度：\(O(能A)\)

空间复杂度：\(O(能A)\)

爬山算法\(AC\)代码如下：

#include <cmath>
#include <ctime>
#include <cstdio>
#include <algorithm>
using namespace std;
 
#define sqr(a) ((a)*(a))
 
const int maxn=1e4+5;
 
int n;
double ansx,ansy,ans=1e18;//ans记录最小权值，ansx记录历史最优节点的x，ansy记录历史最优节点的y
 
struct gty {
    double x,y,w;//x，y存坐标，w存重量
}point[maxn];
 
double len() {
    double x=rand()%200000-100000;
    return x/100000;
}//随机一个-100000~100000之间的长度
 
double dis(double x1,double y1,double x2,double y2) {
    return sqrt(sqr(x1-x2)+sqr(y1-y2));
}//求(x1,y1)，(x2,y2)两点之间的距离
 
double calc(double x,double y) {//计算以点(x,y)为绳结时候的权值
    double tmp=0;
    for(int i=1;i<=n;i++)
        tmp+=dis(x,y,point[i].x,point[i].y)*point[i].w;//直接暴力算
    if(tmp<ans) {ans=tmp;ansx=x,ansy=y;}//如果权值比历史最优更小，那么就更新历史最优
    return tmp;//返回权值
}
 
int main() {
    srand(time(0));
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%lf%lf%lf",&point[i].x,&point[i].y,&point[i].w);
        ansx+=point[i].x;ansy+=point[i].y;
    }ansx/=n;ansy/=n;double now_x=ansx,now_y=ansy;//读入以及初始化
    for(double T=10000;T>=1e-5;T*=0.98) {
        double nxt_x=now_x+len()*T,nxt_y=now_y+len()*T;//爬山，每次跳len*T那么长，那么随着温度慢慢降低也会趋向稳定
        if(calc(now_x,now_y)>calc(nxt_x,nxt_y))
            now_x=nxt_x,now_y=nxt_y;//如果这个方向是绳结移动的趋势方向那么就直接跳过去
    }
    printf("%.3lf %.3lf\n",ansx,ansy);//输出
    return 0;
}

模拟退火不能\(AC\)代码如下：

#include <cmath>
#include <ctime>
#include <cstdio>
#include <algorithm>
using namespace std;

#define sqr(a) ((a)*(a))

const int maxn=1e4+5;
const double T_0=1e-5;
const double del_T=0.98;

int n;
double ansx,ansy,ans=1e18;

struct gty {
    double x,y,w;
}point[maxn];

double dis(double x1,double y1,double x2,double y2) {
    return sqrt(sqr(x1-x2)+sqr(y1-y2));
}

double calc(double x,double y) {
    double tmp=0;
    for(int i=1;i<=n;i++)
        tmp+=dis(x,y,point[i].x,point[i].y)*point[i].w;
    if(tmp<ans) {ans=tmp;ansx=x,ansy=y;}
    return tmp;
}

double len() {
    double x=rand()%200000-100000;
    return x/100000;
}

void Anneal() {
    double T=1e4,now_x=ansx,now_y=ansy;
    while(T>=T_0) {
        double nxt_x=now_x+len()*T;
        double nxt_y=now_y+len()*T;
        double tmp1=calc(now_x,now_y);
        double tmp2=calc(nxt_x,nxt_y);
        if(tmp2<tmp1||exp((tmp1-tmp2)/T)*RAND_MAX>rand())//除了这里和爬山算法是一模一样的。这里加了一个模拟退火特有的“接受不优于当前状态的状态”的概率
            now_x=nxt_x,now_y=nxt_y;
        T*=del_T;
    }
}

int main() {
    srand(time(0));
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%lf%lf%lf",&point[i].x,&point[i].y,&point[i].w);
        ansx+=point[i].x,ansy+=point[i].y;
    }ansx/=n,ansy/=n;
    for(int i=1;i<=54;i++)Anneal();
    printf("%.3lf %.3lf\n",ansx,ansy);
    return 0;
}

BZOJ3680：吊打XXX

原文：https://www.cnblogs.com/AKMer/p/9588724.html