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

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

• 1 Функция
• 2 Алгоритм
  • 2.1 Рекурсивный алгоритм
  • 2.2 Итерационный алгоритм
• 3 См. Также
• 4 Ссылки

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

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

Пусть f (x) будет унимодальной функцией на некоторый интервал [l; р]. Возьмем любые две точки m 1 и m 2 на этом отрезке: l < m1< m2< r. Then there are three possibilities:

• если f (m 1) < f(m2), то требуемый максимум не может быть расположен с левой стороны - [л; 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:

• m1= l + (rl) / 3
• m2= r - (rl) / 3

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

$T\; (n)\; =\; T\; (2\; n\; /\; 3)\; +\; 1\; =\; \Theta \; (log\; \; n)\; \{\backslash \; displaystyle\; T\; (n)\; =\; T\; (2n\; /\; 3)\; +\; 1\; =\; \backslash \; Theta\; (\backslash \; log\; n)\}$

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

def ternary_search (f, left, right, absolute_precision) ->float: "" "Левая и правая текущие границы ; максимум находится между ними. "" "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:" "" Найти максимум унимодальной функции f () в пределах [left, right] Чтобы найти минимум, переверните оператор if / else или обратное сравнение. "" "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 занимает большую часть времени на итерацию)
• Алгоритм двоичного поиска (может использоваться для поиска места изменения знака производной)
• Поиск с интерполяцией
• Экспоненциальный поиск
• Линейный поиск
• Реализация трехмерного троичного поиска