Предположим, что нам дана функция , которая является унимодальной на интервале .
Унимодальная функция имеет одну из следующих двух форм:
В этой заметке мы предполагаем, что функция имеет вторую форму, поэтому наша цель — найти максимальное значение
Решите эти внешние задачи (например, из Codeforces) чтобы закрепить материал урока:
Идея тернарного поиска заключается в том, чтобы разделить текущий интервал на три части.
Пусть
Затем мы сравниваем значения и .
Есть три случая:
Повторяя этот процесс много раз, мы делаем интервал очень маленьким и приближаемся к точке, в которой достигается максимум.
double ternary_search(double l, double r) {
for (int it = 0; it < 200; it++) {
double m1 = l + (r - l) / 3.0;
double m2 = r - (r - l) / 3.0;
if (f(m1) < f(m2)) {
l = m1;
} else {
r = m2;
}
}
return f(l);
}