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

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

Принцип работы

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

Алгоритм для поиска максимума унимодальной функции

Пусть требуется найти максимум функции \( f(x) \) на отрезке \([l, r]\). Алгоритм выполняется итеративно:

1. Вычисляются две точки \( m_1 \) и \( m_2 \), делящие отрезок на три равные части:

\( m_1 = l + \frac{r - l}{3} \) \( m_2 = r - \frac{r - l}{3} \)

1. Вычисляются значения функции в этих точках: \( f(m_1) \) и \( f(m_2) \).

1. Сравниваются значения:

• Если \( f(m_1) < f(m_2) \), то максимум находится в правой части отрезка \([m_1, r]\), так как левее \( m_1 \) функция возрастает медленнее или убывает. Левая граница сдвигается: \( l = m_1 \).
• Если \( f(m_1) \geq f(m_2) \), то максимум находится в левой части отрезка \([l, m_2]\). Правая граница сдвигается: \( r = m_2 \).

1. Шаги 1–3 повторяются до тех пор, пока длина отрезка \( r - l \) не станет меньше заданной точности \( \varepsilon \).

Для поиска минимума условие сравнения инвертируется: если \( f(m_1) < f(m_2) \), то минимум левее, и сдвигается правая граница; если \( f(m_1) \geq f(m_2) \), то минимум правее, и сдвигается левая граница.

Алгоритм для поиска в отсортированном массиве

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

Сравнение с бинарным поиском

Троичный поиск и бинарный поиск имеют различную асимптотическую сложность и область применения.

• Скорость сходимости: На каждой итерации троичный поиск сужает интервал в \( \frac{2}{3} \) раза (точнее, до \( \frac{2}{3} \) от исходной длины), в то время как бинарный поиск — в \( \frac{1}{2} \) раза. Однако троичный поиск требует двух вычислений функции на шаг, а бинарный — одного. В результате количество итераций для достижения заданной точности \( \varepsilon \) для троичного поиска составляет \( \log_{3/2} \frac{r-l}{\varepsilon} \), а для бинарного — \( \log_2 \frac{r-l}{\varepsilon} \). Сравнение логарифмов показывает, что бинарный поиск требует в среднем меньше итераций: \( \log_2 n \approx 1.585 \log_{3/2} n \), но каждая итерация бинарного поиска выполняет одно вычисление функции, а троичного — два. Таким образом, бинарный поиск почти всегда быстрее для поиска в массиве.

• Область применения: Троичный поиск незаменим для задач, где функция не имеет производной или её вычисление затруднительно, но при этом она унимодальна. Бинарный поиск в таких случаях неприменим, так как требует монотонности (для поиска корня или экстремума с помощью производной). Для поиска в отсортированном массиве бинарный поиск предпочтительнее.

• Сложность реализации: Троичный поиск проще в реализации для непрерывных функций, чем методы, основанные на производных (например, метод Ньютона). Однако он чувствителен к выбору точности и может давать ошибки на функциях с пологими участками.

Применение

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

• Оптимизация в инженерии: Поиск оптимальных параметров конструкций (например, угла наклона панели солнечной батареи для максимального КПД) или режимов работы устройств (частота вращения вентилятора для минимального шума при заданном потоке воздуха).

• Компьютерные науки и программирование:
• Решение задач на соревнованиях по программированию, где требуется найти максимум или минимум функции, заданной аналитически или вычисляемой симуляцией.
• Поиск точки равновесия в игровых моделях (например, в задачах теории игр с выпуклыми функциями выигрыша).
• Оптимизация параметров алгоритмов машинного обучения (например, подбор коэффициента регуляризации, если функция потерь унимодальна).

• Физика и математика: Численное нахождение экстремумов функций, заданных экспериментальными данными или сложными формулами, где дифференцирование невозможно или нецелесообразно.

• Экономика и финансы: Поиск оптимальной цены товара, максимизирующей прибыль, при условии, что функция спроса унимодальна.

Пример реализации на языке Python

Ниже приведён пример реализации троичного поиска для нахождения максимума унимодальной функции на отрезке.

```python def ternary_search_max(f, left, right, eps=1e-9): """ Поиск максимума функции f на отрезке [left, right] с точностью eps. """ while right - left > eps: m1 = left + (right - left) / 3 m2 = right - (right - left) / 3 if f(m1) < f(m2): left = m1 else: right = m2 return (left + right) / 2

Пример использования: f(x) = -x^2 + 4x + 1 (максимум в x=2)

def f(x): return -x**2 + 4*x + 1

max_x = ternary_search_max(f, 0, 4) print(f"Максимум достигается при x = {max_x:.6f}, f(x) = {f(max_x):.6f}") ```

Вариации и родственные алгоритмы

• Золотое сечение: Метод, использующий деление отрезка в пропорции золотого сечения (≈0.618). Требует только одного вычисления функции на итерацию (второе берётся из предыдущего шага), что делает его более эффективным, чем троичный поиск, для непрерывных функций. Однако троичный поиск проще в реализации.

• Дихотомический поиск: Частный случай бинарного поиска, используемый для поиска корня уравнения или экстремума с помощью производной. Неприменим без производной.

• Метод парабол: Использует квадратичную аппроксимацию функции для ускорения сходимости, но требует большего числа вычислений на шаг и не гарантирует сходимости для всех унимодальных функций.

Критика и ограничения

• Неэффективность на гладких функциях: Для функций, имеющих непрерывную вторую производную, методы, использующие производные (например, метод Ньютона), сходятся значительно быстрее (квадратичная сходимость против линейной у троичного поиска).

• Чувствительность к точности: При малом значении \( \varepsilon \) и большом количестве итераций накапливается погрешность вычислений с плавающей точкой, что может привести к неправильному результату.

• Требование унимодальности: Если функция имеет несколько локальных экстремумов, троичный поиск найдёт только один из них, причём не обязательно глобальный. Для мультимодальных функций требуются другие методы (например, имитация отжига или генетические алгоритмы).

• Неприменимость для дискретных функций: Для функций, заданных на целочисленных аргументах (например, поиск в массиве), троичный поиск может быть неэффективен из-за необходимости деления на три части, что не всегда даёт целые точки. В таких случаях предпочтительнее бинарный поиск.

Интересные факты

• Троичный поиск является частным случаем более общего метода поиска экстремума с помощью деления отрезка на \( k \) частей, где \( k > 2 \). Однако увеличение \( k \) не приводит к ускорению сходимости, так как количество вычислений функции на шаг растёт линейно, а скорость сужения интервала — логарифмически.
• В некоторых учебных задачах по программированию троичный поиск ошибочно называют «тернарным поиском», хотя термин «тернарный» чаще используется в контексте троичной системы счисления или логики.
• Алгоритм был впервые описан в математической литературе в середине XX века, но широкое распространение в программировании получил с развитием олимпиадного движения в 1990-х годах.

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013. — Глава 5.3.
• Седжвик Р., Уэйн К. Алгоритмы на Java. — 4-е изд. — М.: Вильямс, 2016. — Глава 3.2.
• Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. — М.: МЦНМО, 2014. — Глава 7.
• Лекции по численным методам. — М.: МГУ, 2005. — Раздел «Методы одномерной оптимизации».