4362 字
22 分钟
模拟退火:赛场可读模板与使用场景

模拟退火:赛场可读模板与使用场景#

模拟退火就是反复尝试“小改一下当前方案”:改好了就接受,改差了也偶尔接受;开始时比较敢接受变差,后来越来越谨慎。整个过程另外记住见过的最好方案,最后输出它。

接受变差,是为了给后续更好的改变留机会。例如现在的任务分配暂时比较均衡,但需要先把一个任务挪走,才能再挪另一个任务,得到更好的分配。只允许每一步立即改善,可能一直走不出当前分配。

本节先用文字和具体例子说明,再给一份有中文注释、能直接编译的单文件程序。代码中的“代价”统一为越小越好。退火属于尝试寻找好方案的方法,不保证找到真正最优解;在必须得到精确答案的普通比赛里,不能仅凭多跑几次就认为一定能过。AtCoder 官方入门题解的比赛形式与退火说明

1. 什么时候值得考虑#

题目满足下面几件事,才适合继续考虑退火:

  1. 能先做出一个合法的完整方案。
  2. 给你一个方案,你能算出它有多好,例如总路程、完成时间、冲突数。
  3. 能只改变方案的一小部分,并且这种改变有机会让结果变好。
  4. 所有方案太多,暂时没有找到能保证最优的快速算法,而题目允许近似结果或按得分评价。

如果题目本来就能用排序、枚举、背包DP或其他确定算法解决,先用那些方法。尤其是“恰选几个数使总和最大”,排序后选最大的即可,不需要退火。

如果只有完整正确的方案得1分,其余全部得0分,大量尝试都没有区别,退火也很难判断该往哪里走。可以先看能否用“有几处冲突”“还违反几条要求”衡量接近程度,但最后仍必须检查输出是否合法。

2. 使用场景:分别存什么、算什么、改什么#

下面的“方案”就是你在代码中保存的一组数、一个排列、几个坐标或每件物品的归属。

场景一:从很多候选中恰好选几个#

例子。 从很多候选店址里选5个,让更多住户附近有店。两家店的覆盖可能重叠,因此不能只给每个店址独立打分后取前5名。

  • 保存什么:当前选中的店址,以及其余未选店址。
  • 怎样算好坏:统计住户被覆盖的总数;因为本模板比较的是“代价越小越好”,可以把覆盖数取负数作为代价。
  • 随机改哪里:移除一个已选店址,加入一个未选店址。始终还是5个。
  • 必须注意:不要只随机翻转一个“选/不选”标记,那样会改变选中数量。

本节完整代码就采用这种“一换一”的写法,不过评分换成“选中数的总和离目标多远”,方便手算和检查。

场景二:调整一个访问顺序或工作顺序#

例子。 所有城市都要访问一次,调整访问顺序,使总路程更短。

  • 保存什么:一个城市编号排列。
  • 怎样算好坏:按排列顺序累加相邻城市的距离;如果题目要求回到起点,还要加最后一个城市到起点的距离。
  • 随机改哪里:交换两个城市的位置,或把一段访问顺序反过来。
  • 必须注意:固定起点、固定终点等限制要保留;如果单行道导致来回距离不同,反转一段后,里面每条路的代价也要重新计算。

开始时直接重算整条路线最容易写对。以后需要加速,再研究哪些边真的发生了变化;不用一开始就背一个看不懂的距离差公式。

场景三:把任务分给几台机器,尽量均衡#

例子。 把若干任务分给3台机器,每个任务有耗时,希望最忙的机器也能尽快做完。

  • 保存什么:每个任务分给哪台机器。
  • 怎样算好坏:先累加每台机器的总耗时,再取其中最大值作为代价。
  • 随机改哪里:把一个任务移到另一台机器,或交换两台机器上的各一个任务。
  • 必须注意:若每台机器还有限额、不能空着或必须恰好分到几件任务,新方案也必须满足这些要求。

