三元搜索效率低于此相关算法吗？

Question

所述三元搜索算法是用于找到最小或最大一个的快速算法单峰函数,函数,要么增加然后减少或减小,然后增加.假设我们正在处理一个减少然后增加的函数,并且我们想要找到最小值.三元搜索使用以下递归:

• 如果窗口的大小"足够小",则返回其中点.
• 除此以外:
  • 评估左右边界的功能; 调用值l和r.
  • 评估1/3和2/3点的功能; 调用值m ₁和m ₂
  • 如果m ₁ <m ₂,则我们处于函数的增加区域,并且最小值不能在m ₂和r 之间.
  • 如果m ₁ > m ₂,那么我们处于函数的递减区域,最小值不能在l和m ₁之间
  • 递归搜索未被丢弃的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

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

Answer 1

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