Является ли троичный поиск менее эффективным, чем этот связанный алгоритм?

Question

Алгоритм троичного поиска - это быстрый алгоритм для нахождения минимума или максимума унимодальной функции , функции, которая либоувеличивается, а затем уменьшается или уменьшается, а затем увеличивается.Предположим, что мы имеем дело с функцией, которая уменьшается, затем увеличивается, и что мы хотим найти минимум значения.Тройной поиск работает с использованием следующей рекурсии:

• Если размер окна "достаточно мал", просто верните его среднюю точку.
• В противном случае:
  • Оценитефункционировать на левой и правой границах;вызовите значения l и r.
  • Оцените функцию в точках 1/3 и 2/3;назовите значения m ₁ и m ₂
  • Если m ₁ 2 , то мы находимся вувеличивающаяся область функции и минимальное значение не могут быть между 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? Это реальная возможность, если, скажем, м большое. Таким образом, существует компромисс между точностью и скоростью сходимости. Вероятно, лучший алгоритм этого класса - Поиск по Золотому сечению , который быстр и точен.

Answer 2

Если функция унимодальна, то g (y) = F (y + ε) - F (y) пересекает ноль только один раз, когда увеличивается y от левой до правой границы.

В основном,то, что вы предлагаете в своем втором / улучшенном алгоритме, - это бинарный поиск пересечения нуля (корня) g (y).Предположим, что вы делаете минимизацию, поэтому F (y) имеет единственный минимум.Тогда G (y) некоторое время будет отрицательным, а затем положительным.Таким образом, если g (x) <0, то корень больше, чем x (или точнее: x + ε), а если g (x)> 0, то корень меньше, чем x.

Это быстрее (наихудший случай), чем ваш первый / оригинальный алгоритм, потому что область, где находится минимум, делится пополам на каждый шаг, а не умножается на 2/3.