Оптимизации динамики

  • Разделяй и властвуй
  • Оптимизация Кнута
  • Convex Hull Trick
  • Лямбда-оптимизация

Задача

Даны $n$ точек на прямой. Нужно найти $m$ отрезков, покрывающих все точки, минимизировав при этом сумму квадратов их длин.

Базовое решение — следующая динамика: $f[i, j]$ — минимальная стоимость покрытия $i$ первых (самых левых) точек, используя не более $j$ отрезков (итоговый ответ будет записан в $f[n, m]$ — прим. К. О.).

Переход — перебор всех возможных последних отрезков, то есть $f[i, j] = \min_{k < i} \{f[k, j-1] + (x_{i-1}-x_k)^2 \}$.

In [ ]:
// x[] — отсортированный массив координат точек, нумерация с нуля

// квадрат длины отрезка от i-той до j-той точки
int cost(int i, int j) { return (x[j]-x[i])*(x[j]-x[i]); }

// TODO: предподсчитать cost

for (int i = 0; i <= m; i++)
    f[0][k] = 0; // если нам не нужно ничего покрывать, то всё и так хорошо
// все остальные f предполагаем равными бесконечности

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        for (int k = 0; k < i; k++)
            f[i][j] = min(f[i][j], f[k][j-1] + cost(k, i-1));

Заметим, что циклы по i и j можно поменять местами.

Такое решение пока работает за $O(n^2 m)$ — для каждого состояния линейный перебор. Сейчас мы покажем 4 разных метода, как его ускорить.

Разделяй-и-властвуй

Обозначим за $opt[i, j]$ оптимальный $k$, на котором $f[i, j]$ минимизируется. Для однозначности, из всех оптимальных индексов веберем набольший.

Утверждение. $opt[i, j] \leq opt[i, j+1]$.

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

Что это нам даёт? Если мы уже знаем $opt[i, l]$ и $opt[i, r]$ и хотим посчитать $opt[i, j]$ для какого-то $j$ между $l$ и $r$, то мы можем сузить отрезок поиска оптимального индекса с $[0, i-1]$ до $[opt[i, l], opt[i][r]]$.

Давайте делать следующее: заведем рекурсивную функцию, которая считает динамики для отрезка $[l, r]$, зная, что их $opt$-ы лежат между $l'$ и $r'$. Она берет середину отрезка $[l, r]$ и линейным проходом считает ответ для неё, а затем просто спускается дальше рекурсивно.

In [ ]:
void solve (int l, int r, int _l, int _r, int k) {
    if (l > r) return; // отрезок пустой — выходим
    int t = (l + r) / 2;
    int opt = _l;
    for (int i = max(t, _l); i <= _r; i++) { // TODO: неправильные границы 
        int val = f[i+1][k-1] + cost(i, j);
        if (val < f[t][k])
            f[t][k] = val, opt = i;
    }
    solve(l, t-1, _l, opt, k);
    solve(t+1, r, opt, _r, k);
}

Вызываться она будет просто последовательно для каждого слоя:

In [ ]:
for (int k = 1; k <= m; k++)
    solve(0, n-1, 0, n-1, k);

Теперь пересчет одного «слоя» динамики занимает $O(n \log n)$ вместо $O(n^2)$. Почему? Потому что каждый раз рекурсивная функция уменьшает в два раза хотя бы один из отрезков, так что её глубина будет $O(\log n)$, а значит и каждый элемент будет просмотрен не более $O(\log n)$ раз.

Получается, что асимптотика улучшилась до $O(n m \log n)$.

Оптимизация Кнута

Предыдущий метод основывался на том факте, что $opt[i, j] \leq opt[i, j+1]$. А что, если $opt$ монотонен ещё и по первому параметру?

$$ opt[i-1, j] \leq opt[i, j] \leq opt[i, j+1] $$

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

