Монотонность точки перегиба

Материал из Algocode wiki
Перейти к: навигация, поиск

Пусть в рамках какой-то задачи мы считали "слоистую" динамику $dp_{i, j}$, пересчет которой выглядел (в общем случае):

$$dp_{i, j} = \min_{k=1}^{j-1} \{dp_{i-1,k} + f(k + 1, j)\}$$

Обозначим $opt_{i, j} = argmin_{k=1}^{j-1} \{dp_{i-1,k} + f(k + 1, j)\}$ (а среди всех минимумов --- с меньшим $j$). Тогда в большом количестве задач функция $opt_{i, j}$ монотонна.

Например, пусть мы решали задачу о разбиении $n$ положительных чисел на $k$ отрезков с минимальной суммой квадратов их сумм.

Утверждение:
$opt_{i, j - 1} \le opt_{i, j}$

Докажем от противного, что $opt_{i, j} \ge opt_{i, j - 1}$. Пусть существовал элемент $v < opt_{i, j}$, для которого выполнялось

$$dp_{i, v} + (\sum_{t=v}^{j} x_t)^2 < dp_{i, opt_{i, j - 1}} + (\sum_{t=opt_{i, j - 1}}^{j} x_t)^2 $$

$$dp_{i, v} + (\sum_{t=v}^{j} x_t)^2 - (\sum_{t=opt_{i, j - 1}}^{j} x_t)^2 < dp_{i, opt_{i, j - 1}}$$

Обозначим $s = \sum_{t=v}^{opt_{i, j - 1} - 1} x_t$

$$dp_{i, v} + s \cdot (s + 2 \cdot \sum_{t=opt_{i, j - 1}}^{j} x_t) < dp_{i, opt_{i, j - 1}}$$

Но тогда $$dp_{i, v} + s \cdot (s + 2 \cdot \sum_{t=opt_{i, j - 1}}^{j - 1} x_t) \le dp_{i, opt_{i, j - 1}}$$ Этого не может быть, потому что $v \neq opt_{i, j - 1}$.

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

Зачем это нужно?

При разного рода монотонностях точки перегиба можно применять разные оптимизации динамики:



Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s