Всем привет! Сегодня я хочу познакомить вас с новым алгоритмом: тернарным поиском на неунимодальных функциях. Я придумал ее во время ROI 2024, и благодаря этому стал призером.

Мотивация

В олпроге есть много примеров, когда нам нужно максимизировать или минимизировать значение некоторой функции $$$f$$$. Если функция унимодальна, то нет проблем с использованием тернарного поиска. Но если это неправда, то делать нечего. Конечно, если $$$f$$$ случайна, нужно проверить все ее значения. К счастью, интуиция подсказывает нам, что если функция близка к унимодальной, то мы можем использовать тернарный поиск и на большей части ее области определения.

Интуиция

Рассмотрим унимодальную функцию $$$0.03x^2$$$, добавив к ней немного шума ($$$sin (x)$$$):

Интуиция подсказывает, что если шум не очень сильный, мы все равно можем использовать троичный поиск вдали от глобального минимума.

В данном примере мы можем показать это более формально: производная функции равна $$$0.06x + cos(x)$$$, и при $$$|x| > \frac{1}{0.06} \approx 16.67$$$, добавление косинуса не меняет знак производной.

Первая оптимизация

Итак, первая идея — запустить тернарный поиск, используя не while (r - l > eps), а while (r - l > C), и затем перебрать все значения между $$$l$$$ и $$$r$$$ с некоторой точностью. В случае, когда $$$f$$$ принимает целое число, проблема точности вообще отсутствует.

Вторая оптимизация

Она упоминается в этом блоге. В нем рассказывается аналогичная идея разбиения всех значений аргументов на блоки и применения к ним троичного поиска.

Это единственная связанная с блогом идея, которую я нашел в Интернете. Я пробовал гуглить и спрашивать людей, занимающихся олпрогой, но никто из них не знал об этом раньше.

Тесты

Функция из примера скучна, поэтому рассмотрим более интересную: функция Вейерштрасса.

Приближая, я выяснил, что максимум составляет около $$$1,162791$$$.

Будем искать максимум на интервале (-1, 1).

#include <bits/stdc++.h>
#define M_PI 3.14159265358979323846
using namespace std;
#define ld long double
ld Weierstrass(ld x) {
    ld y = 0;
    for (int i = 0; i < 30; i++) y += pow(0.14, i) * cos(pow(51, i) * M_PI * x);
    return y;
}
ld Classical_ternary(ld f(ld), ld l = -1, ld r = 1, ld eps = 1e-7) {
    while (r - l > eps) {
        ld midl = l + (r - l) / 3;
        ld midr = r - (r - l) / 3;
        if (f(midl) > f(midr)) r = midr;
        else l = midl;
    }
    return f(l);
}
int main() {
    cout << Classical_ternary(Weierstrass) << endl;
}

Это дает нам $$$1,12881$$$. Изменение $$$eps$$$ лишь немного меняет это значение.

Давайте разделим аргументы на блоки. Поскольку аргументы вещественные, мы не будем явно разбивать их, а возьмем максимум в некотором диапазоне вблизи аргумента.

ld Blocks(ld f(ld), ld l = -1, ld r = 1, ld eps = 1e-7) {
    int iter = 10000;
    while (r - l > eps) {
        ld midl = l + (r - l) / 3;
        ld midr = r - (r - l) / 3;
        ld vall = -2e9, valr = -2e9;
        for (ld x = midl, i = 0; i < iter; x += eps, i++) vall = max(vall, f(x));
        for (ld x = midr, i = 0; i < iter; x += eps, i++) valr = max(valr, f(x));
        if (vall > valr) r = midr;
        else l = midl;
    }
    return f(l);
}

Это дает $$$1,15616$$$, что весьма неплохо. Мы можем еще улучшить ответ, взяв максимум из всех значений $$$f$$$, которые мы когда-либо вычисляли:

