Построение минимальных выпуклых оболочек
Проведя небольшое научное исследование (проще говоря, выполнив поиск на сайте), обнаружил, что на хабре имеется всего две статьи с тегом вычислительная геометрия, причем одна из них оказалась моей. Т.к. в последнее время я несколько заинтересовался этой тематикой, то решил продолжить тему алгоритмической геометрии рассмотрением задачи построения так называемых минимальных выпуклых оболочек. Хотя рисунок справа и дает проницательному хаброчитателю исчерпывающее объяснение того, что это такое, тем не менее под катом будут даны чуть более формальные определения и описаны два классических алгоритма построения минимальных выпуклых оболочек.
Понятие минимальной выпуклой оболочки
Пусть на плоскости задано конечное множество точек A. Оболочкой этого множества называется любая замкнутая линия H без самопересечений такая, что все точки из A лежат внутри этой кривой. Если кривая H является выпуклой (например, любая касательная к этой кривой не пересекает ее больше ни в одной точке), то соответствующая оболочка также называется выпуклой. Наконец, минимальной выпуклой оболочкой (далее кратко МВО) называется выпуклая оболочка минимальной длины (минимального периметра). Я не проверял (похоже, это можно доказать от противного), но кажется очевидным, что минимальная оболочка просто обязана быть выпуклой. Все введенные понятия иллюстрируются следующим рисунком.
Главной особенностью МВО множества точек A является то, что эта оболочка представляет собой выпуклый многоугольник, вершинами которого являются некоторые точки из A. Поэтому задача поиска МВО в конечном итоге сводится к отбору и упорядочиванию нужных точек из A. Упорядочивание является необходимым по той причине, что выходом алгоритма должен быть многоугольник, т.е. последовательность вершин. Наложим дополнительно условие на порядок расположения вершин — направление обхода многоугольника должно быть положительным (напомню, что положительным называется обход фигуры против часовой стрелки).
Задача построения МВО считается одной из самых простых задач вычислительной геометрии, для нее существует много различных алгоритмов. Ниже мы рассмотрим два таких алгоритма — Грэхема (Graham scan) и Джарвиса (Jarvis march). Их описание иллюстрируется кодом на Питоне. Обоим алгоритмам потребуется функция rotate, побробно описанная в предыдущем моем посте. Напомню, что эта функция определяет, с какой стороны от вектора AB находится точка C (положительное возвращаемое значение соответствует левой стороне, отрицательное — правой).
Алгоритм Грэхема (Graham scan)
Этот алгоритм является трехшаговым. На первом шаге ищется любая точка в A, гарантированно входящая в МВО. Нетрудно сообразить, что такой точкой будет, например, точка с наименьшей x-координатой (самая левая точка в A). Эту точку (будем называть ее стартовой) перемещаем в начало списка, вся дальнейшая работа будет производиться с оставшимися точками. По некоторым соображениям, исходный массив точек A нами меняться не будет, для всех манипуляций с точками будем использовать косвенную адресацию: заведем список P, в котором будут хранится номера точек (их позиции в массиве A). Итак, первый шаг алгоритма заключается в том, чтобы первой точкой в P оказалась точка с наименьшей x-координатой. Код:
Второй шаг в алгоритме Грэхема — сортировка всех точек (кроме P[0]-ой), по степени их левизны относительно стартовой точки R=AP[0]. Будем говорить, что B * рук), я буду использовать сортировку вставками.
*я буду очень признателен тем, кто сможет мне объяснить, как применить в данном случае встроенную питоновскую сортировку.
Итак, сортировка вставками (не забываем про косвенную адресацию и про то, что нулевая точка не сортируется):
Результат сортировки можно проиллюстрировать следующим рисунком.
Если мы теперь соединим точки в полученном порядке, то получим многоугольник, который, однако, не является выпуклым.
Переходим к третьему действию. Все, что нам осталось сделать, так это срезать углы. Для этого нужно пройтись по всем вершинам и удалить те из них, в которых выполняется правый поворот (угол в такой вершине оказывается больше развернутого). Заводим стек S (реально список) и помещаем в него первые две вершины (они, опять же, гарантированно входят в МВО).
Затем просматриваем все остальные вершины, и отслеживаем направление поворота в них с точки зрения последних двух вершин в стеке S: если это направление отрицательно, то можно срезать угол удалением из стека последней вершины. Как только поворот оказывается положительным, срезание углов завершается, текущая вершина заносится в стек.
В итоге в стеке S (который теперь можно рассматривать, как список) оказывается искомая последовательность вершин, причем в нужной нам ориентации, определяющая МВО заданного множества точек A.
Сложность первого и последнего шагов алгоритма является линейной по n (хотя в последнем случае имеется вложенный цикл, однако, каждая вершина внутри этого цикла ровно один раз заносится в стек, и не более одного раза оттуда удаляется), следовательно, сложность всего алгоритма определяется вторым шагом — сортировкой, именно поэтому сортировка вставкой оказывается не лучшим вариантом при больших n. Если ее заменить на быструю сортировку, то получим суммарную сложность алгоритма O(nlogn). Можно ли улучшить это время? Если алгоритм основан на попарном сравнении точек (как у нас), то доказано, что данная оценка в общем случае не улучшаема. С этой точки зрения алгоритм Грэхема оптимален. Тем не менее у него имеется не очень хорошая особенность — он не является адаптивным в том смысле, что не важно, сколько вершин в итоге войдет в МВО (три, пять, десять или n), все равно время будет линейно-логарифмическим. Такой адаптивностью обладает алгоритм Джарвиса, к рассмотрению которого мы плавно и переходим.
Алгоритма Джарвиса
Алгоритм Джарвиса (другое название — алгоритм заворачивания подарков) концептуально устроен проще алгоритма Грэхема. Он является двухшаговым и не требует сортировки. Первый шаг точно такой же — нам нужна стартовая точка, которая гарантированно входит в МВО, берем самую левую точку из A.
На втором шаге алгоритма строится МВО. Идея: делаем стартовую вершину текущей, ищем самую правую точку в A относительно текущей вершины, делаем ее текущей и т.д. Процесс завершается, когда текущей вновь окажется стартовая вершина. Как только точка попала в МВО, больше ее можно не учитывать. Поэтому заведем еще один список H, в котором в правильном порядке будут храниться вершины МВО. В этот список сразу же заносим стартовую вершину, а в списке P эту вершину переносим в конец (где мы ее в конце концов найдем и завершим алгоритм).
Теперь организуем бесконечный цикл, на каждой итерации которого ищем самую левую точку из P относительно последней вершины в H. Если эта вершина стартовая, то прерываем цикл, если нет — то переносим найденную вершину из P в H. После завершения цикла в H находится искомая оболочка, которую мы и возвращаем в качестве результата.
Хм, мне удалось рассказать об алгоритме Джарвиса, не используя картинок. Следующий рисунок иллюстрирует все!
Оценим сложность алгоритма Джарвиса. Первый шаг линеен по n. Со вторым все интереснее. У нас имеется вложенный цикл, число внешних итераций равно числу вершин h в МВО, число внутренних итераций не превышает n. Следовательно, сложность всего алгоритма равна O(hn). Необычным в этой формуле является то, что сложность определяется не только длиной входных данных, но и длиной выхода (output-sensitive algorithm). А дальше как карты точки лягут. В худшем случае все точки из A входят в МВО (т.е. A уже само по себе выпуклый многоугольник), тогда h=n и сложность подскакивает до квадратичной. В лучшем случае (при условии, что точки из A не лежат на одной прямой) h=3 и сложность становится линейной. Осталось заранее понять, какой у нас случай, что сделать не так просто (если у вас нет машины времени ** ), можно только исходить из характера задачи — если точек много и они равномерно заполняют некоторую область, то (возможно) Джарвис будет быстрее, если же данные собраны на границе области, то быстрее будет Грэхем, как-то так…
**Машина времени вообще полезная штука с точки зрения алгоритмов, любая задача, требующая триллиона лет вычислений, с ее помощью может быть решена практически мгновенно — запускаем программу, садимся в машину времени, «летим» в будущее, считываем результат, возвращаемся назад. Осталось придумать, как обеспечить бесперебойную работу компьютера на пару триллионов лет.
Вместо заключения
На мой взгляд, задача построения минимальных выпуклых оболочек — хороший способ войти в тему вычислительной геометрии, достаточно легко придумать свой собственный алгоритм (однако, наверняка это будет вариация алгоритма Джарвиса). Утверждается, что приложений у этой задачи много, большая их часть связана с распознаванием образов, кластеризацией и т.п. Кроме того, задача построения МВО используется в качестве вспомогательного средства при решении более сложных задач вычислительной геометрии. Да, стоит отметить, что у этой задачи имеется весьма интересное трехмерное обобщение.
Алгоритм. Линейный алгоритм
Описание разработки
Создать условия для формирования первичного представления об алгоритме, его исполнении
Познакомить учащихся с понятиями «алгоритм», «линейный алгоритм»
Развивать алгоритмическое мышление
Развивать познавательный интерес, логическое мышление
Развитие умения планировать свою деятельность
Развивать память, внимание
Формировать интерес к изучению предмета
Воспитывать чувство коллективизма
Тип урока: комбинированный урок
Оборудование урока: ПК
Объяснение нового материала
Обобщение и систематизация знаний
Подведение итогов урока
Учитель: Здравствуйте, мои пытливые умы! Тему сегодняшнего урока вы узнаете, если разгадаете ребус
Учитель: запишите в тетрадь число и тему урока: «Алгоритм.Линейный алгоритм»
Объяснение нового материала
Учитель: Вы решили порадовать маму и в день ее рождения испечь любимый торт. Для этого вы возмьете кулинарную книгу и найдете там подходящий рецепт. Например такой: торт «Пай».
Для теста:200г маргарина, 200г сметаны, 3 стакана муки,
Для бисквита: 4 яйца, 1 стакан сахара, 1 стакан муки
Для начинки: 1 стакан яблочного конфитюра, полстакана сахарной пудры.
Муку и масло положить в миску, порубить ножом, чтобы получилась маслянистая крупа, влить сметану, смешанную солью. И быстро замесить тесто. Разложить его на смазанный маслом противень ровным слоем, прижимая пальцами, поставить в хорошо нагретую духовку и слегка подрумянить. Затем вынуть. Смазать яблочной начинкой, сверху залить ровным слоем смеси для бисквита. Снова поставить в печь, убавив огонь. Когда бисквит зарумянится и пропечется, вынуть торт, и обсыпать сахарной пудрой.
Учитель: Чтобы приготовить торт нужно выполнить определенную последовательность действий, описанных в рецепте. Такую последовательность действий принято называть алгоритмом.
Дети: записывают в тетрадь.
Учитель: При составлении алгоритма нужно быть очень внимательным, поскольку даже от одного знака может зависеть смысл всего алгоритма. Вспомните мультфильм, в котором царь должен был подписать указ: «Казнить нельзя помиловать! Смысл меняется только от перестановки запятой. Сравните:
Казнить нельзя, помиловать!
Казнить, нельзя помиловать!
Учитель: Зачем же нам нужны алгоритмы?
Дети: высказывают предположения.
Учитель подводит ребят к идее – алгоритмы нужны для того, чтобы можно было сложные действия разбивать на простые, которые легко выполнить. Кажется, трудно испечь торт, но посмотрите, как легко этот процесс описывает рецепт из кулинарной книги. То есть алгоритм упрощает решение сложной задачи.
Обобщение и систематизация знаний
Учитель: Как вы думаете, можно ли считать алгоритмом приказ, отданный царем из другой сказки: «Поди туда- не знаю куда, принеси то, не знаю что?»
Дети: Нет, нельзя. Непонятно куда нужно идти и что именно принести. Алгоритм задан неточно, непонятно.
Учитель: Давайте, попробуем исполнить несколько линейных алгоритмов /один человек работает у доски, остальные в тетради/
Поменяй местами первую и последнюю буквы в слове
Убери два первых буквы
Припиши слева букву О
Припиши слева букву Т
Убери третью букву
Замени последнюю букву на К
Замени первую букву на букву Л
Убери третью букву
Убери третью букву
Убери третью букву
Вставь третьей буквой букву Ш——ЛЕША
Вот что вышло, когда исполнитель Мик пропустил одну команду.
Всё, что вы хотели знать о динамическом программировании, но боялись спросить
Я был крайне удивлён, найдя мало статей про динамическое программирование (далее просто динамика) на хабре. Мне всегда казалось, что эта парадигма довольно сильно распространена, в том числе и за пределами олимпиад по программированию. Поэтому я постараюсь закрыть этот пробел своей статьёй.
Основы
Пожалуй, лучшее описание динамики в одно предложение, которое я когда либо слышал:
Динамическое программирование — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать. (с) А. Кумок.
Чтобы успешно решить задачу динамикой нужно:
1) Состояние динамики: параметр(ы), однозначно задающие подзадачу.
2) Значения начальных состояний.
3) Переходы между состояниями: формула пересчёта.
4) Порядок пересчёта.
5) Положение ответа на задачу: иногда это сумма или, например, максимум из значений нескольких состояний.
Порядок пересчёта
Существует три порядка пересчёта:
1) Прямой порядок:
Состояния последовательно пересчитывается исходя из уже посчитанных.
2) Обратный порядок:
Обновляются все состояния, зависящие от текущего состояния.
3) Ленивая динамика:
Рекурсивная мемоизированная функция пересчёта динамики. Это что-то вроде поиска в глубину по ацикличному графу состояний, где рёбра — это зависимости между ними.
Элементарный пример: числа Фибоначчи. Состояние — номер числа.
Все три варианта имеют права на жизнь. Каждый из них имеет свою область применения, хотя часто пересекающуюся с другими.
Многомерная динамика
Пример одномерной динамики приведён выше, в «порядке пересчёта», так что я сразу начну с многомерной. Она отличается от одномерной, как вы уже наверно догадались, количеством измерений, то есть количеством параметров в состоянии. Классификация по этому признаку обычно строится по схеме «один-два-много» и не особо принципиальна, на самом деле.
Многомерная динамика не сильно отличается от одномерной, в чём вы можете убедиться взглянув на пару примеров:
Пример №1: Количество СМСок
Раньше, когда у телефонов были кнопки, их клавиатуры выглядели примерно так:
Требуется подсчитать, сколько различных текстовых сообщений множно написать используя не более k нажатий на такой клавиатуре.
Прямой пересчёт:
Обратный пересчёт:
При использовании обратного пересчёта всё проще: мы всегда обращаемся вперёд, так что в отрицательные элементы мы не уйдём.
5) Ответ — это сумма всех состояний.
Пример №2: Конь
4) А теперь самое интересное в этой задаче: порядок. Здесь нельзя просто взять и пройтись по строкам или по столбцам. Потому что иначе мы будем обращаться к ещё не пересчитанным состояниям при прямом порядке, и будем брать ещё недоделанные состояния при обратном подходе.
Есть два пути:
1) Придумать хороший обход.
2) Запустить ленивую динамику, пусть сама разберётся.
Если лень думать — запускаем ленивую динамику, она отлично справится с задачей.
Если не лень, то можно придумать обход наподобие такого:
Этот порядок гарантирует обработанность всех требуемых на каждом шаге клеток при прямом обходе, и обработанность текущего состояния при обратном.
Динамика и матрица переходов
Если никогда не умножали матрицы, но хотите понять этот заголовок, то стоит прочитать хотя бы вики.
А теперь, зачем всё это надо. Умножение матриц обладает свойством ассоциативности, то есть (но при этом не обладает коммутативностью, что по-моему удивительно). Это свойство даёт нам право сделать так: .
А теперь пример посерьёзнее:
Пример №3: Пилообразная последовательность
Для начала решение без матрицы перехода:
Динамика по подотрезкам
Это класс динамики, в котором состояние — это границы подотрезка какого-нибудь массива. Суть в том, чтобы подсчитать ответы для подзадач, основывающихся на всех возможных подотрезках нашего массива. Обычно перебираются они в порядке увеличения длины, и пересчёт основывается, соответственно на более коротких отрезках.
Пример №4: Запаковка строки
Вот Развернутое условие. Я вкратце его перескажу:
Необходимо по строке s узнать длину самой короткой сжатой строки, разжимающийся в неё.
Решается эта задача, как вы уже наверняка догадались, динамикой по подотрезкам.
1) Состояние динамики: d[l][r] — сжатая строка минимальной длины, разжимающаяся в строку s[l:r]
2) Начальные состояния: все подстроки длины один можно сжать только в них самих.
3) Пересчёт динамики:
У лучшего ответа есть какая-то последняя операция сжатия: либо это просто строка из заглавных букв, или это конкатенация двух строк, или само сжатие. Так давайте переберём все варианты и выберем лучший.
Пример №5: Дубы
Динамика по поддеревьям
Параметром состояния динамики по поддеревьям обычно бывает вершина, обозначающая поддерево, в котором эта вершина — корень. Для получения значения текущего состояния обычно нужно знать результаты всех своих детей. Чаще всего реализуют лениво — просто пишут поиск в глубину из корня дерева.
Пример №6: Логическое дерево
Требуется найти минимальное количество изменений логических операций во внутренних вершинах, такое, чтобы изменилось значение в корне или сообщить, что это невозможно.
Динамика по подмножествам
В динамике по подмножествам обычно в состояние входит маска заданного множества. Перебираются чаще всего в порядке увеличения количества единиц в этой маске и пересчитываются, соответственно, из состояний, меньших по включению. Обычно используется ленивая динамика, чтобы специально не думать о порядке обхода, который иногда бывает не совсем тривиальным.
Пример №7: Гамильтонов цикл минимального веса, или задача коммивояжера
Динамика по профилю
Классическими задачами, решающимися динамикой по профилю, являются задачи на замощение поля какими-нибудь фигурами. Причём спрашиваться могут разные вещи, например, количество способов замощения или замощение минимальным количеством фигур.
Профиль — это k (зачастую один) столбцов, являющиеся границей между уже замощённой частью и ещё не замощённой. Эта граница заполнена только частично. Очень часто является частью состояния динамики.
Почти всегда состояние — это профиль и то, где этот профиль. А переход увеличивает это местоположение на один. Узнать, можно ли перейти из одного профиля в другой можно за линейное от размера профиля время. Это можно проверять каждый раз во время пересчёта, но можно и предподсчитать. Предподсчитывать будем двумерный массив can[mask][next_mask] — можно ли от одной маски перейти к другой, положив несколько фигурок, увеличив положение профиля на один. Если предподсчитывать, то времени на выполнение потребуется меньше, а памяти — больше.
Пример №8: Замощение доминошками
Здесь профиль — это один столбец. Хранить его удобно в виде двоичной маски: 0 — не замощенная клетка столбца, 1 — замощенная. То есть всего профилей .
0) Предподсчёт (опционально): перебрать все пары профилей и проверить, что из одного можно перейти в другой. В этой задаче это проверяется так:
Примеры переходов (из верхнего профиля можно перейти в нижние и только в них):
Полученная асимптотика — .
Динамика по изломанному профилю
Это очень сильная оптимизация динамики по профилю. Здесь профиль — это не только маска, но ещё и место излома. Выглядит это так:
Теперь, после добавления излома в профиль, можно переходить к следующему состоянию, добавляя всего одну фигурку, накрывающую левую клетку излома. То есть увеличением числа состояний в N раз (надо помнить, где место излома) мы сократили число переходов из одного состояния в другое с до . Асимптотика улучшилась с до .
Переходы в динамике по изломанному профилю на примере задачи про замощение доминошками (пример №8):
Восстановление ответа
Иногда бывает, что просто знать какую-то характеристику лучшего ответа недостаточно. Например, в задаче «Запаковка строки» (пример №4) мы в итоге получаем только длину самой короткой сжатой строки, но, скорее всего, нам нужна не её длина, а сама строка. В таком случае надо восстановить ответ.
В каждой задаче свой способ восстановления ответа, но самые распространенные:
Небольшие оптимизации
Память
Зачастую в динамике можно встретить задачу, в которой состояние требует быть посчитанными не очень большое количество других состояний. Например, при подсчёте чисел Фибоначчи мы используем только два последних, а к предыдущим уже никогда не обратимся. Значит, можно про них забыть, то есть не хранить в памяти. Иногда это улучшает асимптотическую оценку по памяти. Этим приёмом можно воспользоваться в примерах №1, №2, №3 (в решении без матрицы перехода), №7 и №8. Правда, этим никак не получится воспользоваться, если порядок обхода — ленивая динамика.
Время
Иногда бывает так, что можно улучшить асимптотическое время, используя какую-нибудь структуру данных. К примеру, в алгоритме Дейкстры можно воспользоваться очередью с приоритетами для изменения асимптотического времени.
Замена состояния
В решениях динамикой обязательно фигурирует состояние — параметры, однозначно задающие подзадачу, но это состояние не обязательно одно единственное. Иногда можно придумать другие параметры и получить с этого выгоду в виде снижения асимптотического времени или памяти.
Пример №9: Разложение числа
Решение №1:
Решение №2:
Строки здесь обозначают слагаемые.
Первое решение последовательно добавляет по одной строчке внизу таблицы, а второе — по одному столбцу слева таблицы. Вариантов размера следующей строчки много — главное, чтобы она была больше предыдущей, а столбцов — только два: такой же как предыдущий и на единичку больше.
Заключение
Основным источником была голова, а туда информация попала с лекций в Летней Компьютерной Школе (для школьников), а также кружка Андрея Станкевича и спецкурса Михаила Дворкина (darnley).
Спасибо за внимание, надеюсь эта статья кому-нибудь пригодится! Хотя мне уже пригодилась — оказывается, написание статьи это хороший способ всё вспомнить.
