首页 > 其他分享 >「学习笔记」浅入模拟退火

「学习笔记」浅入模拟退火

时间:2023-08-24 20:36:18浏览次数:55  
标签:ch 浅入 db pos 笔记 int 模拟退火 read

什么是退火?

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

此时的你大概是这样的

???

看不懂不要紧 毕竟不会让你真的去退火的,让我们一步一步的学习。


在此之前,如果你了解 爬山算法,那你大概可以知道模拟退火的过程了。

模拟退火是一个随机化算法,每次随机都会有一个结果,我们要维护最优结果,但有时最优结果是由当前的不优结果推来的,模拟退火可以让我们有一定的概率接受不优的结果,使得最后可以得到最优解。

过程

模拟退火有三个变量,初始温度 \(T_0\),降温系数 \(d\),终止温度 \(T_k\)。其中 \(T_0\) 是一个比较大的数,\(d\) 是一个非常接近 \(1\) 但是小于 \(1\) 的数,\(T_k\) 是一个接近 \(0\) 的正数。

首先让温度 \(T=T_0\),然后按照上述步骤进行一次转移尝试,再让 \(T=d\cdot T\)。当 \(T<T_k\) 时模拟退火过程结束,当前最优解即为最终的最优解。

注意为了使得解更为精确,我们通常不直接取当前解作为答案,而是在退火过程中维护遇到的所有解的最优值。

题目

P1337 [JSOI2004] 平衡点 / 吊打XXX - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

很好的入门题,可以在这道题学习模拟退火的大致模板。

//The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
typedef double db;

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

const int N = 1100;

int n;
int x[N], y[N], w[N];
db ansx, ansy, dis;

db calc(db xx, db yy) {
    db res = 0;
    rep (i, 1, n, 1) {
        db dx = x[i] - xx, dy = y[i] - yy;
        res += sqrt(dx * dx + dy * dy) * w[i];
    }
    if (res < dis) {
        dis = res;
        ansx = xx;
        ansy = yy;
    }
    return res;
}

db Rand() {
    return (db)rand() / RAND_MAX;
}

void sa() {
    db t = 1e5;
    db nowx = ansx, nowy = ansy;
    while (t > 1e-3) {
        db curx = nowx + t * (Rand() * 2 - 1);
        db cury = nowy + t * (Rand() * 2 - 1);
        db delta = calc(curx, cury) - calc(ansx, ansy);
        if (exp(-delta / t) > Rand()) {
            nowx = curx;
            nowy = cury;
        }
        t *= 0.97;
    }
    rep (i, 1, 100, 1) {
        db curx = ansx + t * (Rand() * 2 - 1);
        db cury = ansy + t * (Rand() * 2 - 1);
        calc(curx, cury);
    }
}

void simulate() {
    while (clock() < CLOCKS_PER_SEC * 0.9) {
        sa();
    }
}

int main() {
    srand(time(0));
    n = read<int>();
    rep (i, 1, n, 1) {
        x[i] = read<int>(), y[i] = read<int>(), w[i] = read<int>();
        ansx += x[i], ansy += y[i];
    }
    ansx /= n, ansy /= n;
    dis = calc(ansx, ansy);
    simulate();
    printf("%.3lf %.3lf\n", ansx, ansy);
    return 0;
}

P2210 Haywire - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

也是一道很好的入门题。

//The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
typedef double db;

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

const int N = 15;

int n, ans = 1e9;
int pos[N];
vector<int> frd[N];

int calc() {
    int res = 0;
    rep (i, 1, n, 1) {
        for (int v : frd[i]) {
            res += abs(pos[i] - pos[v]);
        }
    }
    if (res / 2 < ans) {
        ans = res / 2;
    }
    return res / 2;
}

void sa() {
    db T = 1000;
    while (T > 0.001) {
        int x, y;
        do {
            x = rand() % n + 1;
            y = rand() % n + 1;
        } while (x == y);
        swap(pos[x], pos[y]);
        int res1 = calc();
        swap(pos[x], pos[y]);
        int res2 = calc();
        int delta = res1 / 2 - res2 / 2;
        if (delta <= 0 || (exp((db)delta / T) > (db)rand() / RAND_MAX)) {
            swap(pos[x], pos[y]);
        }
        T *= 0.97;
    }
}

void simulate() {
    while (clock() < CLOCKS_PER_SEC * 0.8) {
        sa();
    }
}

