黄金分割法,又称 0.618 法, 在数学上用于搜索一维单峰函数的极值的方法,和 二分法 类似, 是一种区间缩进的搜索方法。
数学上的黄金分割法 ¶
方便起见,我们只看下单峰函数,上单峰函数雷同。
假设 $f(x)$ 函数是区间 $[a, b]$ 上的一个下单峰函数,其极值的位置是 $t$ 。 就是说, $t$ 左边是单调递减的,右边是单调递增的 。
如果我们往区间上放置两个点 $a_1$ 和 $b_1$ ,对区间进行分割,这时候,只有两种情况:
- 如果 $f(a_1) < f(b_1)$ ,则必然 $t$ 在区间 $[a, b_1]$ 内,就是下图中左边的情况。
- 如果 $f(a_1) >= f(b_1)$ ,则必然 $t$ 在区间 $[a_1, b]$ 内,就是下图中右边的情况。
先只考虑上面所说的第一种情况,我们把左边的 $[a, b_1] $ 当做新的区间,代替原来的 $[a, b]$ ,也就是舍弃最右端的区间段; 同理对于上面所说的第二种情况,此时舍弃最左端的区间段。 然后继续比较、舍弃,如此反复进行,区间大小会不断变小,不断逼近 $t$ 。 如下图所示,绿色的线段表示不断缩小的区间:
直到误差达到理想水平,我们即可以获得单峰极值的近似值。
0.618 的由来 ¶
现在要问,区间的大小一次缩小多少比较合适呢?
黄金分割法的方法是,每次选择区间的 $0.618$ 处和它的对称点 $0.382$ 处作为一对分割点。
如下图 2.1 所示,左右分割点分别在 $0.382$ 比例处和 $0.618$ 比例处,且两个点关于中轴对称。
假设原始线段 $ab$ 的长度是 $L$ , 每次缩短的比例是小数 $r$ 。具体来说,我们希望的是:
每次的两个分割点是对称的。
事先并不知道极值点在哪里,对于不对称的分割点,会出现一侧区间大,一侧区间小的情况,如果极值不断落入大的区间, 会恶化迭代的速度。
在下面图 2.2 中的上图中,对称意味着: 线段 $aa_1$ 的长度和线段 $b_1b$ 一样,即 $(1-r)L$ 。
分割点可以复用。
在下面的图 2.2 中,第一次的分割点 $a_1$ 复用 为第二次的分割点 $b_2$ 。
最好上一次的分割点也可以用作下一次迭代的分割点,这样避免重复计算,每次只需要计算一个分割点的函数值。
则下面的线段 $ab_2$ 和上面中的线段 $aa_1$ 一样长,即 $r^2L = (1-r)L$。
解方程 $r^2 + r = 1$ 得 $r = \frac {\sqrt{5} \ -\ 1} {2}$ ,约等于 $0.618$ 。
复杂度分析 ¶
假设总共需要迭代 $k$ 次,区间才可以缩小到单位长度,假设总共的区间长度是 $n$ 个单位长度, 则有 $ n * (0.618) ^ k = 1$ 。假设 $c = 1 / 0.618$ ,则有 $ k = log_{c}{n}$ 。
根据 换底公式 可以知道:
\[log_{c} {n} = \frac {log_{2} {n}} {log_{2}{c}} = C * log_{2}{n}\]也就是说时间复杂度是 $log{n}$ 。
计算机中的三分法求单峰 ¶
在计算机编程上,可以用同样的方式对单峰数组求极值。 不过,不像数学中 $0.618$ 是连续区间的分割点,离散的数组上,使用 三分法。
下面仍然以下单峰数组为例,上单峰数组雷同。
下图是一个算法过程的示意图,其中红色框内的是每次缩减后的区间段,绿色的元素是分割点:
此算法只对存在单峰的数组有效。
算法过程:
- 步骤 1:初始化查找范围为整个数组,即低位 $low = 0$ ,高位 $high = n - 1$ ,$n$ 是数组的大小。
步骤 2:选择分割点:
- 计算整个范围的三分之一大小:$delta = (high - low) / 3$ 。
- 左分割点是 $partition\text{_}left = low + delta$ 。
- 右分割点与左分割点对称,是 $partition\text{_}left = high - delta$ 。
步骤 3:按以下情况进行比较,然后回到步骤 2 继续迭代。
如果左分割点的值严格小于右分割点的值,则舍弃右侧区间段,即 $high$ 缩小为 $partition\text{_}right - 1$ 。
这里同样舍弃了 $partition\text{_}right$ 位置上的值,因为此数据肯定不是单峰。
同理对于右分割点的值严格小于左分割点的情况, $ low = partition\text{_}left + 1$ 。
如果两个分割点的值相等,则两个点都不是极值,两端都舍弃。
- 步骤 4:直到 $low < high$ 不再满足,即 $low$ 和 $high$ 相等,终止迭代,此时已收敛到一个元素上,即峰值的位置。
复杂度分析 ¶
和黄金分割法一样,要把查找范围收缩到 $1$,迭代次数 $k$ 满足 $n * (1/3) ^ k = 1$ , 则时间复杂度为 $O(log_{3} {n})$ ,由 换底公式 可换算到 $O(log_{2} {n})$ 。
非递归实现的空间复杂度是 $O(1)$ 。
C 语言实现 ¶
C 语言的三分法查找数组内的单峰
// 给出大小为 n 的数组 a 的单峰的下标位置。
int TernarySearchPeak(int a[], int n) {
int low = 0;
int high = n - 1;
int delta = 0;
int partition_left = 0;
int partition_right = 0;
while (low < high) {
delta = (high - low) / 3;
partition_left = low + delta;
partition_right = high - delta;
if (a[partition_left] < a[partition_right]) {
high = partition_right - 1;
} else if (a[partition_left] > a[partition_right]) {
low = partition_left + 1;
} else {
low = partition_left + 1;
high = partition_right - 1;
}
}
return low;
}
(完)