预备概念:
金属退火: 将金属缓慢加热到一定温度, 保持足够时间, 然后以适宜速度冷却
温度: 一个逐渐减小的参数, 表示接受次优解的概率
模拟退火是一种解决复杂问题的算法, 相当于贪心, 但以一个逐渐减小的该率接受次优解, 当然, 该次优解距最优解越远, 同等温度下被接受的概率也就越小
参考洛谷日报上某巨佬代码 (主要是参考在何时接受次优解, 生成正负随机数的技巧以及如何确定退火初值), 打了一下洛咕 P1337
https://www.luogu.org/problemnew/show/P1337
接受次优解:
exp ( ( ans - cur ) / temp) * RAND_MAX > rand()
当前最优解 当前解 温度 定值, 参考 cstdlib 随机数
调参失败时具体技巧:
1: 开始的随机种子一定要多随机几次 (玄学???)
2: 调节温度下降的速度 (至少 0.99 以上 QWQ)
3: 合理调整最终答案的处值, 模拟退火算法可以多执行几次, 判定算法结束的条件精度高
4: 用一些玄学数字: 19******
- #include<cstdio>
- #include<cstdlib>
- #include<cmath>
- #define ll long long
- #define ri register int
- const int MAXN = 1005;
- const int SA_TIME = 4;
- const double DELTA = 1e-14;
- ll read(){
- ll x = 0; int zf = 1; char ch = ' ';
- while (ch != '-' && (ch <'0' || ch> '9')) ch = getchar();
- if (ch == '-') zf = -1, ch = getchar();
- while (ch>= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;
- }
- int x[MAXN], y[MAXN], w[MAXN];
- int n;
- double ansx = 0, ansy = 0, ans=1e18;
- const double delta = 0.993;
- inline double getDis(double x1, double y1, double x2, double y2){
- return (sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
- }
- inline double cacEny(double curx,double cury){
- double sum = 0;
- for (ri i = 1; i <= n; ++i)
- sum += getDis(x[i], y[i], curx, cury) * w[i];
- return sum;
- }
- inline int getRand(){
- // 需要返回负数, 故特殊处理 rand 函数
- return ((rand() <<1) - RAND_MAX);
- }
- inline void SA(){
- double sx = ansx, sy = ansy, curx, cury;
- double temp = 1926;
- while (temp>= DELTA){
- if (temp <10)
- temp = temp - 1 + 1;
- curx = sx + getRand() * temp, cury = sy + getRand() * temp;
- double cur_eny = cacEny(curx, cury);
- if (cur_eny < ans){
- sx = curx, sy = cury;
- ansx = curx, ansy = cury, ans = cur_eny;
- }// 接受次优解
- else {
- if (exp((ans - cur_eny) / temp) * RAND_MAX> rand())
- sx = curx, sy = cury;
- }
- temp *= delta;
- }
- }
- inline void Solve() {
- int sumx = 0, sumy = 0;
- for (ri i = 1; i <= n; ++i)
- sumx += x[i], sumy += y[i];
- ansx=(double)(sumx) / n, ansy=(double)(sumy) / n;
- for (ri i = 1; i <= SA_TIME; ++i)
- SA();
- }
- int main() {
- srand(71806291); srand(rand()); srand(rand()); srand(rand());
- n = read();
- for (ri i = 1; i <= n; ++i)
- x[i] = read(), y[i] = read(), w[i] = read();
- Solve();
- printf("%.3f %.3f\n", ansx, ansy);
- return 0;
- }
未经博主允许禁止转载
参考资料:
洛谷日报 2018 年 9 月 #60 地址 作者: M_sea
exp 函数 地址 作者: 百度百科
来源: http://www.bubuko.com/infodetail-3005731.html