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

Нам задано функцію $f(x)$ , яка є унімодальною на відрізку $[l, r]$ . Під унімодальною функцією ми розуміємо одну з двох можливих поведінок функції:

Функція спочатку строго зростає, досягає максимуму (в одній точці або на відрізку), а потім строго спадає.
Функція спочатку строго спадає, досягає мінімуму, а потім строго зростає.

У цій статті ми розглядатимемо перший сценарій. Другий сценарій повністю симетричний першому.

Завдання полягає в тому, щоб знайти максимум функції $f(x)$ на відрізку $[l, r]$ .

Коли підходить цей алгоритм?

Функція унімодальна (строго зростає до екстремуму, потім строго спадає) і ви шукаєте її максимум або мінімум?
Функція лише монотонна, а ви шукаєте точку переходу чи конкретне значення, а не екстремум? (якщо так → Бінарний пошук)
Точку екстремуму можна знайти лише через порівняння значень $f$ , без аналітичної похідної? (якщо похідна відома й потрібна швидка збіжність → Метод Ньютона)

Алгоритм

Розглянемо будь-які 2 точки $m_1$ та $m_2$ на цьому відрізку: $l < m_1 < m_2 < r$ . Обчислимо значення функції в точках $m_1$ та $m_2$ , тобто знайдемо $f(m_1)$ та $f(m_2)$ . Тепер ми отримуємо один із трьох варіантів:

$f(m_1) < f(m_2)$

Шуканий максимум не може бути розташований ліворуч від $m_1$ , тобто на відрізку $[l, m_1]$ , оскільки або обидві точки $m_1$ та $m_2$ , або лише $m_1$ належать області, де функція зростає. У будь-якому разі це означає, що максимум треба шукати на відрізку $[m_1, r]$ .
$f(m_1) > f(m_2)$

Ця ситуація симетрична до попередньої: максимум не може бути розташований праворуч від $m_2$ , тобто на відрізку $[m_2, r]$ , і простір пошуку звужується до відрізка $[l, m_2]$ .
$f(m_1) = f(m_2)$

Бачимо, що або обидві ці точки належать області, де значення функції максимальне, або $m_1$ перебуває в області зростання, а $m_2$ — в області спадання (тут ми скористалися строгістю зростання/спадання функції). Отже, простір пошуку звужується до $[m_1, m_2]$ . Щоб спростити код, цей випадок можна об'єднати з будь-яким із попередніх.

Таким чином, спираючись на порівняння значень у двох внутрішніх точках, ми можемо замінити поточний відрізок $[l, r]$ новим, коротшим відрізком $[l^\prime, r^\prime]$ . Повторно застосовуючи описану процедуру до відрізка, ми можемо отримати як завгодно короткий відрізок. Зрештою його довжина стане меншою за певну наперед задану константу (точність), і процес можна зупинити. Це числовий метод, тож ми можемо вважати, що після цього функція досягає свого максимуму в усіх точках останнього відрізка $[l, r]$ . Без втрати загальності ми можемо повернути значення $f(l)$ .

Ми не накладали жодних обмежень на вибір точок $m_1$ та $m_2$ . Цей вибір визначатиме швидкість збіжності й точність реалізації. Найпоширеніший спосіб — вибрати точки так, щоб вони ділили відрізок $[l, r]$ на три рівні частини. Отже, маємо

m_1 = l + \frac{(r - l)}{3}

m_2 = r - \frac{(r - l)}{3}

Якщо $m_1$ та $m_2$ вибрати ближче одне до одного, швидкість збіжності трохи зросте.

Аналіз часу роботи

T(n) = T({2n}/{3}) + O(1) = \Theta(\log n)

Це можна уявити так: щоразу після обчислення функції в точках $m_1$ та $m_2$ ми, по суті, відкидаємо приблизно одну третину відрізка — або ліву, або праву. Отже, розмір простору пошуку становить ${2n}/{3}$ від початкового.

Застосувавши основну теорему про рекурентні співвідношення, ми отримуємо шукану оцінку складності.

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

Якщо $f(x)$ приймає цілочисловий параметр, відрізок $[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, \ldots, r)$ , щоб знайти точку, яка дає максимальне значення $f(x)$ .

Метод золотого перерізу

У деяких випадках обчислення $f(x)$ може бути доволі повільним, але зменшити кількість ітерацій неможливо через проблеми з точністю. На щастя, можна обчислювати $f(x)$ лише один раз на кожній ітерації (окрім першої).

Щоб зрозуміти, як це зробити, перегляньмо ще раз спосіб вибору $m_1$ та $m_2$ . Припустимо, що ми вибираємо $m_1$ та $m_2$ на $[l, r]$ так, що $\frac{r - l}{r - m_1} = \frac{r - l}{m_2 - l} = \varphi$ , де $\varphi$ — деяка константа. Щоб зменшити обсяг обчислень, ми хочемо вибрати таке $\varphi$ , щоб на наступній ітерації одна з нових точок обчислення $m_1'$ , $m_2'$ збігалася з $m_1$ або $m_2$ , і тоді ми зможемо повторно використати вже обчислене значення функції.