“让最长耗时最小”和“让各组耗时的平方和最小”是不同目标,要按题目要求评分,不能随便互换。若改动先破坏当前方案再检查,拒绝时很容易忘记恢复;本节使用候选副本,被拒绝后直接丢弃。

场景四:在一个区域里找一个合适的位置#

例子。 在给定矩形里放一个点,希望它离最近的障碍点尽可能远。

  • 保存什么:当前横坐标和纵坐标。
  • 怎样算好坏:算出它到每个障碍点的距离,取最小距离;希望这个距离越大越好,因此评分时取负数。
  • 随机改哪里:横坐标、纵坐标各随机加减一点。
  • 必须注意:点不能跑出矩形;有禁入区域时也要检查。越界的候选可以直接丢弃,不必强行挤到边界。

坐标改动幅度和温度分开设。温度决定“多大的代价变差还能容忍”,坐标幅度决定“这一跳能移动多远”。例如区域宽1000,却每次只移动0.001,可能跑很久也走不到别处。

也不是所有找位置的题都需要退火:一条直线上最小化距离和,可以找中位数;最小化平方距离和,可以找平均位置;覆盖所有点的最小圆,本书有专门算法。先识别这些结构。

场景五:调整布局,减少冲突#

例子。 在棋盘上摆放若干对象,希望相互冲突的对数尽量少。

  • 保存什么:每个对象的位置。
  • 怎样算好坏:统计冲突对数,越少越好。
  • 随机改哪里:移动一个对象,或交换两个对象的位置。
  • 必须注意:不能放在禁用格、不能重叠等硬性要求,要在生成候选时检查。不能把“冲突还剩1对”当成已经满足无冲突要求。

如果只移动一个对象总是无法改善,可以尝试同时移动少量对象,但每次都把整个布局随机重做,通常又很难保留已经得到的好部分。

场景六:方案要经过一段模拟才能评分#

例子。 修改任务顺序后,要按题目规则模拟执行,才知道总完成时间。

  • 保存什么:当前执行顺序或操作安排。
  • 怎样算好坏:完整模拟得到的完成时间或题目给定得分。
  • 随机改哪里:交换少量位置,或者只取出一小段任务重新安排。
  • 必须注意:一次评分如果很慢,能尝试的次数就少。先估算运行量,再决定跑几轮;不要只把降温系数改得更接近1。

“改一小部分,再完整检查候选”是容易写对的起点。官方入门题解也建议,把以后加速用的局部评分与完整重算对照检查。AtCoder 官方入门题解,第4节

3. 接受规则:只需要看当前、候选、最好这三个词#

假设代价越小越好:

  • 候选代价比当前小,接受。
  • 候选代价和当前相同,也可以接受,给下一次改变换一个起点。
  • 候选代价比当前大,才按概率决定是否接受。
  • 一旦遇到比历史最好还好的方案,就把它单独保存。

一定和当前比较。 假设最好代价是0,当前代价是10,候选代价是8。8比当前的10好,应当直接接受;不要因为它比历史最好的0差,就把它误判成一次变差。

代码使用下面这句计算“接受变差”的概率:

exp(-变差幅度 / 温度)

exp 是 C++ 的指数函数,这里你只需要掌握结果的变化方向:变差幅度越大,概率越小;温度越高,概率越大。注意前面的负号,且只在候选更差的分支计算。GSL 官方文档中的接受规则

例如当前代价100、候选代价110,变差了10:

温度 大约有多大概率接受
100 90%
10 37%
1 0.005%

随机生成一个0到1的小数,若它小于上面算出的概率,就接受。rand() 的原始返回值是整数,不能直接拿来和这个概率比较。

4. 参数怎样在现场调#

代码里有四个参数需要先看:

参数 示例设置 改动后有什么影响
开始温度 1000 越大,开始时越愿意接受变差
停止温度 0.01 越小,后期越不容易接受变差
每步降温系数 0.995 每尝试一次温度乘它;越接近1,尝试次数越多
重启次数 5 从几个不同起点分别跑,始终保存全程最好方案

