Тернарний пошук

Постановка задачі

Нехай дана функція $f(x)$, унімодальна на деякому відрізку $[l;r]$. Під унімодальна розуміється один з двох варіантів. Перший: функція спочатку строго зростає, потім досягає максимуму (в одній точці або цілому відрізку), потім строго спадає. Другий варіант, симетричний: функція спочатку спадає, досягає мінімуму, зростає. Надалі ми будемо розглядати перший варіант, другий буде абсолютно симетричний йому. Потрібно знайти максимум функції $f(x)$ на відрізку $[l;r]$.

Алгоритм

Візьмемо будь-які дві точки $m_{1}$ і $m_{2}$ в цьому відрізку: $l<m_{1}<m_{2}<r$. Порахуємо значення функції $f(m_{1})$ і $f(m_{2})$.Далі у нас виходить три варіанти:

• Якщо виявиться, що $f(m_{1})<f(m_{2})$, то шуканий максимум не може перебувати в лівій частині, тобто в частині $[l;m_{1}]$. У цьому легко переконатися: якщо в лівій точці функція менше, ніж в правій, то або ці дві точки знаходяться в області «підйому» функції, або тільки ліва точка знаходиться там. У будь-якому випадку, це означає, що максимум далі є сенс шукати тільки в відрізку $[m_{1};r]$.
• Якщо, навпаки, $f(m_{1})>f(m_{2})$, то ситуація аналогічна попередній з точністю до симетрії. Тепер шуканий максимум не може перебувати в правій частині, тобто в частині $[m_{2};r]$, тому переходимо до відрізка $[l;m_{2}]$.
• Якщо $f(m_{1})=f(m_{2})$, то або обидві ці точки знаходяться в області максимуму, або ліва точка знаходиться в області зростання, а права — в області спадання (тут істотно використовується те, що зростання / спадання суворі). Таким чином, в подальшому пошук має сенс на відрізку $[m_{1};m_{2}]$, але (з метою спрощення коду) цей випадок можна віднести до будь-якого з двох попередніх.

Таким чином, за результатом порівняння значень функції в двох внутрішніх точках ми замість поточного відрізка пошуку $[l;r]$ знаходимо новий відрізок $[l';r']$. Повторимо тепер всі дії для цього нового відрізка, знову отримаємо новий, суворо менший, відрізок, і так далі.

$m_{1}=l+{\frac {r-l}{3}}$

$m_{2}=r-{\frac {r-l}{3}}$

Втім, при іншому виборі, коли $m_{1}$ і $m_{2}$ ближче один до одного, швидкість збіжності збільшиться.

Випадок цілочисельного аргументу

Якщо аргумент функції $f$ цілочисельний, то відрізок $[l;r]$ теж стає дискретним, але, оскільки ми не накладали ніяких обмежень на вибір точок $m_{1}$ і $m_{2}$, то на коректність алгоритму це ніяк не впливає. Можна як і раніше вибирати $m_{1}$ і $m_{2}$ так, щоб вони ділили відрізок $[l;r]$ на 3 частини, але вже тільки приблизно рівні.

Другий відмінний момент — критерій зупинки алгоритму. В даному випадку тернарний пошук треба буде зупиняти, коли стане $r-l<3$, адже в такому випадку вже неможливо буде вибрати точки $m_{1}$ і $m_{2}$ так, щоб були різними і відрізнялися від $l$ і $r$, і це може привести до зациклення. Після того, як алгоритм тернарного пошуку зупиниться і стане $r-l<3$, з решти декількох точок $(l,l+1,...,r)$ треба вибрати точку з максимальним значенням функції.

Реалізація

Реалізація для безперервного випадку (тобто коли функція $f$ має вигляд: double f(double x)):

double l = ..., r = ..., EPS = ...;//вхідні дані 
while (r - l > EPS) {
    double m1 = l + (r - l) / 3,
        m2 = r - (r - l) / 3;
    if (f(m1) < f(m2))
        l = m1;
    else
        r = m2;
}

Тут EPS — фактично, абсолютна похибка відповіді (не враховуючи похибок, пов'язаних з неточним обчисленням функції).

Замість критерію «while (r - l > EPS)» можна вибрати і такий критерій:

for (int it = 0; it < iterations; ++it)

З одного боку, доведеться підібрати константу $iterations$, щоб забезпечити необхідну точність (зазвичай досить декількох сотень, щоб досягти максимальної точності). Зате, з іншого боку, число ітерацій перестає залежати від абсолютних величин $l$ і $r$, тобто ми фактично за допомогою $iterations$ задаємо необхідну відносну похибку.