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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

Реалізація

Реалізація для безперервного випадку (тобто коли функція ${\displaystyle 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)

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