Троичный поиск

Троичный алгоритм поиска это метод в информатике для поиска минимума или максимума функции унимодальной .

Функция

Предположим, мы ищем максимум $f(x)$ и что мы знаем, что максимум лежит где-то между $A$ и $B$. Чтобы алгоритм был применим, должно быть некоторое значение $x$ такой, что

• для всех $a,b$ с $A\leq a<b\leq x$, у нас есть $f(a)<f(b)$, и
• для всех $a,b$ с $x\leq a<b\leq B$, у нас есть $f(a)>f(b)$.

Алгоритм

Позволять $f(x)$ быть унимодальной функцией на некотором интервале $[l;r]$. Возьмите любые две точки $m_{1}$ и $m_{2}$ в этом сегменте: $l<m_{1}<m_{2}<r$. Тогда есть три возможности:

• если $f(m_{1})<f(m_{2})$, то искомый максимум не может располагаться слева – $[l;m_{1}]$. Это означает, что максимум далее имеет смысл искать только в интервале $[m_{1};r]$
• если $f(m_{1})>f(m_{2})$, что ситуация аналогична предыдущей, с точностью до симметрии. Теперь искомый максимум не может находиться в правой части – $[m_{2};r]$, поэтому перейдите в сегмент $[l;m_{2}]$
• если $f(m_{1})=f(m_{2})$, то поиск следует вести в $[m_{1};m_{2}]$, но этот случай можно отнести к любому из двух предыдущих (в целях упрощения кода). Рано или поздно длина отрезка станет чуть меньше заданной константы, и процесс можно будет остановить.

точки выбора $m_{1}$ и $m_{2}$:

• $m_{1}=l+(r-l)/3$
• $m_{2}=r-(r-l)/3$

Порядок выполнения

$T(n)=T(2n/3)+1=\Theta (\log n)$

Рекурсивный алгоритм

def ternary_search(f, left, right, absolute_precision) -> float:
    """Left and right are the current bounds;
    the maximum is between them.
    """
    if abs(right - left) < absolute_precision:
        return (left + right) / 2

    left_third = (2*left + right) / 3
    right_third = (left + 2*right) / 3

    if f(left_third) < f(right_third):
        return ternary_search(f, left_third, right, absolute_precision)
    else:
        return ternary_search(f, left, right_third, absolute_precision)

Итерационный алгоритм

def ternary_search(f, left, right, absolute_precision) -> float:
    """Find maximum of unimodal function f() within [left, right].
    To find the minimum, reverse the if/else statement or reverse the comparison.
    """
    while abs(right - left) >= absolute_precision:
        left_third = left + (right - left) / 3
        right_third = right - (right - left) / 3

        if f(left_third) < f(right_third):
            left = left_third
        else:
            right = right_third

     # Left and right are the current bounds; the maximum is between them
     return (left + right) / 2

См. также

• Метод Ньютона в оптимизации (может использоваться для поиска того, где производная равна нулю)
• Поиск золотого сечения (аналогично троичному поиску, полезен, если вычисление f занимает большую часть времени на итерацию)
• Алгоритм двоичного поиска (может использоваться для поиска места изменения знака производной)
• Интерполяционный поиск
• Экспоненциальный поиск
• Линейный поиск
• Реализация N-мерного троичного поиска