OI-wiki 爬山算法完全指南原理、实现、例题与调参实战【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读爬山算法Hill Climbing是 OI / ICPC 竞赛中一种简单而暴力的局部择优方法它利用目标函数的反馈信息在当前最优解的邻域内不断生成更优候选解。本文以 OI-wiki 的 hill-climbing.md 为主体结合仓库内 hill-climbing_1.cpp、hill-climbing_2.cpp 两份可编译参考代码及其配套测试数据系统讲解算法思想、温度降温机制、两道经典例题JSOI2008 球形空间产生器、BZOJ 3680 吊打 XXX的完整求解流程并给出多次爬山优化与参数调优的实战建议。读完本文你将能够在无法写出严格正解的计算几何/数学题中用爬山算法快速逼近最优解并理解它为何最终需要与模拟退火配合使用。一、算法思想一种局部择优的启发式搜索爬山算法是深度优先搜索的一种改进其核心是用反馈信息帮助生成解的决策。它解决的问题场景是当前无法直接推导出最优解但可以判断两个解中哪个更优。此时算法利用这一比较能力根据反馈信息不断生成新的可能解。用一句话概括整个迭代过程每次在当前找到的最优方案 $x$ 附近寻找一个新方案 $x$如果 $x$ 更优就转移到 $x$否则保持不变。这个过程天然要求目标函数具备一定的连续向好性质因此对于单峰函数爬山算法显然可行——它总能沿着坡面一路爬向唯一的峰顶。为什么不用三分一个很自然的疑问是既然单峰函数可以直接三分ternary search为什么还需要爬山原文档给出了两个关键理由这正是爬山算法的价值所在正解写法不易掌握常见于毒瘤计算几何题与数学题即使知道函数单峰也难以写出解析式或严谨的二分判定条件状态维度过多当问题本身维度很多时难以容易地写出分治算法例如下文的例 1 本可以用二分完成合法正解但高维球心的形式使二分实现繁琐此时可以通过非常暴力的计算得到最优解。致命缺陷陷入局部最优爬山算法的贪心本质决定了它只看眼前更优的方向。对于多峰函数算法很容易停在某个局部最优解上它认为周围没有比当前更好的点于是驻足即便远处存在更高的山峰。下图直观展示了这一情形绿色箭头是全局最优解而红色箭头是爬山算法可能找到并停驻的局部最优解。在 docs/misc/images/hill-climbing.png 对应的插图中可以看到只要起点位于错误的山坡贪心上升就会把算法带入谷顶的局部峰。这也是本文最后引入模拟退火的原因。二、具体实现温度参数与降温机制爬山算法的工程实现有一个重要细节引入温度参数与模拟退火类似但语义不同——爬山不包含接受劣解的随机跳变。直觉类比醉酒爬山的兔子原文档给出了一个经典类比爬山算法就像一只喝醉了的兔子在山上跳。它每次都朝着它所认为的更高的地方跳但这个判断往往只是个不准确的趋势它可能一次就跳到山顶也可能跳过头翻到对面去不过没关系兔子翻过去之后还会跳回来关键在于随着时间推移兔子逐渐冷静下来每次跳得更加谨慎、步长更小以收敛到合适的最优点。兔子逐渐变得清醒的过程就是降温过程——温度参数 $t$ 在爬山过程中不断减小从而控制每次更新的步长防止在最优解附近来回震荡、永远不收敛。降温参数怎么选降温参数是略小于 $1$ 的常数实践中一般在$$[0.985,\ 0.999]$$区间内选取。参数越接近 $1$降温越慢迭代次数越多、搜索越充分但耗时也越长参数越远离 $1$降温越快迭代提前结束结果可能粗糙。需要结合数据规模与时限折中选择。通用伪代码框架综合原文档与仓库参考代码爬山算法的通用流程可以归纳为初始化当前解 x通常取样本的重心/平均值减少搜索量 设定初始温度 t 与降温参数 rate while t 阈值: 根据目标函数计算反馈如梯度方向的累加量 cans x x cans * t # 用温度控制步长 t t * rate # 降温 输出 x注意更新时不能直接加上改变值而要加上改变值与温度的乘积——这是算法能够收敛的关键。三、例题 1JSOI2008 球形空间产生器原文档的第一道例题来自 JSOI2008 的经典问题可在洛谷 P4035 找到原题。题目描述给出 $n$ 维空间中的 $n1$ 个点已知它们在同一个 $n$ 维球面上求出球心。 数据范围$n \leq 10$坐标绝对值不超过 $20000$。为什么可以用爬山球心到球面上每个点的距离都等于半径因此各点到球心距离的方差是关于球心位置的函数且很明显是单峰函数——偏离真实球心越远距离越不均匀。这正好落在爬山算法适用范围内。算法流程5 步原文档给出了完整流程这里逐一展开初始化球心为重心将球心初始化为各给定点各维坐标的平均值即重心以先验地靠近真实球心减少后续枚举量计算平均距离对当前球心求出每个已知点到该球心的欧氏距离的平均值$tot$遍历所有点计算改变值记录一个改变值 $cans$每一维度分别记录。对每个点将其欧氏距离与平均值比较——大于平均值则把差值加入改变值否则减去。原文档特别指出实际上并不用判断大小只要不考虑绝对值、直接用坐标计算即可参考代码中直接累加(dis[i] - tot) * (f[i][j] - ans[j]) / tot形象理解这个过程相当于把新球心在空间里推来推去——碰到太远的点就朝点方向拉一点碰到太近的点就朝反方向推一点乘温度更新球心将 $cans$ 乘上当前温度 $t$更新球心各维坐标回到步骤 2 继续迭代温度降到阈值以下时结束输出最终球心。关键点再次强调更新球心时不能直接加改变值而要加上改变值与温度的乘积。仓库参考代码逐段解析仓库中的完整实现位于 hill-climbing_1.cpp核心结构如下check()函数——计算每个维度的修正量void check() { tot 0; for (int i 1; i n 1; i) { dis[i] 0; cans[i] 0; for (int j 1; j n; j) dis[i] (f[i][j] - ans[j]) * (f[i][j] - ans[j]); dis[i] sqrt(dis[i]); // 欧氏距离 tot dis[i]; } tot / (n 1); // 平均距离 for (int i 1; i n 1; i) for (int j 1; j n; j) cans[j] (dis[i] - tot) * (f[i][j] - ans[j]) / tot; // 欧氏距离差 * 差值贡献按维度累加 }main()函数——初始化与降温循环int main() { cin n; for (int i 1; i n 1; i) for (int j 1; j n; j) { cin f[i][j]; ans[j] f[i][j]; } for (int i 1; i n; i) ans[i] / (n 1); // 初始化为重心 for (double t 10001; t 0.0001; t * 0.99995) { // 不断降温 check(); for (int i 1; i n; i) ans[i] cans[i] * t; // 按温度缩放步长 } cout fixed setprecision(3); for (int i 1; i n; i) cout ans[i] ; }从源码可以看到几个典型的参数选择初始温度$t 10001$终止阈值$t \ge 0.0001$降温系数$0.99995$落在文档建议的 $[0.985, 0.999]$ 区间附近且更接近 1——因为维度可达 10 且坐标可达 $20000$需要更长迭代来精细收敛输出保留 3 位小数setprecision(3)。配套测试数据验证仓库在 docs/misc/examples/hill-climbing/hill-climbing_1.in 提供了可复现测试2 0.0 0.0 -1.0 1.0 1.0 0.0即 $n2$三个点 $(0,0)$、$(-1,1)$、$(1,0)$。对应的标准答案hill-climbing_1.ans为0.500 1.500读者可以自行验证点 $(0.5, 1.5)$ 到三个点的欧氏距离均为 $\sqrt{2.5}$确实是这三点所在圆的圆心。程序在给定参数下能稳定收敛到该值。四、例题 2BZOJ 3680 吊打 XXX第二道例题是 BZOJ 3680可在 hydro.ac 的 BZOJ 题库找到原题。题目描述求 $n$ 个点的带权类费马点。简单说就是给定平面上 $n$ 个带权点 $(x_i, y_i, w_i)$求一个点使得 $\sum_i w_i \cdot dist(P, P_i)$ 最小——即带权距离和最小点。由于引入了权重这是一类物理意义明确的最优化问题。解答思路套用爬山框架 物理知识原文档的解答非常简练框架类似用了点物理知识。具体而言目标函数$\sum_i w_i \cdot d_i$其中 $d_i$ 是候选点到第 $i$ 个点的欧氏距离物理直觉把每个已知点想象成用弹簧/绳子拉着候选点力的大小正比于权重方向指向各自已知点候选点的平衡位置就是合力为零的点即类费马点爬山迭代每一轮把所有点对候选点的拉力带权单位向量累加得到合力方向沿合力方向按当前温度步长移动候选点不断降温直至收敛。仓库参考代码解析完整实现见 hill-climbing_2.cpp核心的hillclimb()函数void hillclimb() { double t 1000; while (t 1e-8) { double nowx 0, nowy 0; for (int i 1; i n; i) { double dx x[i] - ansx, dy y[i] - ansy; double dis sqrt(dx * dx dy * dy); nowx (x[i] - ansx) * w[i] / dis; // 带权单位向量拉力 nowy (y[i] - ansy) * w[i] / dis; } ansx nowx * t, ansy nowy * t; // 按温度缩放步长移动 if (t 0.5) t * 0.5; // 前期快速降温 else t * 0.97; // 后期精细降温 } }这份代码展示了与原文档完全一致的框架但降温策略更具技巧性——分段降温初始温度 $t 1000$终止条件 $t 10^{-8}$当 $t 0.5$ 时每轮乘以 $0.5$快速逼近大致区域当 $t \le 0.5$ 时每轮乘以 $0.97$慢速精细收敛。这种先快后慢的降温策略在实践中非常有效前期大步长快速接近最优区域后期小步长精细逼近兼顾效率与精度。配套测试数据验证仓库提供了测试数据hill-climbing_2.in3 0 0 1 0 2 1 1 1 1即三个等权点 $(0,0)$、$(0,2)$、$(1,1)$ 求类费马点。标准答案hill-climbing_2.ans为0.577 1.000其中 $0.577 \approx 1/\sqrt{3}$恰好是等腰三角形费马点的经典位置验证了算法结果的正确性。五、优化多次爬山与全局最优单次爬山的质量高度依赖初始点位置。为了尽可能获取优秀答案原文档给出的标准优化手段是多次爬山修改初始状态随机或按不同策略生成多个不同的初始点修改降温参数使用不同的降温系数运行多轮修改初始温度改变搜索初期的步长规模记录全局最优解每轮爬山结束后将本轮结果与历史最优比较更新全局最优答案。伪代码如下全局最优 初始解 重复若干次: 以不同初始状态/参数运行爬山得到局部最优 x 若 x 优于全局最优: 全局最优 x 输出全局最优原文档同时给出了一个重要的实战警示多次爬山可能超时。因此在正式考试/比赛中务必手造大数据测试并调整参数轮数、初始温度、降温系数、终止阈值在运行时间与答案精度之间取得平衡。六、劣势为何要走向模拟退火爬山算法的劣势上文已经反复提及它容易陷入局部最优解。当目标函数不是单峰函数时这个劣势是致命的——贪心的只接受更优解策略使算法永远无法从局部峰下山去寻找更高的山峰。正因如此OI-wiki 将模拟退火Simulated Annealing作为爬山算法的直接后继者进行介绍模拟退火在爬山的基础上引入了以一定概率接受劣解的机制允许算法在温度较高时跳下山谷从而以较大概率逃离局部最优逼近全局最优。读者可继续阅读 模拟退火 一文了解两者在机制与适用场景上的差异。七、总结与适用场景速查维度说明适用前提能判断两个解孰优孰劣但难以写出严格正解目标函数最好近似单峰典型场景计算几何、数学题中的高维最优化如求球心、费马点核心机制沿反馈方向按温度 × 修正量步长迭代温度逐渐降低关键参数初始温度、降温系数建议 $[0.985, 0.999]$、终止阈值、迭代次数常用优化多次爬山 全局最优记录分段降温先快后慢主要劣势多峰函数下易陷入局部最优可通过模拟退火弥补配套资源索引例题 1 完整代码hill-climbing_1.cpp测试数据hill-climbing_1.in 与 hill-climbing_1.ans例题 2 完整代码hill-climbing_2.cpp测试数据hill-climbing_2.in 与 hill-climbing_2.ans算法插图docs/misc/images/hill-climbing.png相关算法文档模拟退火。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考