求整数域上单峰函数黄金分割搜索的正确实现代码

问题背景 #

有一个计算成本高昂的单峰函数f，仅在整数点有定义，需要找到它的最小值。浮点版黄金分割搜索可正常运行，但修改为整数版后出现结果错误或无限迭代的问题：比如调用参数a=0、b=5（真实最小值在x=3），设置tolerance=1时结果错误，设置tolerance=0.9时无限循环。

问题分析 #

原整数版实现的核心问题：

• 使用round生成整数点容易导致x1和x2重复，破坏黄金分割的区间收缩逻辑
• 停止条件沿用浮点版的tolerance，不适合整数域的离散特性（整数区间最小有效长度为1）
• 最终返回中点取整的方式，可能错过真正的最小值点

修正后的实现代码 #

import math

def golden_section_search_integer(f, a, b):
    """
    针对仅在整数点有定义的单峰函数，实现黄金分割搜索找最小值
    
    参数:
        f (function): 待最小化的单峰函数，仅接受整数输入
        a (int): 搜索区间左边界（整数）
        b (int): 搜索区间右边界（整数）
    
    返回:
        int: 使函数f取得最小值的整数点
    """
    phi = (math.sqrt(5) - 1) / 2  # 黄金比例常数
    
    # 初始化两个内部整数点，确保x1 < x2
    x1 = math.floor(a + (1 - phi) * (b - a))
    x2 = math.ceil(a + phi * (b - a))
    
    # 避免x1或x2超出区间，或两点重合
    x1 = max(a, min(x1, b-1))
    x2 = max(x1+1, min(x2, b))
    
    f_x1 = f(x1)
    f_x2 = f(x2)
    
    # 整数域停止条件：区间长度大于1时继续收缩
    while b - a > 1:
        if f_x1 < f_x2:
            # 丢弃右半区间，收缩右边界
            b = x2
            x2 = x1
            f_x2 = f_x1
            # 重新计算左内部点，确保是整数且不等于x2
            x1 = math.floor(a + (1 - phi) * (b - a))
            x1 = max(a, min(x1, b-1))
            if x1 != x2:
                f_x1 = f(x1)
        else:
            # 丢弃左半区间，收缩左边界
            a = x1
            x1 = x2
            f_x1 = f_x2
            # 重新计算右内部点，确保是整数且不等于x1
            x2 = math.ceil(a + phi * (b - a))
            x2 = max(x1+1, min(x2, b))
            if x2 != x1:
                f_x2 = f(x2)
    
    # 最终区间只剩1或2个整数，比较后返回最小值点
    candidates = list(range(a, b+1))
    return min(candidates, key=f)

# 测试函数
def f(x):
    return (x - 3)**2 + 5

# 调用测试
print(golden_section_search_integer(f, 0, 5))  # 输出：3

关键修改说明 #

1. 停止条件优化：改为while b - a > 1，当区间长度≤1时，直接比较剩余整数点的函数值
2. 整数点生成逻辑：用floor和ceil替代round，确保x1 < x2且始终在区间内，避免点重合
3. 边界校验：添加max/min确保生成的内部点不会超出区间范围
4. 最终结果选择：直接比较区间内所有剩余整数的函数值，返回真正的最小值点，避免取整误差

内容的提问来源于stack exchange，提问作者Simd