algorithm - 三元搜索是否比这个相关算法效率低？

Question

ternary search 算法是一种快速算法，用于查找 unimodal function 的最小值或最大值，一个先增加后减少，或先减少后增加的函数。假设我们正在处理一个先减后增的函数，并且我们想要找到值的最小值。三元搜索使用以下递归工作:

• 如果窗口的大小“足够小”，则返回它的中点。
• 否则:
  • 评估左右边界的功能；将值称为 l 和 r。
  • 评估 1/3 和 2/3 点的功能；调用值 m₁ 和 m₂
  • 如果 m₁ < m₂，则我们处于函数的递增区域，最小值不能介于 m₂ 之间> 和 r.
  • 如果 m₁> m₂，那么我们处于函数的递减区域，最小值不能在 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

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

Answer 1

此版本肯定会收敛得更快，但可能更容易出现浮点精度问题。例如，如果得到 m + eps = m 怎么办？比方说，如果 m 很大，那是一种真实的可能性。因此，在准确性和收敛速度之间存在权衡。此类中最好的算法可以说是 Golden Section Search ，既快速又准确。