5

三元搜索算法是一种快速算法，用于寻找单峰函数的最小值或最大值，该函数要么先增大后减小，要么先减小后增大。假设我们正在处理一个先减少然后增加的函数，并且我们想要找到最小值。三元搜索使用以下递归工作：

  • 如果窗口的大小“足够小”，则返回它的中点。
  • 除此以外：
    • 评估左右边界的函数；调用值 l 和 r。
    • 在 1/3 和 2/3 点评估函数；调用值 m 1和 m 2
    • 如果 m 1 < m 2，那么我们处于函数的递增区域，并且最小值不能在 m 2和 r 之间。
    • 如果 m 1 > m 2，那么我们在函数的递减区域中，最小值不能在 l 和 m 1之间
    • 递归搜索未被丢弃的 2/3。

该算法运行迅速，因为它可以在每次迭代中不断抛出 1/3 的值。

然而，我觉得我错过了一些东西，因为我相信我们可以让这个算法运行得更快。特别要注意的是，我们总是丢弃边界和探测点之一之间范围的三分之一。这意味着我们保留了探测点和另一个边界之间的区域。因为三元搜索在 1/3 点处选择探测点，这意味着我们在每个点保留 2/3 的值。如果我们不是在 1/3 和 2/3 点处探测，而是在 1/2 - ε 和 1/2 + ε 点处探测一个极小的 ε 怎么办？这意味着我们将在每一步中丢弃 1/2 - ε 的范围，这意味着范围的大小将比我们每次仅丢弃 1/3 的元素时减小得快得多。

例如，如果我选择 ε = 1/1000，我们将在每次迭代中抛出 999/2000 的范围进行搜索。此处显示了经过一定次数的迭代后剩余的分数（三元搜索在左侧，我的算法在右侧：）

 1 :                1.0  >=                1.0
 2 :     0.666666666667  >=             0.5005
 3 :     0.444444444444  >=         0.25050025
 4 :     0.296296296296  >=     0.125375375125
 5 :     0.197530864198  >=    0.0627503752501
 6 :     0.131687242798  >=    0.0314065628127
 7 :    0.0877914951989  >=    0.0157189846877
 8 :    0.0585276634659  >=   0.00786735183621
 9 :    0.0390184423106  >=   0.00393760959402
10 :    0.0260122948737  >=   0.00197077360181
11 :    0.0173415299158  >=  0.000986372187705
12 :    0.0115610199439  >=  0.000493679279947
13 :   0.00770734662926  >=  0.000247086479613
14 :   0.00513823108617  >=  0.000123666783046
15 :   0.00342548739078  >=  6.18952249147e-05
16 :   0.00228365826052  >=  3.09785600698e-05
17 :   0.00152243884035  >=  1.55047693149e-05
18 :   0.00101495922690  >=  7.76013704213e-06
19 :  0.000676639484599  >=  3.88394858959e-06

这个算法的修改版本是否比原始版本“更好”？或者我在这里遗漏了什么意味着我不应该使用修改后的策略来选择探测点？

4

2 回答 2

3

这个版本肯定会更快收敛，但可能更容易出现浮点精度问题。例如，如果你得到 m + eps = m 怎么办？比如说，如果 m 很大，这是一个真正的可能性。因此，在准确性和收敛速度之间存在权衡。这类最好的算法可以说是黄金分割搜索，它既快速又准确。

于 2011-12-14T10:15:10.803 回答
1

如果一个函数是单峰的，那么 g(y) = F(y+ε) - F(y) 只过零一次，当 y 从左边界增加到右边界时。

基本上，您在第二个/改进算法中提出的是对 g(y) 的过零（根）的二进制搜索。假设您正在进行最小化，因此 F(y) 有一个最小值。然后 G(y) 暂时为负，然后为正。因此，如果 g(x) <0，则根大于 x（或更准确地说：x+ε），如果 g(x)>0，则根小于 x。

这比您的第一个/原始算法更快（最坏情况），因为最小值所在的区域每一步减半，而不是乘以 2/3。

于 2011-12-14T14:01:57.890 回答