int main() {
    srand(time(0));
    n = read<int>();
    rep (i, 1, n, 1) {
        rep (j, 1, 3, 1) {
            frd[i].emplace_back(read<int>());
        }
    }
    rep (i, 1, n, 1) {
        pos[i] = i;
    }
    calc();
    simulate();
    cout << ans << '\n';
    return 0;
}

标签:ch,浅入,db,pos,笔记,int,模拟退火,read
From: https://www.cnblogs.com/yifan0305/p/17655036.html

相关文章

  • YTEZ校内数学集训笔记
    计数原理例题1:用一个大写的英文字母或一个阿拉伯数字给教室里的一个座位编号,总共能编出多少种不同的号码?或:\(a\wedgeb\)有\(a\)无\(b\)有\(b\)无\(a\)有\(a\)有\(b\)且:\(a\veeb\)有\(a\)有\(b\)非:\(┐a\)无\(a\)答案:英文字母共有26个,阿拉伯数......
  • 「学习笔记」meet in the middle(折半搜索)
    meetinthemiddle,适用于输入数据较小,但也没小到可以直接用暴力搜索通过的情况。主要的思想就是讲整个搜索过程分成两半进行,最后在将这两半的结果进行合并,对于搜索复杂度为\(O(a^b)\)的情况,meetinthemiddle可以将它优化为\(O(a^{\frac{b}{2}})\)。题目P5691[NOI2001]......
  • Unity.UI实习笔记
    1.点击Button弹出Panel功能SetActive:在场景中激活或停用对象。需要注意的是,停用父对象,那么场景中活跃的子对象也会停止,但子对象仍在其层次结构中保持活跃状态。例如停用父对象PhysicsDoor,子对象Door变灰,但在层次结构中仍旧保持活跃状态。引用自博客:https://blog.csdn.net/JF_......
  • MySQL基础笔记
    MySQLDDL:操作数据库和表DML:对数据进行增删改DQL:对数据进行查询DCL:对数据库进行权限管理数据库增删改查createdatabaseifnotexistsdb1;#如果数据库不存在才创建dropdatabaseifexistsdb1;#如果数据库存在才删除usedb1;#使用数据库selectDATABASE();#......
  • 【学习笔记】Manacher(马拉车)求回文子串
    点击查看目录目录参考资料与图片来源算法思路具体实现例题解题参考资料与图片来源参考博客我觉得这个博客讲的不好,他只讲看规律得到的结论,原因却不说,怪。参考博客2oi-wiki算法思路对于长度可能为奇可能为偶的情况,首先要预处理字符串,在每个字符左右增加一个无关字符#。......
  • 哈夫曼树学习笔记
    定义:1.二叉哈夫曼树:对于一个数列,构建一棵树上带权路径之和最小的二叉树(当然可以\(k\)叉)2.树上带权路径:每个叶子节点到根节点的路径上所有节点的点权\(w\)和到跟的路径长度\(dis\)的乘积之和简单来说,哈夫曼树满足\(\sumw_i\timesdis_i\)最小基本构造方法:前置知识(没做过也......
  • h5(html5)+css3前端笔记五
    盒子模型网页布局本质网页布局过程先准备好相关的网页元素,网页元素基本都是盒子Box。利用CSS设置好盒子样式,然后摆放到相应位置PS基本操作综合案例圆角边框盒子阴影文字阴影......
  • Selenium 学习笔记
    Selenium学习笔记Selenium框架是时下在Web领域中被使用得最为广泛的自动化测试工具集之一,它能帮助程序员们面向指定的Web前端应用快速地开发出自动化测试用例,且能实现跨各种平台、各种编程语言地在多种浏览器上开展测试工作。除此之外,由于该框架的学习曲线比较平缓,开发测试......
  • 算法工程师学习运筹学 笔记四 运输问题
    运输问题运输问题是一种特殊的线性规划问题,可以解决如类似把商品从一些产地运往另一些销售地使总运输成本最低的问题。由于其场景特殊性,找到比单纯型法更搞笑简便的算法,这便是研究运输问题的目的所在。下面是运输问题的思维导图 一、运输问题的数学模型对于单一商品的调度运......
  • 《程序员的自我修养》第四章学习笔记
     2015.12.26的笔记,放在了草稿箱。2023.8.24发布一下吧。第四章静态链接 先上两个文件//a.cexternintshared;intmain(){inta=100;swap(&a,&shared);}//b.cintshared=1;voidswap(int*a,int*b){*a^=*b^=*a^=*b;} 再......