模拟退火

模拟退火 模拟退火 1. 模拟退火原理

原理

• 模拟退火：是一种随机算法，用于解决最优化问题。要求求解的问题对应的函数要有连续性。
• 模拟退火算法是模拟物理过程，有如下参数：

（1）温度t：即步长。分为初始温度和终止温度，对应代码中就是初始搜索范围和终止搜索的范围。

（2）衰减系数：每次搜索范围减小的比例，是(0, 1)中的一个数，可以取0.999，需要手动调节。

• 在每次迭代的过程中，我们在给定步长区间内随机一个新点，令dt = f(新点)-f(当前点)，如果求函数极小值的话，分为两种情况：

（1）dt<0，则跳到新点；

（2）dt>0，则以一定该概率跳到该点，且dt越大，跳过去的概率越低。

• 跳过去的概率值可以取为 e − d t / t e^{-dt/t} e−dt/t。

• 模拟退火的过程可能会收敛到局部最优解，但是这个过程我们可以做多次，这样收敛到局部最优解的概率就很小了。比如达到局部最优解的概率是0.99，则我们做1000次，达到局部最优解的概率是： 0.9 9 1000 ≈ 4.3 × 1 0 − 5 0.99^{1000} approx 4.3 times 10^{-5} 0.991000≈4.3×10−5。

2. AcWing上的模拟退火题目 AcWing 3167. 星星还是树

问题描述

• 问题链接：AcWing 3167. 星星还是树

分析

• 本题求解的这个点是费马点，即到所有点距离和最小的点。如果是一维的，排个序找中位数即可。

• 可以证明，这个函数是个凸函数，具有连续性。使用模拟退火求解即可。

代码

• C++

#include 
#include 
#include 
#include 
#include 

#define x first
#define y second

using namespace std;

typedef pair PDD;

const int N = 110;

int n;
PDD q[N];
double ans = 1e8;

// 返回[l, r]之间的随机小数
double rand(double l, double r) {
    return (double)rand() / RAND_MAX * (r - l) + l;
}

double get_dist(PDD a, PDD b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

// 计算p到给定点的距离和
double calc(PDD p) {
    double res = 0;
    for (int i = 0; i < n; i++)
        res += get_dist(p, q[i]);
    ans = min(ans, res);
    return res;
}

void simulate_anneal() {
    
    PDD cur(rand(0, 10000), rand(0, 10000));
    for (double t = 1e4; t > 1e-4; t *= 0.9) {
        PDD np(rand(cur.x - t, cur.x + t), rand(cur.y - t, cur.y + t));
        double dt = calc(np) - calc(cur);
        if (exp(-dt / t) > rand(0, 1)) cur = np;
    }
}

int main() {
    
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%lf%lf", &q[i].x, &q[i].y);
    
    for (int i = 0; i < 100; i++) simulate_anneal();
    
    printf("%.0lfn", ans);
    
    return 0;
}

AcWing 2424. 保龄球

问题描述

• 问题链接：AcWing 2424. 保龄球

分析

• 本题需要求解最大值，相当于求全排列中的最大值。

• 每次我们可以随机交换两个轮次，计算交换前后的差距，更新答案。

代码

• C++

#include 
#include 
#include 
#include 
#include 

#define x first
#define y second

using namespace std;

typedef pair PII;

const int N = 55;

int n, m;  // n: 规定的轮次  m: 实际的轮次
PII q[N];
int ans;

int calc() {
    
    int res = 0;
    for (int i = 0; i < m; i++) {
        res += q[i].x + q[i].y;
        if (i < n) {
            if (q[i].x == 10) res += q[i + 1].x + q[i + 1].y;
            else if (q[i].x + q[i].y == 10) 
                res += q[i + 1].x;
        }
    }
    ans = max(ans, res);
    return res;
}

void simulate_anneal() {
    
    for (double t = 1e4; t > 1e-4; t *= 0.99) {
        auto a = rand() % m, b = rand() % m;
        int x = calc();
        swap(q[a], q[b]);
        // 交换后进行的轮次 n + (q[n - 1].x == 10)   等于   实际轮次m
        if (n + (q[n - 1].x == 10) == m) {
            int y = calc();
            int dt = y - x;
            // 如果dt>0, 则不用恢复原状
            if (exp(dt / t) < (double)rand() / RAND_MAX)
                swap(q[a], q[b]);
        } else swap(q[a], q[b]);
    }
}

int main() {
    
    cin >> n;
    for (int i = 0; i < n; i++) cin >> q[i].x >> q[i].y;
    if (q[n - 1].x == 10) m = n + 1, cin >> q[n].x >> q[n].y;
    else m = n;
    
    // for (int i = 0; i < 100; i++) simulate_anneal();
    
    // 卡时写法: 卡0.1秒
    while ((double)clock() / CLOCKS_PER_SEC < 0.1) simulate_anneal();
    
    cout << ans << endl;
    
    return 0;
}

AcWing 2680. 均分数据

问题描述

• 问题链接：AcWing 2680. 均分数据

分析

• 这里可以随机将这些数据放置到某个组中，为了使得收敛的速度更快，可以采用贪心的策略将n个数据放置到m个组中。

• 每次找到和最小的组，将该数据放到该组中。

代码

• C++

#include 
#include 
#include 
#include 

using namespace std;

const int N = 25, M = 10;

int n, m;
int w[N], s[M];  // s:存储每组和
double avg;
double ans = 1e9;

double calc() {
    
    // 贪心给每个数据分组
    memset(s, 0, sizeof s);
    for (int i = 0; i < n; i++) {
        int k = 0;
        for (int j = 0; j < m; j++)
            if (s[j] < s[k])
                k = j;
        s[k] += w[i];
    }
    
    double res = 0;
    for (int i = 0; i < m; i++)
        res += (s[i] - avg) * (s[i] - avg);
    res = sqrt(res / m);
    ans = min(ans, res);
    return res;
}

void simulate_anneal() {
    
    random_shuffle(w, w + n);
    
    for (double t = 1e4; t > 1e-4; t *= 0.99) {
        double x = calc();
        int a = rand() % n, b = rand() % n;
        swap(w[a], w[b]);
        double y = calc();
        double dt = y - x;
        if (exp(-dt / t) < (double)rand() /RAND_MAX)
            swap(w[a], w[b]);
    }
}

int main() {
    
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> w[i];
        avg += w[i];
    }
    avg /= m;
    
    for (int i = 0; i < 10; i++) simulate_anneal();
    
    printf("%.2lfn", ans);
    
    return 0;
}