这些只是示例值。先看看随机小改一次时,代价通常会变差多少:如果常常变差几万,开始温度1000可能太低;如果通常只变差1,开始温度1000就会非常宽松。不能把同一组数当作所有题的固定答案。

用当前参数,每轮大约尝试2300次,5轮共约1.2万次。本模板每次复制整个方案、重新计算代价,所用时间还要乘上方案大小。如果题目有很多数据组,所有数据组的运行量也要相加。

重启不是继续上一轮。 本例第一轮从原顺序开始,后面打乱顺序,换新的初始选择,再恢复开始温度。随机数生成器只初始化一次,不要每次重启都用同一种子重新创建,否则可能把同一条搜索过程重复跑几遍。

5. 完整模板在解决什么问题#

例题:给出若干整数,恰好选出指定个数,让它们的总和尽量接近目标。

输入:

4 2 14
2 5 9 12

意思是从4个数里选2个,希望总和接近14。可以选2和12,也可以选5和9,误差都是0。输出第一行是找到的最小误差,第二行是选中数的原下标,从1开始;例如:

0
1 4

不同合法选择的输出顺序可以不同。误差必须和输出的选择对应。

这道例题只是方便展示退火的完整过程:实际遇到选数题,仍应先看能否枚举或用背包DP准确解决。本程序不把“运行结束”当成“已经证明最优”。

方案用一个下标排列保存:前面指定数量的位置表示选中,后面的位置表示未选中。例如排列 0 3 1 2 表示选中原下标0和3,也就是数2和12。随机从前半部分和后半部分各取一个位置交换,选中的数量始终不变。

输入前提:个数不能为负,选取数量在0到总个数之间;所有输入数的绝对值之和,再加目标的绝对值,不超过 10^15。代码按这个范围使用 long long,避免求和、做差和取绝对值溢出。

6. 带中文注释的完整单文件代码#

