JSOI2004 洛谷P1337 平衡点 /费马点/ 吊打XXX

都说这道题是模拟退火的经典例题……第一次跨入随机化贪心的大门……

关于头图我不再放直接下载的地址了，点击头图会跳转到P站，P站的原图比较好看。上不去的话……emmm自己想办法？或者找找有没有神秘链接啊

题目

题目描述

如图：有n个重物，每个重物系在一条足够长的绳子上。每条绳子自上而下穿过桌面上的洞，然后系在一起。图中X处就是公共的绳结。假设绳子是完全弹性的（不会造成能量损失），桌子足够高（因而重物不会垂到地上），且忽略所有的摩擦。

问绳结X最终平衡于何处。

注意：桌面上的洞都比绳结X小得多，所以即使某个重物特别重，绳结X也不可能穿过桌面上的洞掉下来，最多是卡在某个洞口处。

输入输出格式

输入格式：

文件的第一行为一个正整数n（1≤n≤1000），表示重物和洞的数目。接下来的n行，每行是3个整数：Xi.Yi.Wi，分别表示第i个洞的坐标以及第 i个重物的重量。(-10000≤x,y≤10000, 0<w≤1000 )

输出格式：

你的程序必须输出两个浮点数（保留小数点后三位），分别表示处于最终平衡状态时绳结X的横坐标和纵坐标。两个数以一个空格隔开。

输入输出样例

输入样例#1：

3
0 0 1
0 2 1
1 1 1

输出样例#1：

0.577 1.000

分析

emmm……毕竟网上各种大佬都详细介绍了这种算法，我只想补充一些关于这种算法我自己个人的理解，由于那个全局最优点无法一路贪心得到（并不是因为答案没有凹凸性，而是平面图的步进问题，即你要以怎样的间隔去枚举可能的答案），我们可以想到如果离答案很远的时候大步向前走，离答案很近的时候慢慢走，那么就有可能接近答案，而模拟退火的模板框架中的拷贝全局解决定了退火过程中一但遇到最优解就一定会被记录下来，而不管当前解是什么状态，所以我们有一定概率（而且是蛮大的概率）碰到最优解，但这仍然是概率，万一你脸黑一路朝北或者脸好一路朝南也不是不可能，所以这时候我们就需要决定模拟退火算法中最重要的三个常数：

1. 初始温度
2. 下降率（迭代率）
3. 阈值

至于这三个常数设多少为好……emmm只能说，因题而已，大佬总是可以凭经验调出最佳参数。但我们蒟蒻也可以手动调参，只要遵循这几个原则：

• 平稳下降
• 尽可能多的迭代（不超时的情况下）
• 控制精度

多试几次也可以掌握这种技巧。直接贴代码好了

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
const int maxn = 2456;
int n;
ld ans=1e8;
struct obj{
    ld x,y,w;
}a[maxn];
pair<ld,ld> poi;
ld dist(ld x,ld y,ld u,ld v){
    return sqrtl((x-u)*(x-u)+(y-v)*(y-v));
}
long double getdis(pair<ld,ld> pp){
    //返回当前解的答案值
    ld res = 0;
    for(int i=1;i<=n;i++)
        res+=dist(a[i].x,a[i].y,pp.first,pp.second)*(ld)a[i].w;
    if (res<ans)
        ans = res,poi = pp;//重点————计算答案时随时更新全局最优解
    return res;
}
inline long double qrand()
{
    //随机生成0到1的数
    return rand()%1000/1000.0;
}
void getans(){
    ld T = 100000000000;//初始温度看玄学
    pair<ld,ld> now = poi;//拷贝全局解为当前解
    while(T>0.0001){//阈值玄学，多次尝试后0.0001可以AC
        pair<ld,ld> cur;
        cur.first=poi.first+T*(qrand()*2-1);
        cur.second=poi.second+T*(qrand()*2-1);//得到新解
        ld dis = getdis(now)-getdis(cur);//得到新解与当前解的差值
        if ((dis>0||exp(dis/T)>qrand()))//模拟退火经典不等式
            now = cur;//选取新解为当前解
        T*=0.993;//迭代率玄学
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    srand(19980875);
    int totx=0,toty=0;
    for(int i=1;i<=n;i++){
        cin >> a[i].x >> a[i].y >> a[i].w;
        totx+=a[i].x;
        toty+=a[i].y;
    }
    poi.first = (ld)totx/n;
    poi.second = (ld)toty/n; // 构造初始解
    ans = getdis(poi);//得到初始答案
    getans();//单次模拟退火
    printf("%.3llf %.3llf\n",poi.first,poi.second);
    //cout << poi.first << " " << poi.second;
    return 0;
}

时间复杂度我真心不知道怎么算，反正跑挺快的……

版权声明：本文为原创文章，版权归星夜的蓝天所有。

本文链接：http://poi.ac/archives/41/

本作品采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。

转载时须注明出处及本声明