Convex hull trick — различия между версиями
(→Альтернативный подход) |
(→Альтернативный подход) |
||
Строка 126: | Строка 126: | ||
[[Файл:picture5convexhull.png]] | [[Файл:picture5convexhull.png]] | ||
− | Докажем то, что описанный выше алгоритм корректен. | + | Докажем то, что описанный выше алгоритм корректен. Для этого достаточно показать, что если имеются 3 вектора a, b, c, расположенные как на рис. 5, т.е. точка b не лежит на выпуклой оболочке векторовч <tex>0, a, b, c </tex> : <tex> \Leftrightarrow |[a-b, b-c]| < 0 </tex> |
{{Теорема | {{Теорема | ||
|id=th12392. | |id=th12392. | ||
− | |statement=Если есть 3 вектора a, b, c, | + | |statement=Если есть 3 вектора a, b, c, таких что <tex>|[a-b, b-c]| < 0</tex> то либо (a, u[i]) < (b, u[i]), либо (c, u[i]) < (b, u[i]). |
− | |proof= | + | |proof=<tex>|[a-b, b-c]| < 0 \Leftrightarrow (a_{x} - b_{x})\cdot(b_{y} - c_{y}) < (a_{y} - b_{y}) \cdot (b_{x} - c_{x})</tex> (*). Предположим (от противного), что <tex>(b, u[i]) < (a, u[i]) \Leftrightarrow b_{x} + a[i] \cdot b_{y} < c_{x} + a[i] \cdot c_{y} \Leftrightarrow (b_{x} - c_{x}) < a[i] \cdot (c_{y} - b_{y})</tex> и <tex>(b, u[i]) < (c, u[i]) \Leftrightarrow b_{x} + a[i] \cdot b_{y} < a_{x} + a[i] \cdot a_{y} \Leftrightarrow (a_{x} - b_{x}) > a[i] \cdot (b_{y} - a_{y})</tex>. |
Подставим эти неравенства в (*). Получим цепочку неравенств : <tex>a[i] \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y}) = a[i]</tex><tex> \cdot (b_{y} - a_{y}) \cdot </tex><tex>(b_{y} - c_{y})</tex> <tex> < (a_{x} - b_{x})</tex><tex> \cdot (b_{y} - c_{y})</tex><tex> < (a_{y} - b_{y}) \cdot </tex><tex>(b_{x} - c_{x})</tex> <tex>< a[i] \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y})</tex>. Получили противоречие : <tex>a[i] \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y}) < a[i] \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y})</tex>. Значит предположение неверно, чтд. | Подставим эти неравенства в (*). Получим цепочку неравенств : <tex>a[i] \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y}) = a[i]</tex><tex> \cdot (b_{y} - a_{y}) \cdot </tex><tex>(b_{y} - c_{y})</tex> <tex> < (a_{x} - b_{x})</tex><tex> \cdot (b_{y} - c_{y})</tex><tex> < (a_{y} - b_{y}) \cdot </tex><tex>(b_{x} - c_{x})</tex> <tex>< a[i] \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y})</tex>. Получили противоречие : <tex>a[i] \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y}) < a[i] \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y})</tex>. Значит предположение неверно, чтд. |
Версия 20:07, 18 января 2017
Convex hull trick -- один из методов оптимизации динамического программирования [[1]], использующий идею выпуклой оболочки. Позволяет улучшить ассимптотику решения некоторых задачь, решемых методом динамического программирования с до . Техника впервые появилась в 1995 году (задачу на нее предложили в USACO -- национальной олимпиаде США по программированию). Массовую известность получила после IOI (международной олимпиады по программированию для школьников) 2002.
Содержание
Пример задачи, решаемой методом convex hull trick
Рассмотрим задачу на ДП:
Задача: |
Есть бензопилы. Но пила устроена так, что она может спиливать только по 1 метру от дерева, к которому ее применили. Также после срубленного метра (любого дерева) пилу нужно заправлять, платя за бензин определенной кол-во монет. Причем стоимость бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен (убывание и возрастание нестрогие) , то цена заправки равна . Изначально пила заправлена. Также известны следующие ограничения : возрастают, убывают. Изначально пила заправлена. | деревьев с высотами (в метрах). Требуется спилить их все, потратив минимальное количество монет на заправку
(Задача H с Санкт-Петербургских сборов к РОИ 2016[2])
Наивное решение
Сначала заметим важный факт : т.к.
убывают (нестрого) и , то все неотрицательны. Понятно, что нужно затратив минимальную стоимость срубить последнее ( -е) дерево, т.к. после него все деревья можно будет рубить бесплатно (т.к. ). Посчитаем следующую динамику : - минимальная стоимость, заплатив которую можно добиться того, что дерево номер будет срублено. База динамики : , т.к. изначально пила заправлена и высота первого дерева равна 1, по условию задачи. Переход динамики : понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта идея относится скорее к теме жадных алгоритмнов, чем к теме данной статьи). Поэтому перед -м деревом мы обязательно срубили какое-то -е, причем . Поэтому чтобы найти нужно перебрать все и попытаться использовать ответ для дерева намер . Итак, пусть перед -м деревом мы полностью срубили -е, причем высота -го дерева составляет , а т.к. последнее дерево, которое мы срубили имеет индекс , то стоимость каждого метра -го дерева составит . Поэтому на сруб -го дерева мы потратим монет. Также не стоит забывать, ситуацию, когда -е дерево полностью срублено, мы получили не бесплатно, а за монет. Итогвая формула пересчета : .Посмотрим на код выше описанного решения:
int(int a[n], int c[n]) dp[1] = 0 dp[2] = dp[3] = ... = dp[n] = for i = 1..n-1 dp[i] = for j = 0..i-1 if (dp[j] + a[i] c[j] < dp[i]) dp[i] = dp[j] + a[i] c[j] return dp[n]
Нетрудно видеть, что такая динамика работает за
.Ключевая идея оптимизации
Для начала сделаем замену обозначений. Давайте обозначим
за , за , а за .Теперь формула приняла вид
. Выражение - это в точности уравнение прямой вида .Сопоставим каждому
, обработанному ранее, прямую . Из условия « убывают уменьшаются с номером » следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффициент. Давайте нарисуем несколько таких прямых :Выделим множество точек
, таких что все они принадлежат одной из прямых и при этом нету ни одной прямой , такой что . Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых (её еще называют нижней ошибающей множества прямых на плоскости). Назовем ее « ». Видно, что множество точек представляет собой выпуклую вверх функцию.Цель нижней огибающей множества прямых
Пусть мы считаем динамику для
-го дерева. Его задает . Итак, нам нужно для данного найти . Это выражение есть . Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координаты x следует то, что отрезок, который пересекает прямую , можно найти бинарным поиском. Это потребует времени на поиск такого , что . Теперь осталось научиться поддерживать множество прямых и быстро добавлять -ю прямую после того, как мы посчитали .Воспользуемся идеей алгоритма построения выпуклой оболочки множества точек. Заведем 2 стека
и , которые задают прямые в отсортированном порядке их угловыми коэффицентами и свободными членами. Рассмотрим ситуацию, когда мы хотим добавить новую ( -тую) прямую в множество. Пусть сейчас в множестве лежит прямых (нумерация с 1). Пусть - точка пересечения -й прямой множества и -й, а - точка пересечения новой прямой, которую мы хотим добавить в конец множества и -й. Нас будут интересовать только их -овые координаты и , соответственно. Если оказалось, что новая прямая пересекает -ю прямую выпуклой оболочки позже, чем -я -ю, т.е. , то -ю удалим из нашего множества, иначе - остановимся. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2, либо не станет меньшеАсимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно
раз добавится в стек и максимум раз удалится. Значит время работы перестройки выпуклой оболочки займет суммарно.Теорема: |
Алгоритм построения нижней огибающей множества прямых корректен. |
Доказательство: |
Достаточно показать, что последнюю прямую нужно удалить из множества т.и т.т., когда она наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем последняя - предпоследнюю. Пусть - уравнение новой прямой, - уравнения прямых множества. Тогда т.к. , то при , а т.к. , то при . Если , то при , т.е. на отрезке прямая номер sz лежит ниже остальных и её нужно оставить в множестве. Если же , то она ниже всех на отрезке , т.е. её можно удалить из множества |
Детали реализации:
Будем хранить 2 массива :
- -координаты, начиная с которых прямые совпадают с выпуклой оболочкой (т.е. i-я прямая совпадает с выпуклой оболочкой текущего множества прямых при ) и - номера деревьев, соответствующих прямым (т.е. -я прямая множества, где соответствует дереву номер ). Также воспользуемся тем, что возрастают (по условию задачи), а значит мы можем искать первое такое , что не бинарным поиском, а методом двух указателей за операций суммарно. Также массив front[] можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси x до ближайшего целого (*), т.к. на самом деле мы, считая динамику, подставляем в уравнения прямых только целые , а значит если -я прямая пересекается с -й в точке (z-целое, ), то мы будем подставлять в их уравнения или . Поэтому можно считать, что новая прямая начинает совпадать с выпуклой оболочкой, начиная сРеализация
int(int a[n], int c[n]) st[1] = 1 from[1] = - // первая прямая покрывает все x-ы, начиная с -∞ sz = 1 // текущий размер выпуклой оболочки pos = 1 // текущая позиция первого такого j, что x[i] \geqslant front[st[j]] for i = 2..n while (front[pos] < x[i]) // метод 1 указателя (ищем первое pos, такое что x[i] покрывается "областью действия" st[pos]-той прямой pos = pos + 1 j = st[pos] dp[i] = K[j] a[i] + B[j] if (i < n) // если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку K[i] = c[i] // наши переобозначения переменных B[i] = dp[i] // наши переобозначения переменных x = - while true j = st[sz] x = divide(B[j] - B[i], K[i] - K[j]) // x-координата пересечения с последней прямой оболочки, округленное в нужную сторону (*) if (x > from[sz]) break // перестаем удалять последнюю прямую из множества, если новая прямая пересекает ее позже, чем начинается ее "область действия" sz = sz - 1// удаляем последнюю прямую, если она лишняя st[sz + 1] = i from[sz + 1] = x // добавили новую прямую sz = sz + 1 return dp[n]
Здесь функция
(a, b) возвращает нужное(*) округление a / b. Приведем её код :int
(int a, int b)
delta = 0
if (a mod b ≠ 0) delta = 1
if ((a > 0 and b > 0) or (a < 0 and b < 0)) return [a / b] + delta
return -[|a| / |b|]
Такая реализация будет работать за O(n).
Динамический convex hull trick
Заметим, что условия на прямые, что [3]).
возрастает/убывает и убывает/возрастает выглядят достаточно редкими для большинства задач. Пусть в задаче таких ограничений нет. Первый способ борьбы с этой проблемой - отсортировать входные данные нужным образом, не испортив свойств задачи (пример : задача G c Санкт-Петербургских сборов к РОИ 2016 Но рассмотрим общий случай. По-прежнему у нас есть выпуклая оболочка прямых, имея которую мы за
Чтобы уметь вставлять прямую в множество будем хранить
(или любой аналог в других языках программирования) пар = . Когда приходит новая прямая, ищем последнюю прямую с меньшим угловым коэффицентом, чем у той прямой, которую мы хотим добавить в множество. Поиск такой прямой занимает . Начиная с найденной прямой выполняем "старый" алгоритм (удаляем, пока текущая прямая множества бесполезна). И симметричный алгоритм применяем ко всем прямым справа от нашей (удаляем правого соседа нашей прямой, пока она пересекает нас позже, чем своего правого соседа).Асимптотика решения составит
на каждый из запросов «добавить прямую» + суммарно на удаление прямых, т.к. по-прежнему каждая прямая не более одного раза удалится из множества, а каждое удаление из std::set занимает времени. Итого .Альтернативный подход
Другой способ интерпретировать выражение
заключается в том, что мы будем пытаться свести задачу к стандартной выпуклой оболочке множества точек. Перепишем выражение средующим образом : , т.е. запишем как скалярное произведение векторов и . Вектора хотелось бы организовать так, чтобы за находить вектор, максимизирующий выражение . Посмотрим на рис. 5. Заметим интуитивно очевидный факт : красная точка (вектор) не может давать более оптимальное значение одновременно чем обе синие точки. По этой причине нам достаточно оставить выпуклую оболочку векторов , а ответ на запрос - это поиск , максимизирующего проекцию на . Это задача поиска ближайшей точки выпуклого многоугольника (составленного из точек выпуклой оболочки) к заданной прямой (из в ). Ее можно решить за двумя бинарными или одним тернарным поиском Асимптотика алгоритма по-прежнему составитДокажем то, что описанный выше алгоритм корректен. Для этого достаточно показать, что если имеются 3 вектора a, b, c, расположенные как на рис. 5, т.е. точка b не лежит на выпуклой оболочке векторовч
:Теорема: |
Если есть 3 вектора a, b, c, таких что то либо (a, u[i]) < (b, u[i]), либо (c, u[i]) < (b, u[i]). |
Доказательство: |
Подставим эти неравенства в (*). Получим цепочку неравенств : (*). Предположим (от противного), что и . . Получили противоречие : . Значит предположение неверно, чтд. |
Из доказанной теоремы и следует корректность алгоритма.
См. также
2) http://neerc.ifmo.ru/wiki/index.php?title=Динамическое_программирование