$模拟退火$

$这种全局最优的问题用模拟退火$

$模拟退火就是每次向四周随机移动,移动的幅度和温度成正比,如果新的位置更优就接受,否则按一定概率接收,概率和温度成正比$

$最后稳定后再在最优解附近蹦跶几下看看有没有更好的$

$你问我这是什么道理,我说无(我)可(不)奉(知)告(道)$

#include<bits/stdc++.h>
using namespace std;
const int N = ;
struct P {
double x, y, w;
} p[N], ans;
int n;
double mn = 1e18, T = ;
double rd() {
return rand() % / 10000.0;
}
double sqr(double x) {
return x * x;
}
double calc(P a) {
double ret = ;
for(int i = ; i <= n; ++i) {
ret += sqrt(sqr(a.x - p[i].x) + sqr(a.y - p[i].y)) * p[i].w;
}
if(ret < mn) {
mn = ret;
ans = a;
}
return ret;
}
int main() {
srand();
scanf("%d", &n);
for(int i = ; i <= n; ++i) {
scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].w);
ans.x += p[i].x;
ans.y += p[i].y;
}
ans.x /= n;
ans.y /= n;
P now = ans;
while(T > 0.001) {
P nw;
nw.x = now.x + T * (rd() * - 1.0);
nw.y = now.y + T * (rd() * - 1.0);
double d = calc(now) - calc(nw);
if(d > || exp(d / T) > rd()) {
now = nw;
}
T *= 0.991;
}
for(int i = ; i <= ; ++i) {
P nw;
nw.x = ans.x + T * (rd() * - 1.0);
nw.y = ans.y + T * (rd() * - 1.0);
calc(nw);
}
printf("%.3f %.3f\n", ans.x, ans.y);
return ;
}

最新文章

  1. centos 编译 安装 protobuf
  2. 第一部分:IBM量子体验
  3. PHP中GD2的运用,注意编码格式的改变,以及head()函数之前不能有任何html元素包括空格!!!
  4. 转 : c++ 结构体 前向声明
  5. Set Linux starts in multi-user mode as default.
  6. [转]WCF:如何将net.tcp协议寄宿到IIS
  7. dlmalloc 2.8.6 源代码具体解释(6)
  8. android开发技巧
  9. Discuz经典函数注释之authcode
  10. ASP.NET后台中调用前台Javascript函数的几种方法
  11. python的pandas库学习笔记
  12. 【Java基础】【21IO(字符流)&amp;字符流其他内容&amp;递归】
  13. jQuery的下拉选select2插件用法
  14. Zabbix appliance One Stop
  15. php与java通用AES加密解密算法
  16. 第五节,损失函数:MSE和交叉熵
  17. 【转载】linux ls -l命令详解
  18. SGU---102 欧拉函数
  19. 4. Add override methods to class
  20. python 定义类 学习1

热门文章

  1. 混合背包 hdu5410 CRB and His Birthday
  2. JrtpLib vs2012环境下编译及使用 GotoFirstSourceWithData 方法 进不去
  3. Windows 系统 vs2012 MinGW 编译ffmpeg 静态库
  4. VCC/AVCC/VDD/AVDD区别
  5. linux 块设备驱动(五)——块设备应用层的操作
  6. maven命令学习-发布上传jar包-deploy
  7. Nmap扫描教程之基础扫描具体解释
  8. 51NOD 1962 区间计数 单调栈+二分 / 线段树+扫描线
  9. 在苹果iOS平台中获取当前程序进程的进程名等信息
  10. [HAOI2016]找相同子串