Давайте теперь просто для каждого состояния перебирать элементы непосредственно от $ opt[i-1, j] $ до $ opt[i, j+1] $. Выясняется, что это работает быстро. Чтобы понять почему, распишем количество элементов, которые мы просмотрим для каждого состояния, и просуммируем:

$$ \sum_{i, j} (opt[i, j+1] - opt[i-1, j] + 1) = nm + \sum_{ij} (opt[i, j+1] - opt[i-1, j]) = O((n+m)n) = O(n^2) $$

Здесь мы заметили, что все элементы, кроме граничных, учитываются в сумме ровно два раза — один раз с плюсом, другой с минусом. Каждый из $opt[i, j]$ не более $O(n)$.

In [ ]:
for (int i = 1; i <= n; i++) {
    for (int j = m; j >= 1; j--) {
        for (int k = opt[i-1][j]; k <= opt[i][j+1]; k++) {
            int val = f[i+1][k-1] + cost(i, j);
            if (val < f[t][k])
                f[t][k] = val, opt[i][j] = i;
        }
    }
}

Сравните с базовым решением — всего 3 новых строчки.

Convex Hull Trick

Этот метод призывает думать об оптимизируемой функции геометрически — посмотрев на cost и увидев там скалярное произведение.

$$ f[i, j] = \min_{k < i} \{f[k, j-1] + (x_{i-1}-x_k)^2 \} = \min_{k < i} \{ f[k, j-1] + x_{i-1}^2 - 2x_{i-1} x_k + x_k^2 \}$$

Посмотрим внимательнее на минимизируемое выражение. $x_{i-1}^2$ не зависит от $k$, значит его можно вынести. Под минимумом останется $ \underbrace{f[k, j-1] + x_k^2}_{a_k} \underbrace{-2x_k}_{b_k} x_{i-1} $.

Это теперь можно переписать как $ \min_k (a_k, b_k) \cdot (1, X_{i-1}) $ (имеется в виду скалярное произведение)

Представим $(a_k, b_k)$ как точки на плоскости. Тогда мы можем построить их нижнюю огибающие и бинарным поиском находить оптимальную, с минимальным скалярным произведением.

TODO: иллюстрация.

TODO: мем про Скуби-Ду.

Ли Шао

Существует другой подход: увидеть здесь не точки и оптимизацию скалярного произведения, и линии и нахождение минимума в точке.

Лямбда-оптимизация

Не «фольклорное» название — дискретный метод множителей Лагранжа.

Пусть у нас есть функция $f(x)$, которую сложно посчитать. Но пусть при этом нам легко посчитать g(x) = .

Заметим следующее:

Давайте заменим $f[i, j]$ на $g_\lambda[i]$ — та же задача, но теперь у нас нет лимита на количество отрезков. Вместо этого мы платим фиксированный «штраф», равный $\lambda$, за использование отрезка.

Давайте сделаем бинпоиск по $\lambda$. Понятно, что для каких-то лямбд мы будем использовать ровно $j$ отрезков. Тогда ответ на динамику $f[i, j] = g[i] - \lambda k$.

Суммируем

TODO: сделать табличку

  • Разделяйка: $O(nm \log n)$, если cost такой, что opt монотонна по одному аргументу.
  • Кнут: $O(nm)$, если cost такой, что opt монотонна по обоим аргументам.
  • CHT: $O(nm)$. В оптимизируемой функции нужно увидеть скалярное произведение.
  • Лагранж: $O(n \log n)$. Функция должна быть выпуклой.

Другие задачи

Как мы увидели, часто оптимизации динамики взаимо заменяемые. Сведение оставляется читателю как упражнение.

Есть $n$ ферм на длинной прямой дороге. Каждая ферма каждую осень производит сколько-то мешков зерна. Требуеттся так поставить $m$ амбаров в некоторых фермах, чтобы суммарная стоимость транспортировки зерна была минимальной. Перевезти 1 мешок зерна на 1 метр стоит 1 доллар.