查看“︁黄金分割搜索”︁的源代码

{{Unreferenced|time=2021-05-15T07:01:05+00:00}}
'''黄金分割搜索'''是一种通过不断缩小[[单峰函数]]的[[最值]]的已知范围，从而找到最值的方法。它的名称源于这个算法保持了间距具有[[黄金分割]]特性的三个点。这个算法与斐波那契搜索和二分查找关系紧密。黄金分割搜索是由Kiefer提出的，而[[斐波那契搜索]]是由Avriel和Wilde所提出。
[[File:GoldenSectionSearch.png|200px|right|黄金分割搜索示意图|thumb]]

==内容==
===基本概念===
上图表示了算法中找最小值的一个步骤。<math>f(x)</math>的函数值位于垂直坐标轴上，参数x位于水平坐标轴。已经有三个位于函数<math>f(x)</math>上的点的值被计算出来。: <math>x_1</math>，<math>x_2</math>，和<math>x_3</math>。可见<math>f_2</math>小于<math>f_1</math>和<math>f_3</math>，所以很明显的，最小值处于<math>x_1</math>和<math>x_3</math>之间。

接下来的步骤是通过计算函数位于另一个点<math>x4</math>的值。在最大的区间选择<math>x4</math>会更有效率，例如：<math>x_2</math>和<math>x_3</math>之间。从图中我们可以看出，如果函数的值落在<math>f_{4a}</math>的话，最小值落于<math>x_1</math>和<math>x_4</math>之间，并且新的一组点将会是<math>x_1</math>和<math>x_2</math>和<math>x_4</math>。然而如果函数的值为<math>f_{4b}</math>的话，新的一组点将会是<math>x_2</math>和<math>x_4</math>和<math>x_3</math>。因此，无论是哪种情况，我们都可以建立一个新的更狭窄的区间，用于搜索函数的最小值。

===点的选择===
由图可知，新的区间会介于<math>x_1</math>和<math>x_4</math>，长度为a+c，或者介于<math>x_2</math>和<math>x_3</math>，长度为<math>b</math>。黄金分割搜索要求这些区间是相等的。若不是如此，较宽的区间会被使用很多次，降低了收敛率。为了确保<math>b</math> = <math>a</math> + <math>c</math>，算法应确保<math>x_4</math> = <math>x_1</math> - <math>x_2</math> + <math>x_3</math>。

然而<math>x_2</math>的确定仍是一个问题。我们避免了<math>x_2</math>非常接近<math>x_1</math>或者<math>x_3</math>的情况，确保了每一次迭代区间宽度会缩小同样的比例。

为了确保计算<math>f(x_4)</math>后的值与之间的成比例，假设<math>f(x_4)</math>的值为<math>f_4a</math>，且我们新的一组点为<math>x_1</math>，<math>x_2</math>和<math>x_4</math>，则必须使：

:<math>\frac{c}{a}=\frac{a}{b}</math>。然而，如果<math>f(x_4)</math>的值为<math>f_4b</math>，并且我们新的一组点为<math>x_2</math>，<math>x_4</math>和<math>x_3</math>，则必须使：
:<math>\frac{c}{b-c}=\frac{a}{b}</math>。结合<math>b</math> = <math>a</math> + <math>c</math>可解得
:<math>\frac{b}{a}=\varphi</math>
而φ就是[[黄金比例]]：

:<math>\varphi= \frac{1+\sqrt{5}}{2}= 1.618033988\ldots</math>
这就是这个算法被称为黄金分割搜索的原因。

===3.终止条件===
===4.递归算法===
===5.斐波那契搜索===
===6.参阅===

{{貴金屬比例}}

[[Category:算法]]
[[Category:斐波那契数]]