Трои́чный по́иск (Тернарный поиск) — это метод в информатике для поиска максимумов и минимумов функции, которая либо сначала строго возрастает, затем строго убывает, либо наоборот. Троичный поиск определяет, что минимум или максимум не может лежать либо в первой, либо в последней трети области, и затем повторяет поиск на оставшихся двух третях. Троичный поиск демонстрирует парадигму программирования «разделяй и властвуй».
Функция Предположим, что мы ищем максимум функции 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).
Алгоритм /** Находит максимум функции с одним экстремумом между 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; }
См. также Двоичный поиск (используется для поиска точки, где производная меняет знак) Метод Ньютона (используется для поиска точки, где производная обращается в ноль) Метод золотого сечения (схож с троичным поиском, полезен, если за одну итерацию вычисление f занимает больше всего времени) Интерполирующий поиск Линейный поиск
Категория:Алгоритмы поиска Категория:Алгоритмы оптимизации