模拟退火
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 <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>#define x first
#define y secondusing namespace std;typedef pair<double, double> 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("%.0lf\n", ans);return 0;
}
AcWing 2424. 保龄球
问题描述
-
问题链接：AcWing 2424. 保龄球
分析
-
本题需要求解最大值，相当于求全排列中的最大值。
-
每次我们可以随机交换两个轮次，计算交换前后的差距，更新答案。
代码
- C++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>#define x first
#define y secondusing namespace std;typedef pair<int, int> 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) 等于 实际轮次mif (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 <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>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("%.2lf\n", ans);return 0;
}
