Тернарный поиск

Алгоритмы   29 июля 2012  Автор статьи:  

Троичный или тернарный поиск предназначен для поиска минимума (максимума) функций особого вида на некотором отрезке. Функциями особого вида являются так называемые унимодальные функции. Унимодальной функцией 1го (2го) рода называется такая функция f(x), для которой на отрезке [l,r] существуют такие точки x_0 и x_1 : l \le x_0 \le x_1 \le r, что на отрезке [l,x_0] функция f(x) монотонно убывает (возрастает), на отрезке [x_0,x_1] эквивалентна некоторой константе, и на отрезке [x_1,r] возрастает (убывает).
Тернарный поиск делает серию итераций, на каждой из которых длина исследуемого отрезка [l,r] уменьшается в некоторое число раз(для классического варианта когда отрезки [l,x_0][x_0,x_1][x_1,r] имеют одинаковую длину, длина искомого отрезка уменьшается в 1.5 раза). При этом поддерживается следующий инвариант: отрезок продолжает содержать аргумент, на котором функция достигает минимальное(максимальное) значение. Для выполнения этого инварианта на каждой итерации производится сравнение значения функций в точках x_0 и x_1. На основании этого сравнения можно сделать вывод, как сокращать отрезок(все нижеперечисленное описывает действия с унимодальной функцией 1го рода): если f(x_0) < f(x_1), то точка минимума унимодальной функции не может располагаться на отрезке [x_1,r], поэтому его можно дальше не рассматривать; в противном случае отбрасывается отрезок [l,x_0]. Итерации производим до тех пор, пока длина отрезка [l,r] не станет меньше требуемой точности ответа.
Если точки x_0 и x_1 делят отрезок [l,r] на три равные части, то среднее время работы алгоритма — O(\log_{\frac{3}{2}}{\frac{r-l}{e})}), где e — требуемая точность ответа. На самом деле, точное деление на три равных части нигде не используется, и точки x_0 и x_1 выбирают как можно ближе к середине отрезка [l,r], при этом выбранные точки симметричны относительно центра отрезка. Так, например на практике часто выбирают следующие координаты точек: x_0 = l + \frac{r - l}{5}\cdot2, x_1 = l + \frac{r - l}{5}\cdot3.

Научиться программировать

  • на Delphi

  • на Java

  • на C++