Троичный поиск
Троичный поиск (ternary search, тернарный поиск) — метод поиска минимума или максимума функции на отрезке, которая либо сначала строго возрастает, затем строго убывает, либо наоборот.
Алгоритм[править]
Рассмотрим этот алгоритм на примере поиска минимума (поиск максимума аналогичен).
Пусть функция
на отрезке имеет минимум, и мы хотим найти точку , в которой он достигается.Посчитаем значения функции в точках
и .Так как в точке
минимум, то на отрезке функция убывает, а на — возрастает, то есть.
Значит если
, то , аналогично из следует .Тогда нам нужно изменить границы поиска и искать дальше, пока не будет достигнута необходимая точность, то есть
.Из рассуждений и рисунка может возникнуть идея взять, например, отрезок
вместо отрезка . Но этого делать нельзя, потому что мы не умеем различать случаи, когда и слева или справа от минимума.Можно заметить, что если мы всегда будем брать отрезок
при или при , то минимум функции всегда будет в нашем отрезке. Если , то можно взять любой отрезок.Псевдокод[править]
Рекурсивный вариант:
double ternarySearchMin(double f(), double left, double right, double eps): if right - left < eps return (left + right) / 2 a = (left * 2 + right) / 3 b = (left + right * 2) / 3 if f(a) < f(b) return ternarySearchMin(f, left, b, eps) else return ternarySearchMin(f, a, right, eps)
Итеративный вариант:
double ternarySearchMin(double f(), double left, double right, double eps): while right - left > eps a = (left * 2 + right) / 3 b = (left + right * 2) / 3 if f(a) < f(b) right = b else left = a return (left + right) / 2
Время работы[править]
Так как на каждой итерации мы считаем два значения функции и уменьшаем область поиска в полтора раза, пока
, то время работы алгоритма составитСм. также[править]
Источники информации[править]
- Дональд Кнут — Искусство программирования. Том 3. Сортировка и поиск. / Knuth D.E. — The Art of Computer Programming. Vol. 3. Sorting and Searching.
- Троичный поиск — Википедия
- Ternary search — Wikipedia