OI-wiki 爬山算法完全指南：原理、实现、例题与调参实战

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. 正解写法不易掌握：常见于"毒瘤"计算几何题与数学题，即使知道函数单峰，也难以写出解析式或严谨的二分判定条件；
2. 状态维度过多：当问题本身维度很多时，难以容易地写出分治算法（例如下文的例 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

注意：更新时不能直接加上改变值，而要加上"改变值与温度的乘积"——这是算法能够收敛的关键。

三、例题 1：JSOI2008 球形空间产生器

原文档的第一道例题来自 JSOI2008 的经典问题（可在洛谷 P4035 找到原题）。

题目描述

给出 $n$ 维空间中的 $n+1$ 个点，已知它们在同一个 $n$ 维球面上，求出球心。 数据范围：$n \leq 10$，坐标绝对值不超过 $20000$。

为什么可以用爬山

球心到球面上每个点的距离都等于半径，因此"各点到球心距离的方差"是关于球心位置的函数，且很明显是单峰函数——偏离真实球心越远，距离越不均匀。这正好落在爬山算法适用范围内。

算法流程（5 步）

原文档给出了完整流程，这里逐一展开：

1. 初始化球心为重心：将球心初始化为各给定点各维坐标的平均值（即重心），以先验地靠近真实球心，减少后续枚举量；
2. 计算平均距离：对当前球心，求出每个已知点到该球心的欧氏距离的平均值$tot$；
3. 遍历所有点计算改变值：记录一个改变值 $cans$（每一维度分别记录）。对每个点，将其欧氏距离与平均值比较——大于平均值则把差值加入改变值，否则减去。原文档特别指出：实际上并不用判断大小，只要不考虑绝对值、直接用坐标计算即可（参考代码中直接累加(dis[i] - tot) * (f[i][j] - ans[j]) / tot）；
   • 形象理解：这个过程相当于把新球心"在空间里推来推去"——碰到太远的点就朝点方向拉一点，碰到太近的点就朝反方向推一点；
4. 乘温度更新球心：将 $cans$ 乘上当前温度 $t$，更新球心各维坐标，回到步骤 2 继续迭代；
5. 温度降到阈值以下时结束，输出最终球心。

关键点再次强调：更新球心时不能直接加改变值，而要加上改变值与温度的乘积。

仓库参考代码逐段解析

仓库中的完整实现位于 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

即 $n=2$，三个点 $(0,0)$、$(-1,1)$、$(1,0)$。对应的标准答案（hill-climbing_1.ans）为：

0.500 1.500

读者可以自行验证：点 $(0.5, 1.5)$ 到三个点的欧氏距离均为 $\sqrt{2.5}$，确实是这三点所在圆的圆心。程序在给定参数下能稳定收敛到该值。

四、例题 2：BZOJ 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.in）：

3 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）作为爬山算法的直接后继者进行介绍：模拟退火在爬山的基础上引入了以一定概率接受劣解的机制，允许算法在温度较高时"跳下山谷"，从而以较大概率逃离局部最优，逼近全局最优。读者可继续阅读 模拟退火 一文，了解两者在机制与适用场景上的差异。

七、总结与适用场景速查

配套资源索引：

• 例题 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