Тернарный поиск - Ternary search

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

Функция

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

  • для всех a , b с A ≤ a < b ≤ x имеем f ( a ) < f ( b ) и
  • для всех a , b с x ≤ a < b ≤ B имеем f ( a )> f ( b ).

Алгоритм

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

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

точки выбора m 1 и m 2 :

  • т 1 = 1 + ( г - 1 ) / 3
  • м 2 = г - ( г - л ) / 3
Порядок выполнения

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

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

Смотрите также

Ссылки