ld Blocks(ld f(ld), ld l = -1, ld r = 1, ld eps = 1e-7) {
    int iter = 10000;
    ld ans = -2e9;
    while (r - l > eps) {
        ld midl = l + (r - l) / 3;
        ld midr = r - (r - l) / 3;
        ld vall = -2e9, valr = -2e9;
        for (ld x = midl, i = 0; i < iter; x += eps, i++) vall = max(vall, f(x));
        for (ld x = midr, i = 0; i < iter; x += eps, i++) valr = max(valr, f(x));
        ans = max({ans, vall, valr});
        if (vall > valr) r = midr;
        else l = midl;
    }
    return max(ans, f(l));
}

Это дает нам $$$1,16278$$$, что очень близко к ожидаемым $$$1,162791$$$. Кажется, что мы нашли хороший метод. Но давайте копнём глубже.

Третья оптимизация

Давайте изменим константу $$$3$$$ в коде. Назовем ее $$$C$$$. Опытным олпрогерам известно, что часто хорошо выбрать $$$C$$$ равной $$$2$$$ (бинарный поиск по производной) или $$$\frac{\sqrt5+1}{2}$$$ (терпоиск с золотым сечением). Поскольку на каждой итерации мы отбрасываем $$$\frac{1}{C}$$$ часть нашего интервала, вероятность того, что максимум окажется внутри отрезанной части, уменьшается с увеличением C.

Выберем $$$C = 100$$$ и запустим тернарный поиск. Как мы уже знаем, взятие максимума из всех вызовов функций — очень хорошая оптимизация, поэтому я сразу ее добавлю.

ld find_maximum(ld f(ld), int C = 3, ld l = -1, ld r = 1, ld eps = 1e-7) {
    ld ans = -2e9;
    while (r - l > eps) {
        ld midl = l + (r - l) / C;
        ld midr = r - (r - l) / C;
        ld vall = f(midl), valr = f(midr);
        ans = max({ans, vall, valr});
        if (vall > valr) r = midr;
        else l = midl;
    }
    return max(ans, f(l));
}

Если мы запустим его при $$$C = 3$$$, то получим $$$1,13140$$$ (алгоритм тот же, что и в классическом троичном поиске, но мы берем максимум, поэтому ответ намного лучше). Теперь давайте увеличим $$$C$$$ и посмотрим, как увеличится ответ:

Мы запускаем его с $$$C = 30$$$ и получаем $$$1,16275$$$. Запускаем его с $$$C = 100$$$ и получаем... $$$1,15444$$$.

Дело в том, что увеличение $$$C$$$ не гарантирует увеличения ответа.

Четвертая оптимизация

Давайте переберем все значения $$$C$$$ от 3 до 100 и возьмем лучший ответ:

for (int C = 3; C < 100; C++) res = max(res, find_maximum(Weierstrass, C));

Это дает нам $$$1,16279$$$ и работает быстрее, чем разбиение на блоки. Чтобы сравнивать эти подходы дальше, нам нужно изменить функцию, потому что оба метода возвращают значения, которые очень близки к ответу.

Используем $$$a = 0,88$$$ и $$$b = 51$$$ для функции Вейерштрасса. Обратите внимание, что в Desmos невозможно увидеть фактический максимум функции.

Я сравню эти два подхода в Запуске Codeforces.

Blocks res: 6.6809
Blocks time: 3.645
100-ternary res: 6.27581
100-ternary time: 0.753

Blocks res: 6.6809
Blocks time: 3.365
200-ternary res: 6.48924
200-ternary time: 2.725

Blocks res: 6.6809
Blocks time: 3.442
400-ternary res: 7.05544
400-ternary time: 10.751

Я попробовал объединить эти методы вместе, но результат оказался хуже, чем у обоих методов (потому что я использовал $$$1000$$$ итераций вместо $$$10000$$$ и перебор $$$C < 10$$$, чтобы влезть в ТЛ).

Вывод

На рассмотренной мной функции оба подхода достаточно хороши. На реальных соревнованиях я использовал только свой подход (четвертую оптимизацию).

Из недавних задач, 2035E - Монстр, я успешно использовал эту технику. Вот реализация для целочисленных аргументов: 288346163.

Если вы знаете, как найти максимум лучше (не методом имитации отжига), пожалуйста, напишите.