Тепер припустимо, що після поточної ітерації ми поклали $l = m_1$ . Тоді точка $m_1'$ задовольнятиме $\frac{r - m_1}{r - m_1'} = \varphi$ . Ми хочемо, щоб ця точка збігалася з $m_2$ , тобто $\frac{r - m_1}{r - m_2} = \varphi$ .

Помноживши обидві частини рівності $\frac{r - m_1}{r - m_2} = \varphi$ на $\frac{r - m_2}{r - l}$ , ми отримуємо $\frac{r - m_1}{r - l} = \varphi\frac{r - m_2}{r - l}$ . Зауважимо, що $\frac{r - m_1}{r - l} = \frac{1}{\varphi}$ та $\frac{r - m_2}{r - l} = \frac{r - l + l - m_2}{r - l} = 1 - \frac{1}{\varphi}$ . Підставивши це й помноживши на $\varphi$ , ми отримуємо таке рівняння:

$\varphi^2 - \varphi - 1 = 0$

Це добре відоме рівняння золотого перерізу. Розв'язавши його, отримуємо $\frac{1 \pm \sqrt{5}}{2}$ . Оскільки $\varphi$ має бути додатним, маємо $\varphi = \frac{1 + \sqrt{5}}{2}$ . Застосувавши ту саму логіку до випадку, коли ми кладемо $r = m_2$ і хочемо, щоб $m_2'$ збігалося з $m_1$ , ми отримуємо те саме значення $\varphi$ . Отже, якщо вибрати $m_1 = l + \frac{r - l}{1 + \varphi}$ та $m_2 = r - \frac{r - l}{1 + \varphi}$ , на кожній ітерації ми можемо повторно використати одне зі значень $f(x)$ , обчислених на попередній ітерації.

Реалізація

C++
Python
TypeScript
Go

double ternary_search(double l, double r) {
	double eps = 1e-9;				//встановіть граничну похибку тут
	while (r - l > eps) {
		double m1 = l + (r - l) / 3;
		double m2 = r - (r - l) / 3;
		double f1 = f(m1);		//обчислює значення функції в m1
		double f2 = f(m2);		//обчислює значення функції в m2
		if (f1 < f2)
			l = m1;
		else
			r = m2;
	}
	return f(l);					//повертає максимум f(x) на [l, r]
}

def ternary_search(l: float, r: float) -> float:
    eps = 1e-9                      # встановіть граничну похибку тут
    while r - l > eps:
        m1 = l + (r - l) / 3
        m2 = r - (r - l) / 3
        f1 = f(m1)                  # обчислює значення функції в m1
        f2 = f(m2)                  # обчислює значення функції в m2
        if f1 < f2:
            l = m1
        else:
            r = m2
    return f(l)                     # повертає максимум f(x) на [l, r]

function ternarySearch(l: number, r: number): number {
    const eps = 1e-9;               // встановіть граничну похибку тут
    while (r - l > eps) {
        const m1 = l + (r - l) / 3;
        const m2 = r - (r - l) / 3;
        const f1 = f(m1);           // обчислює значення функції в m1
        const f2 = f(m2);           // обчислює значення функції в m2
        if (f1 < f2)
            l = m1;
        else
            r = m2;
    }
    return f(l);                    // повертає максимум f(x) на [l, r]
}

func ternarySearch(l, r float64) float64 {
	const eps = 1e-9 // встановіть граничну похибку тут
	for r-l > eps {
		m1 := l + (r-l)/3
		m2 := r - (r-l)/3
		f1 := f(m1) // обчислює значення функції в m1
		f2 := f(m2) // обчислює значення функції в m2
		if f1 < f2 {
			l = m1
		} else {
			r = m2
		}
	}
	return f(l) // повертає максимум f(x) на [l, r]
}

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

Замість критерію r - l > eps ми можемо вибрати фіксовану кількість ітерацій як критерій зупинки. Кількість ітерацій слід вибирати так, щоб забезпечити потрібну точність. Зазвичай у більшості задач для програмування гранична похибка становить ${10}^{-6}$ , тож 200 — 300 ітерацій є достатніми. Крім того, кількість ітерацій не залежить від значень $l$ та $r$ , тож кількість ітерацій відповідає потрібній відносній похибці.

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

Алгоритм

Аналіз часу роботи

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

Метод золотого перерізу

Реалізація

Задачі для практики

Відеоматеріали

Алгоритм​

Аналіз часу роботи​

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

Метод золотого перерізу​

Реалізація​

Задачі для практики​

Відеоматеріали​

Алгоритм

Аналіз часу роботи

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

Метод золотого перерізу

Реалізація

Задачі для практики

Відеоматеріали