代码里的三处“换题改这里”分别对应:计算代价、调整温度、生成一次合法的小改动。更换方案的数据结构时,也要同步修改初解和输出。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// 完整例题:从 n 个整数中恰好选 k 个,让它们的总和尽量接近 target。
// 输入:n k target,下一行 n 个整数。
// 输出:找到的最小误差,下一行输出选中的原下标(从 1 开始)。
// 数值前提:所有数的绝对值之和,再加上 target 的绝对值,不超过 10^15。
// 因此下面的整数求和、相减和取绝对值都不会溢出。
int n, k;
ll target;
vector<ll> value;
// 随机数生成器只初始化一次。固定种子方便本地复现。
mt19937 rng(20261025);
uniform_real_distribution<double> random01(0.0, 1.0);
vector<int> best_order; // 搜索过程中,见过的最好方案。
ll best_cost = LLONG_MAX;
// 【换题改这里 1】如何计算一个方案的代价。这里代价越小越好。
// order 存所有数的原下标,前 k 个位置表示选中,后面表示未选中。
ll calculate_cost(const vector<int>& order) {
ll sum = 0;
for (int i = 0; i < k; ++i) sum += value[order[i]];
return abs(sum - target);
}
void simulated_annealing(vector<int> current_order) {
ll current_cost = calculate_cost(current_order);
if (current_cost < best_cost) {
best_cost = current_cost;
best_order = current_order;
}
// 全不选或全选时,选中的集合已经固定,不存在“一换一”的改变。
// 先返回,避免下面构造空范围的随机数分布。
if (k == 0 || k == n) return;
uniform_int_distribution<int> pick_selected(0, k - 1);
uniform_int_distribution<int> pick_unselected(k, n - 1);
// 【换题改这里 2】根据一次变差的常见幅度调温,下面只是示例参数。
const double start_temperature = 1000.0; // 大:开始时较愿意接受变差。
const double stop_temperature = 0.01; // 小:结束前主要保留改善。
const double cooling = 0.995; // 每尝试一次,温度乘这个数。
for (double temperature = start_temperature;
temperature > stop_temperature;
temperature *= cooling) {
// 复制一份候选。若不接受它,直接丢弃,当前方案就不会被改坏。
vector<int> candidate_order = current_order;
// 【换题改这里 3】随机小改一次,并保证新方案仍然合法。
// 从选中区和未选中区各取一个位置,交换后仍然恰选 k 个数。
int selected_pos = pick_selected(rng);
int unselected_pos = pick_unselected(rng);
swap(candidate_order[selected_pos], candidate_order[unselected_pos]);
ll candidate_cost = calculate_cost(candidate_order);
// 必须和“当前方案”比较,不能和 best_cost 比较。
bool accept_candidate = candidate_cost <= current_cost;
if (!accept_candidate) {
ll worse_by = candidate_cost - current_cost; // 到这里一定为正。
// exp 是 C++ 的指数函数。参数越负,返回的概率越接近 0。
// 变差越多,接受概率越低;温度越高,接受概率越高。
double probability = exp(-static_cast<double>(worse_by) / temperature);
accept_candidate = random01(rng) < probability;
}
if (accept_candidate) {
current_order = std::move(candidate_order);
current_cost = candidate_cost;
// 接受变差只是为了继续探索,最好方案必须另外保存。
if (current_cost < best_cost) {
best_cost = current_cost;
best_order = current_order;
}
}
// 没接受:候选副本被丢弃,不需要再交换回去。
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> n >> k >> target)) return 0;
if (n < 0 || k < 0 || k > n) return 0;
value.resize(n);
for (ll& x : value) cin >> x;
// order = [0, 1, ..., n-1],第一次从原顺序开始。
vector<int> order(n);
iota(order.begin(), order.end(), 0);
const int restarts = 5;
for (int run = 0; run < restarts; ++run) {
// 后面几次打乱顺序,换一个起点;沿用同一个随机数生成器。
if (run > 0) shuffle(order.begin(), order.end(), rng);
simulated_annealing(order);
}
// 输出 best_order 对应的代价和方案,不输出最后停留的 current_order。
cout << best_cost << '\n';
for (int i = 0; i < k; ++i) {
if (i) cout << ' ';
cout << best_order[i] + 1;
}
cout << '\n';
}

在模板目录编译:

Terminal window
g++ -std=c++17 -O2 -Wall -Wextra ready/annealing_readable.cpp -o /tmp/cp-annealing
/tmp/cp-annealing

7. 改成自己的题时,按这个顺序检查#

  1. 先确定代码里保存什么。例如选中的下标、城市顺序、每件物品的组别、点的坐标。
  2. 写一个完整评分函数,能手算的小例必须和它一致。若原目标越大越好,可用它的相反数作为代价;取负前先检查类型范围。
  3. 写一次随机小改动,确认它不会违反恰选数量、位置范围、容量等限制。非法候选直接丢弃,并继续降温。
  4. 始终比较候选与当前,接受后同时更新当前方案和当前代价;遇到全程最好时,把方案与代价一起保存。
  5. 先保持完整重算的写法。确实太慢时,再只计算受改动影响的部分,并与完整评分对照。

例如改成城市路线:方案仍然可以是编号排列,评分改成总路程,小改动改为交换两个允许移动的位置,输出改为访问顺序。改成点坐标:方案要改成横纵坐标,评分按题目要求计算,随机改动改为坐标加减,并检查范围。

这份程序会修改全局的最好方案;若改为多组数据,每组开始前重置 best_cost 并清空 best_order。

相关:算法竞赛编译器预处理、算法竞赛数学套路、算法竞赛个人易错点。

模拟退火:赛场可读模板与使用场景
https://sanzenin.top/posts/obsidian/模拟退火的适用情形与分类模板/
作者
Sanzenin 凪
发布于
2026-10-25
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取