Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Функция [ править ]

Предположим , мы ищем максимум ф ( х ) , и что мы знаем , что максимум лежит где - то между 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 :  "" "Левая и правая - текущие границы;  максимум находится между ними.  " ""  if  abs ( right  -  left )  <  absolute_precision :  return  ( left  +  right )  /  2 left_third  =  ( 2 * слева  +  справа )  /  3  right_third  =  ( слева  +  2 * справа )  /  3 если  f ( left_third )  <  f ( right_third ):  вернуть  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 :  "" "Найти максимум унимодальной функции f () в пределах [left, right]  Чтобы найти минимум, переверните оператор if / else или отмените сравнение.  " " "в  то время как  абс ( справа  -  слева )  > =  absolute_precision :  left_third  =  left  +  ( right  -  left )  /  3  right_third  =  right  -  (справа  -  слева )  /  3 если  f ( left_third )  <  f ( right_third ):  left  =  left_third  else :  right  =  right_third # Слева и справа - текущие границы; максимум между ними  возврат  ( левый  +  правый )  /  2

См. Также [ править ]

Ссылки [ править ]