爬山算法

What · 是什么

爬山算法（hill climbing）是一种局部择优的启发式搜索：在当前最优解 x 的邻域内生成候选解 x'，若 x' 比 x 更优则转移到 x'，否则保持 x。它是深度优先搜索的启发式改进，利用反馈信息（目标函数值）引导搜索。对单峰函数（只有一个峰）保证收敛到最优；对多峰函数极易陷入局部最优。竞赛中常用于无法写出精确解的毒瘤计算几何/数学题（如求球心、费马点），实现上通常引入温度参数——初始步长大，随迭代次数逐渐缩小（类比兔子醉酒爬山逐渐清醒），以便先粗后细地逼近最优。

Why · 为什么

How · 实现

伪代码

def hill_climb(初始解 x0):
    x = x0
    T = 初始温度(大步长)          # 例如 10000
    d = 0.99                       # 降温系数 [0.985,0.999]
    while T > 终止阈值:
        x' = 在 x 附近随机生成候选  # 步长与 T 成正比
        if f(x') 更优:
            x = x'
        T = T * d
    return x
# 多次运行取全局最优
best = max(hill_climb(随机初始) for _ in range(k))

Python 实现

import math
import random


def hill_climb_sphere(points, iters=3000):
    """爬山求 n 维点集的重心/费马式最优点(示例: 最小化到各点距离平方和 => 重心).
    points: list of (x1,...,xn)
    返回最优点的坐标(近似). 用温度衰减缩小步长.
    """
    n_dim = len(points[0])
    # 初始解: 重心
    x = [sum(p[i] for p in points) / len(points) for i in range(n_dim)]

    def f(px):
        return sum((px[i] - p[i]) ** 2 for p in points for i in range(n_dim))

    T = 100.0
    while T > 1e-6:
        # 邻域: 每维加一个高斯/均匀扰动, 幅度与温度相关
        x2 = [x[i] + random.uniform(-1, 1) * T for i in range(n_dim)]
        if f(x2) < f(x):
            x = x2
        T *= 0.995
    return x


def hill_climb_unimodal():
    """单峰函数 f(x)=-(x-3.7)^2, 从远处出发应爬到 x≈3.7"""
    x = random.uniform(-50, 50)
    T = 50.0
    while T > 1e-4:
        x2 = x + random.uniform(-1, 1) * T
        if -(x2 - 3.7) ** 2 > -(x - 3.7) ** 2:
            x = x2
        T *= 0.995
    return x


if __name__ == "__main__":
    # 单峰验证
    random.seed(0)
    xs = [hill_climb_unimodal() for _ in range(50)]
    assert all(abs(v - 3.7) < 0.3 for v in xs), xs

    # 球心: 一个 n 维球面上的点集, 最小化到各点距离的平方差 => 重心近似
    # 构造: 单位球心 (1,2), 半径 3, 取 8 个点
    center = (1.0, 2.0)
    points = []
    for ang in range(8):
        a = ang * 3.14159 / 4
        points.append((center[0] + 3 * math.cos(a), center[1] + 3 * math.sin(a)))
    # 用欧氏距离平方和最小化 => 重心 (1,2)
    res = hill_climb_sphere(points)
    assert abs(res[0] - 1.0) < 0.5 and abs(res[1] - 2.0) < 0.5, res

    print("hill-climbing tests passed")

易错点

• 只接受更优解 => 必困局部最优，多峰问题慎用
• 温度系数太小收敛过快会停在半山腰；太大则来回震荡不收敛
• 单峰函数的判断（可三分/解析求解时优先精确解）
• 初始点选择对结果影响大，多随机初值取最优
• 步长与函数尺度不匹配（量级悬殊）时需归一化坐标

例题

信源

• OI Wiki✓ https://oi-wiki.org/misc/hill-climbing/
• Wikipedia✓ https://en.wikipedia.org/wiki/Hill_climbing