Монотонность точки перегиба: различия между версиями
KiKoS (обсуждение | вклад) м |
KiKoS (обсуждение | вклад) м |
||
Строка 28: | Строка 28: | ||
* $opt_{i, j} \le opt_{i, j + 1}$ — [[Divide&Conquer оптимизация]] | * $opt_{i, j} \le opt_{i, j + 1}$ — [[Divide&Conquer оптимизация]] | ||
* $opt_{i - 1, j} \le opt_{i, j} \le opt_{i, j + 1}$ — [[оптимизация Кнута]] | * $opt_{i - 1, j} \le opt_{i, j} \le opt_{i, j + 1}$ — [[оптимизация Кнута]] | ||
+ | |||
+ | {{Автор|Константин Амеличев|kik0s}} | ||
+ | [[Категория:Конспект]] | ||
+ | [[Категория:Оптимизации динамики]] |
Версия 10:06, 27 сентября 2019
Пусть в рамках какой-то задачи мы считали "слоистую" динамику $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}$.
Разумеется, в реальных задачах никто ничего не доказывает, потому что утверждение о монотонности обычно интуитивно понятно.
Зачем это нужно?
При разного рода монотонностях точки перегиба можно применять разные оптимизации динамики:
- $opt_{i, j} \le opt_{i, j + 1}$ — Divide&Conquer оптимизация
- $opt_{i - 1, j} \le opt_{i, j} \le opt_{i, j + 1}$ — оптимизация Кнута
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s