[模板]模拟退火/SCOI传送带
模拟退火(Generated by deepseek-r1)
模拟退火算法是一种基于物理退火过程的启发式优化算法，其核心思想是通过概率性接受次优解来跳出局部最优，逐步逼近全局最优解。以下是其核心流程的简要讲解：
[*]初始化参数
[*]初始温度 $ T_0 $：设置较高温度（如 $ 10^5 $ ），确保算法在早期有足够能量跳出局部最优。
[*]初始解：随机生成或启发式生成一个初始解（如随机路径、参数组合）。
[*]降温系数 $ \alpha $（如 0.95~0.99）：控制温度下降速度，通常接近 1 以保证缓慢降温。
[*]终止条件：设定最低温度 $ T_{\text{min}} $ 或最大迭代次数。
[*]迭代过程（外循环）
在每个温度 $ T $ 下，执行以下步骤直到满足终止条件：
(1) 内循环（状态扰动与评估）
[*]生成新解：通过随机扰动当前解（如交换路径中的两个点、调整参数值）产生候选解。
[*]计算目标函数差 $ \Delta E $：比较新解与当前解的目标函数值差（例如路径长度、误差值）。
(2) Metropolis 接受准则
[*]接受更优解：若 $ \Delta E < 0 $（新解更优），直接接受新解。
[*]概率性接受劣解：若 $ \Delta E \geq 0 $，以概率 $ P = \exp(-\Delta E / T) $ 接受新解。通过生成随机数与 $ P $ 比较决定是否接受劣解，避免陷入局部最优
(3) 降温
[*]温度更新：按降温函数降低温度，例如指数降温 $ T_{k+1} = \alpha \cdot T_k $。
[*]终止与输出
[*]终止条件：当温度降至 $ T_{\text{min}} $ 或目标函数值不再显著变化时结束算法。
[*]输出最优解：返回当前记录的最优解。
关键特点
[*]概率性搜索：通过接受劣解的策略，平衡全局探索（高温阶段）与局部开发（低温阶段）。
[*]参数敏感：初始温度、降温速率、内循环次数等参数需根据问题调整，直接影响收敛速度和结果质量。
应用场景
[*]组合优化：如旅行商问题（TSP）、调度问题。
[*]连续优化：如函数极值求解、神经网络训练。
通过上述流程，模拟退火能够在复杂解空间中高效搜索全局最优解，适用于多种非凸优化问题。
总的来说原理是对的，但是解题时容易出现玄学错误，使用IOI这种赛制的比赛中
SCOI传送带
不得不说有AI还是很方便，注释都不用写
连代码AI生成了都是一遍过
点击查看代码#includeusing namespace std;// 定义一个类型别名pdd，它是一个pair类型，用于表示二维平面上的点 typedef pair pdd;// 定义宏x和y，分别表示pair的第一个和第二个元素，方便访问点的坐标 #define x first #define y second// 计算两点之间的欧几里得距离 // 参数a和b是两个pdd类型的点 // 返回值是两点之间的距离 double dis(pdd a, pdd b) { // 根据欧几里得距离公式计算距离，即sqrt((x1 - x2)^2 + (y1 - y2)^2) return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2)); }// 计算从点a到点b，点c到点d的路径上，按照一定比例移动所需的总时间 // 参数a和b表示第一条线段的起点和终点 // 参数c和d表示第二条线段的起点和终点 // 参数t表示在第一条线段上移动的比例 // 参数s表示在第二条线段上移动的比例 // 参数p表示在第一条线段上的移动速度 // 参数q表示在第二条线段上的移动速度 // 参数r表示从第一条线段上的某点到第二条线段上某点的移动速度 // 返回值是总时间 double caltime(pdd a, pdd b, pdd c, pdd d, double t, double s, double p, double q, double r) { pdd e, f; // 计算第一条线段上按照比例t的点e的坐标 e.x = a.x + (b.x - a.x) * t; e.y = a.y + (b.y - a.y) * t; // 计算第二条线段上按照比例s的点f的坐标 f.x = c.x + (d.x - c.x) * s; f.y = c.y + (d.y - c.y) * s; // 根据时间 = 距离 / 速度，计算总时间 return dis(a, e) / p + dis(e, f) / r + dis(f, d) / q; }// 生成一个之间的随机小数 // 返回值是一个之间的随机小数 double pro() { // rand()函数生成一个随机整数，除以RAND_MAX得到一个之间的随机小数 return (double)rand() / RAND_MAX; }// 使用模拟退火算法求解从点a到点b，点c到点d的最短时间路径 // 参数a和b表示第一条线段的起点和终点 // 参数c和d表示第二条线段的起点和终点 // 参数p表示在第一条线段上的移动速度 // 参数q表示在第二条线段上的移动速度 // 参数r表示从第一条线段上的某点到第二条线段上某点的移动速度 // 返回值是最短时间 double solve(pdd a, pdd b, pdd c, pdd d, double p, double q, double r) { // 随机初始化第一条线段和第二条线段上的移动比例t和s double t = pro(), s = pro(); // 计算初始的总时间 double best = caltime(a, b, c, d, t, s, p, q, r); // 模拟退火算法的初始温度 for (double temp = 1e5; temp > 1e-5; temp *= 0.999) { // 在当前t的基础上，随机扰动得到新的t值，并确保在范围内 double nt = max(0.0, min(1.0, t + pro() * 0.2 - 0.1)); // 在当前s的基础上，随机扰动得到新的s值，并确保在范围内 double ns = max(0.0, min(1.0, s + pro() * 0.2 - 0.1)); // 计算新的总时间 double ntime = caltime(a, b, c, d, nt, ns, p, q, r); // 如果新的总时间更短，或者满足一定的概率接受更差的解（模拟退火的特性） if (ntime < best || exp(best - ntime) / temp > pro()) { // 更新t和s的值 t = nt; s = ns; // 更新最短时间 best = min(best, ntime); } } return best; }int main() { // 初始化随机数种子，使用当前时间作为种子，确保每次运行程序时生成的随机数不同 srand(time(0)); pdd a, b, c, d; double p, q, r; // 从标准输入读取第一条线段的起点和终点的坐标 cin >> a.x >> a.y >> b.x >> b.y; // 从标准输入读取第二条线段的起点和终点的坐标 cin >> c.x >> c.y >> d.x >> d.y; // 从标准输入读取三条路径的移动速度 cin >> p >> q >> r; // 输出最短时间，保留两位小数 cout
页:
[1]