2. 爬山算法：基本原理、实现步骤、优缺点分析

爬山算法，说白了就是「往高处走」。你站在一个山坡上，闭着眼睛，只靠脚底的感觉，哪边高就往哪边迈一步。这就是爬山算法的核心思路——每一步都选择让评价函数值提升最大的方向。

我在做自动对焦的初期，第一个想到的就是它。原因很简单：它够快，够直接。你想想看，对焦评价函数（比如 Brenner 梯度、Tenengrad 方差）在理想情况下就是一个单峰函数，爬山算法正好能快速爬到峰顶。

2.1 基本原理

爬山算法属于局部搜索算法。它不关心全局地图长什么样，只盯着当前点的邻居，挑最好的那个走。

数学上可以这样描述：

• 设当前镜头位置为 \( x_t \)，对应的对焦评价值为 \( f(x_t) \)
• 在 \( x_t \) 的邻域内采样，得到 \( f(x_t + \Delta) \) 和 \( f(x_t - \Delta) \)
• 如果 \( f(x_t + \Delta) > f(x_t) \)，则向正方向移动一步
• 如果 \( f(x_t - \Delta) > f(x_t) \)，则向负方向移动一步
• 如果两边都不比当前好，就认为到达了峰值，停止搜索

2.2 实现步骤

我习惯把爬山算法的实现拆成 5 步。每一步都有坑，我一个个说。

1. 初始化：确定起始位置 \( x_0 \)。通常从当前镜头位置开始，或者从对焦范围的中点开始。我建议从靠近近端的位置起步，因为大多数镜头在近端到中段的梯度变化更明显。
2. 设定步长：步长 \( \Delta \) 决定了每次移动的物理距离。步长太大容易跳过峰值，步长太小收敛太慢。我在项目中一般先用大步长粗搜，再用小步长精搜。
3. 计算当前评价值：在当前镜头位置采集一帧图像，计算对焦评价函数值 \( f(x_t) \)。
4. 探索邻居：分别向正方向和负方向移动步长 \( \Delta \)，采集图像并计算评价值 \( f(x_t + \Delta) \) 和 \( f(x_t - \Delta) \)。
5. 决策与移动：比较三个值（当前、正向、负向），选择最大的那个方向移动。如果当前值最大，则停止；否则重复步骤 3-5。

// 伪代码：爬山算法实现
function hillClimbing(startPos, stepSize, maxIter) {
    let currentPos = startPos;
    let currentVal = evaluate(currentPos);
    
    for (let i = 0; i < maxIter; i++) {
        let forwardPos = currentPos + stepSize;
        let backwardPos = currentPos - stepSize;
        
        let forwardVal = evaluate(forwardPos);
        let backwardVal = evaluate(backwardPos);
        
        if (forwardVal > currentVal && forwardVal >= backwardVal) {
            currentPos = forwardPos;
            currentVal = forwardVal;
        } else if (backwardVal > currentVal) {
            currentPos = backwardPos;
            currentVal = backwardVal;
        } else {
            // 到达峰值
            break;
        }
    }
    return currentPos;
}

2.3 优缺点分析

爬山算法不是万能的。我用一张表把它的优缺点说清楚。

维度	优点	缺点
速度	收敛快，每次只比较 2-3 个邻居	步长选择不当会震荡或跳过峰值
实现复杂度	代码简单，不需要复杂的数据结构	对评价函数的噪声敏感
全局性	在单峰场景下能精确找到峰值	容易陷入局部极值，无法处理多峰
适应性	适合静态场景、光照稳定的环境	动态场景下（如运动物体）容易误判
资源消耗	内存占用极低，适合嵌入式	每次移动都需要采集图像，功耗较高

2.4 爬山算法的变体

标准爬山算法太「耿直」了。在实际项目中，我常用下面几种变体来弥补它的不足。

• 随机爬山法：每次从多个随机方向中选择一个，而不是只检查正负两个方向。适合评价函数有轻微噪声的场景。
• 首选爬山法：只要找到一个比当前好的方向就立刻移动，不再比较其他方向。速度更快，但精度略低。
• 模拟退火爬山法：以一定概率接受比当前差的解，避免陷入局部极值。温度参数需要仔细调，我一般从 0.5 开始衰减。
• 自适应步长爬山法：根据梯度大小动态调整步长。梯度大时用大步快速接近，梯度小时用小步精细搜索。

2.5 爬山算法的适用场景

你可能会问：爬山算法这么简单，真的能用吗？

能，但要看场景。我总结了几条经验：

• 适合：微距对焦、文档扫描、固定场景监控。这些场景下评价函数通常是单峰的。
• 不适合：运动物体跟踪、多目标对焦、强光/弱光环境。这些场景下评价函数容易出现多峰或噪声。
• 折中方案：先用全局搜索（比如 Fibonacci 搜索）找到大致位置，再用爬山算法做精细调整。我在工业相机项目中就是这么做的，效果不错。

2.6 爬山算法的流程示意图

下面这张 SVG 图展示了爬山算法的完整流程。你可以看到从初始化到收敛的每一步。

2.7 总结

爬山算法是自动对焦搜索策略的「入门必修课」。它简单、快速、容易实现，但局限性也很明显。我个人建议：不要把它当作万能方案，而是作为复杂策略中的一个基础模块。

在实际项目中，我通常把爬山算法和全局搜索结合起来——先用大步长快速定位到峰值附近，再用小步长爬山算法做精细调整。这样既保证了速度，又避免了局部极值。