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

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

Нехай дана функція $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$ має вигляд: Шаблон:Code:

Шаблон:Sxhl

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

Замість критерію «Шаблон:Code» можна вибрати і такий критерій:

Шаблон:Sxhl

З одного боку, доведеться підібрати константу $i t e r a t i o n s$ , щоб забезпечити необхідну точність (зазвичай досить декількох сотень, щоб досягти максимальної точності). Зате, з іншого боку, число ітерацій перестає залежати від абсолютних величин $l$ і $r$ , тобто ми фактично за допомогою $i t e r a t i o n s$ задаємо необхідну відносну похибку. Шаблон:Методи оптимізації

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

Зміст

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

Алгоритм

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

Реалізація

Навігаційне меню

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

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

Алгоритм

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

Реалізація

Навігаційне меню

Пошук