С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 6
Текст из файла (страница 6)
Если вдруг обнаружится, что два каких-то угла равны, то упорядочим соответствующие точки по удаленности от O, нодля краткости будем говорить просто о сортировке по величине угла.Соединив точки в этом порядке (будем обозначать их P1 , P2 , ..., Pn , приэтом P1 = P), и соединив дополнительно Pn c P1 , мы получим замкнутую несамопересекающуюся ломаную, но ограниченный этой ломаной многоугольник может не быть выпуклым (см. рис.
а). Тогда среди вершин P2 , P3 , ..., Pn найдется хотя бы одна, скажем Pk , вдавленная,которая принадлежит треугольнику Pk−1 OPk+1 при k < n и треугольнику Pn−1 OP1 при k = n (рис. б). Вдавленную вершину можно исключить из дальнейшего рассмотрения, соединив напрямую Pk−1 с Pk+1 ,или, соответственно, P1 с Pn−1 . Удалив все вдавленные вершины, мыполучим требуемый многоугольник. Такова общая идея алгоритма.Задержимся на удалении вдавленных вершин.«Наглядно можно представлять себе дело так: в точках M вбиты гвозди, на которые натянута резинка, охватывающая их все, — эта резинка и будет выпуклой оболочкой множества гвоздей» []. Но в нашем понимании построение выпуклой оболочкипредполагает еще перечисление вершин в порядке их обхода.§ . Асимптотические оценки (два примера)P5P8P5P8P6P7P4а)OP1P6P7P3P4б)OP2P3P2P1Рис.
. a) Точки, упорядоченные по величине угла ∠ P1 OPi , i = 1, 2, ..., n; б) вершина P4 — первая вдавленная вершина в последовательности P2 , P3 , ..., P8 .Вдавленные вершины можно обнаружить просмотром точекP2 , P3 , ..., Pn , P1 : переходя от вершины Pi к вершине Pi+1 , i = 2, 3, ......, n − 1, можно сразу проверять, принадлежит ли Pi треугольникуPi−1 OPi+1, а при переходе от Pn к P1 проверять, принадлежит ли Pnтреугольнику Pn−1 OP1 . Если да, то Pi или соответственно Pn , удаляется, но после этого надо проверить, не окажется ли теперь вдавленнойпредыдущая из неудаленных вершин, — на рис. б видно, что послеудаления P4 вершина P3 становится вдавленной.
Возможно, что удаление одной вдавленной вершины повлечет удаление нескольких ужерассмотренных вершин, но вершина P1 никогда не будет удалена.При i < n − 1 после Pi+1 мы рассматриваем Pi+2 и вновь пытаемсяосвободиться от вдавленных вершин с меньшими номерами и т. д.Последний шаг — переход от Pn к P1 и завершающая попытка освободиться от вдавленных вершин.Затраты этапа построения точек P и O ограничены значением c1 n,где c1 — некоторая константа.Если используется сортировка, сложность которой по числу сравнений есть r(n), то в алгоритме Грэхема может потребоваться не более c2 r(n) операций для сортировки точек по величине угла, константа c2 отражает затраты на сравнение двух углов и сравнение расстояний от O до двух данных точек.Покажем, что описанный процесс удаления вдавленных вершинпотребует затрат, не превосходящих по величине c3 n, где c3 — некоторая константа (в частности, учитывающая затраты на проверку принадлежности точки треугольнику).
В самом деле, если переход от Piк Pi+1 сопровождается проверкой вдавленности некоторого числа vi Глава . Сложности алгоритмов как функции числовых аргументоввершин, то число удаленных при этом вершин равно vi − 1. Но обnP(vi − 1) < n, и,щее число удаленных вершин меньше n. Поэтомукак следствие,i =2nXvi < 2n.(.)i =2Это означает, что сложность TG (n) алгоритма Грэхема по общемучислу арифметических операций и сравнений не превосходит c′ r(n) ++ c′′ n, где c′ и c′′ суть некоторые положительные константы.
Сложность любой сортировки массивов длины n по числу сравнений неможет быть меньше n/2, так как каждый элемент должен пройти хотя бы одно сравнение и в каждом сравнении участвуют два элемента.Имеемn¶ r(n)(c′ + 2c′′ ),TG (n) ¶ c′ r(n) + c′′ n = r(n) c′ + c′′r(n)откуда TG (n) = O(r(n)). При этом у нас нет пока достаточных оснований для утверждения, что TG (n) = Θ(r(n)), потому что нет, например,оснований утверждать, что после выбора P и O может действительно потребоваться r(n) сравнений обсуждаемого типа (ведь мы можемеще выполнять арифметические операции; почему бы не предположить, что, прибегая к ним, можно существенно снизить число сравнений при сортировке), и мы пока можем утверждать только то, чтоTG (n) = Ω(n); эту тему мы отложим до § .После того как точки упорядочены по величине угла, информацию об их координатах можно представить в виде двунаправленного списка, и тогда удаление вдавленных вершин не будет связанос какими-либо перемещениями координат точек, и, подходя формально, можно было бы затраты на перемещения в процессе удалениявдавленных вершин считать равными нулю.
При менее формальномподходе эти затраты можно считать ограниченными сверху значением cn, где c — некоторая константа: переход от массива к двунаправленному списку и, равным образом, в силу (.), работа со ссылкамиво время удаления вдавленных вершин потребуют затрат, ограниченных величинами такого вида. В свою очередь, сложность любой сортировки по числу перемещений элементов не может быть меньшечем n/2 (так как не исключено, например, что изначальный порядок элементов является обратным к требуемому). Отсюда сложностьалгоритма Грэхема по числу перемещений не превосходит произведения некоторой константы и сложности используемой сортировкипо числу перемещений.
Аналогично, для сложности по общему чис-§ . Асимптотические оценки (два примера)лу арифметических операций, сравнений и перемещений мы имеемоценку O(s(n)), где s(n) — соответствующая сложность используемойсортировки.Основываясь на эскизном описании алгоритма Грэхема, мы получили следующее.Для любой сортировки массивов длины n, имеющей некоторуюсложность s(n) по общему числу сравнений и перемещений элементов, существует алгоритм построения выпуклой оболочки n точек,заданных массивом своих координат на плоскости, сложность которого по общему числу арифметических операций, сравнений и перемещений есть O(s(n)).Пространственная сложность алгоритма Грэхема, очевидно, естьO(n).Пример .. Пусть G = (V , E) — ориентированный граф без кратных ребер и v ∈ V .
Вояжем по G, выходящим из вершины v, будемназывать любой путь, который• начинается в вершине v,• не проходит ни по одному из ребер дважды,• завершается в вершине, из которой не выходит ни одного непройденного ребра(вояж не обязательно охватывает все ребра G). Примером выходящего из вершины 1 вояжа в изображенном на рис. графе служит(1, 2, 2, 3, 1, 4).4351267Рис. . Ориентированный граф.Построение какого-то одного выходящего из данной вершины vвояжа может быть выполнено произвольным блужданием по непройденным ребрам графа, завершающимся в вершине, из которой невыходит непройденных ребер. Систематизация блужданий может со- Глава .
Сложности алгоритмов как функции числовых аргументовстоять в том, что, попав в некоторую вершину, мы выбираем дляпродолжения пути ребро, ведущее в вершину с наименьшим доступным номером.Определяемый этим алгоритмом вояж может захватить и все ребра — например, когда граф имеет вид кольца (на рис. изображентакой граф, для которого | E | = | V | = 5). Входом алгоритма являетсяграф G и вершина v.
Если мы рассматриваем | E | как размер входа, то для сложно3сти любого алгоритма построения вояжаобязательно имеет место нижняя оценка Ω(| E |) — ввиду, например, того, что42для любого фиксированного | E | существует граф, имеющий вид кольца. Возникает вопрос, можно ли обосновать верхнююоценку O(| E |)? Если да, то в итоге это дало бы оценку Θ(| E |).51Для представления графов, не имеющих кратных ребер, часто используютсяРис.
. Граф в виде кольцаматрицы смежности. Матрица смежно(любой вояж охватываетсти — квадратная матрица порядка | V |,все ребра).состоящая из нулей и единиц (фактически, булева матрица), в которой элементс индексами i, j равен единице, если и только если из i-й вершинывыходит ребро в j-ю вершину. Такой способ представления действительно удобен во многих задачах.
Но когда речь идет о блужданиях по графу, при которых однажды пройденное ребро изымается издальнейшего рассмотрения, более удобным оказывается представление графа в виде массива a1 , a2 , ..., a| V | списков смежных вершин.В списке ai , i = 1, 2, ..., | V |, в порядке возрастания содержатся номеравершин, в которые входят ребра, выходящие из вершины с номером i.Для графа, приведенного на рис. , имеемa1 = (2, 4), a2 = (2, 3), a3 = (1, 4), a4 = (), a5 = (6), a6 = (5), a7 = ();для графа в виде кольца —a1 = (2), a2 = (3), ...,a| V |−1 = (| V |),a| V | = (1)(в этом графе | V | = | E |). Представление в виде массива списков смежных вершин возможно и для графов, имеющих кратные ребра; в этомслучае номера вершин в каждом списке располагаются в порядкенеубывания.§ .
Асимптотические оценки (два примера)Начав вояж из вершины с номером v, мы смотрим, не пуст ли список av : если он пуст, то вояж закончен. Если же список av не пуст, переносим первый его элемент (пусть это будет, например, i) в списоквершин, через которые шаг за шагом проходит вояж; затем рассматриваем список ai , если он пуст, то вояж закончен, иначе повторяемвсе то же самое, что проделывали в предыдущей вершине, и т. д.:l := cons(v, nil); i := v ;while not null(ai ) do i := car(ai ); l := cons(i, l); ai := cdr(ai ) odМы здесь использовали операции над списками, применяемые в языке Лисп: car — первый элемент списка, cdr — список после удаления первого его элемента, cons — вставка элемента в начало списка,null — предикат проверки пустоты списка, nil — обозначение пустогосписка.Затраты, связанные с удлинением пути на один шаг и с проверкой,не завершен ли вояж, ограничены сверху константой (эти затратысуть четыре операции над списками), длина всего пути не превосходит | E |, и затраты во всех случаях не превосходят произведениянекоторой константы на | E |.Список l содержит в обратном порядке все вершины, через которые последовательно проходит вояж.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
