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

2018-12-22T21:52:06Z

46.229.177.35: /* Алгоритм */

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

== Функция ==
Предположим, что мы ищем максимум функции ''f''(''x''), и что нам известно, что максимум лежит между ''A'' и ''B''. Чтобы алгоритм был применим, должно существовать некоторое значение ''x'', такое, что
* для всех ''a'', ''b'', для которых ''A ≤ a < b ≤ x'', выполняется ''f(a) < f(b)'', и
* для всех ''a'', ''b'', для которых ''x ≤ a < b ≤ B'', выполняется ''f(a) > f(b)''.

== Алгоритм ==
<source lang="c">
/**
Находит максимум функции с одним экстремумом между l и r.
Чтобы найти минимум - достаточно поменять местами действия в ветках if/else.
*/
double l = ..., r = ..., EPS = ...; // входные данные
double m1, m2;
while (r - l > EPS) {
m1 = l + (r - l) / 3;
m2 = r - (r - l) / 3;
if (f (m1) < f (m2))
l = m1;
else
r = m2;
}
</source>

== См. также ==
* [[Двоичный поиск]] (используется для поиска точки, где производная меняет знак)
* [[Метод Ньютона]] (используется для поиска точки, где производная обращается в ноль)
* [[Метод золотого сечения]] (схож с троичным поиском, полезен, если за одну итерацию вычисление f занимает больше всего времени)
* [[Интерполирующий поиск]]
* [[Линейный поиск]]

{{rq|sources|empty|style}}
{{Методы оптимизации}}

[[Категория:Алгоритмы поиска]]
[[Категория:Алгоритмы оптимизации]]

Поле цифровой дидактики - Вклад [ru]

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