Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 20, Минимальные остовные деревья
|
|
становится пропорциональным сумме Е + V lgV. Полные бинарные деревья Фибоначчи являются более сложными структурами, нежели биномиальные очереди; они несколько неудобны при использовании на практике, но в то же время некоторые из простых реализации очередей с приоритетами обладают сходными характеристиками производительности (см. раздел ссылок).
Таблица 20.1. Затраты на алгоритмы построения дерева MST
Данная таблица подводит итоги затрат (худший случай времени прогона) на выполнение алгоритмов построения дерева MST для алгоритмов, изучение которых проводилось в данной главе. Приводимые здесь формулы основаны на предположении, что такое дерево MST существует и существует X ребер, длина которых не превосходит размеров самого длинного ребра в дереве MST (см. свойство 20.10). Границы худшего случая могут оказаться чрезмерно консервативными, чтобы оказаться полезными для прогнозирования производительности графов на практике. Рассматриваемые алгоритмы выполняются за время, близкое к линейному, причем в широком диапазоне реальных ситуаций.
Один из эффективных подходов связан с применением сортировки с поразрядным обменом в реализации очереди с приоритетами. По производительности такие методы обычно эквивалентны методу Крускала или даже методам, предполагающим применение поразрядной сортировки в качестве метода, использующего частичную сортировку, который мы обсуждали в разделе 20.4.
Другой давно известный простой подход, предложенный Д. Джонсоном (D. Jonhson) в 1977 г., является наиболее эффективным методом: очередь с приоритетами для алгоритма Прима реализуется с помощью d-арных частично упорядоченных полных деревьев, а не с помощью стандартных полных бинарных деревьев (см. рис. 20.17). Программа 20.10 представляет собой полную реализацию интерфейса очереди по приоритету, который мы использовали ранее и в основу которого положен этот метод. Для такой реализации очереди с приоритетами на выполнение операции decrease key требуется менее log(d)V шагов, а для выполнения операции remove the minimum требуется время, пропорциональное d log(d)V По свойству 20.8 подобное поведение приводит к тому, что время выполнения алгоритма Прима будет пропорционально Vd log(d)V + E log(d)V, которое линейно для графов, не относящихся к категории разреженных.
Часть 5. Алгоритмы на графах
Свойство 20.12. Пусть задан граф с V вершинами и Е ребрами и пусть d обозначает насыщенность Е / V. Если d < 2, то время выполнения алгоритма Прима пропорционально V lgV. В противном случае мы можем уменьшить время выполнения в худшем случае в lg(E/V) раз, воспользовавшись в качестве очереди с приоритетами [ Е/V]-арным частично упорядоченным полным деревом.
Доказательство: В продолжение рассуждений из предыдущего параграфа отметим, что число шагов есть Vd log(d)V+ E log(d)V, таким образом, время выполнения в лучшем случае пропорционально E logdV= (E lgV)/lgd.■
Если Е пропорционально V 1+в, по свойству 20.12 время выполнения в худшем случае пропорционально Е/е, и значение линейно при любом значении константы е. Например, если число ребер пропорционально V 3/2, то затраты не превышают 2Е; если число ребер пропорционально V 4/3, то затраты не превышают 3E, и если число ребер пропорционально V5/4, то затраты не превышают 4 Е. Для графа с одним миллионом вершин затраты меньше 6E, если насыщенность не превышает 10.
Таблица 20.2. Эмпирические исследования алгоритмов, вычисляющих дерево MST__________
Эта таблица показывает относительное время выполнения различных алгоритмов вычисления MST на случайных взвешенных графах разной насыщенности. При малых значениях насыщенности лучшие результаты дает алгоритм Крускала, поскольку он позволяет применять быструю сортировку. При больших значениях насыщенности лучшей остается классическая реализация алгоритма Прима, поскольку в этом случае отпадает необходимость в непроизводительных затратах на предварительную обработку списков. Для графов с промежуточной насыщенностью реализация алгоритма Прима с поиском по приоритету выполняется за время, не превышающее времени, необходимого для проверки каждого ребра графа, умноженного на небольшое постоянное значение.
Глава 20. Минимальные остовные деревья
Обозначения:
С Извлекается всего ребер.
Н Алгоритм Прима (списки смежных вершин/индексированное частично упорядоченное полное бинарное дерево).
J Версия Джонсона алгоритма Прима (очередь с приоритетами в виде частично упорядоченного полного d-арного дерева.
Р Алгоритм Прима (представление графа в виде матрицы смежности).
К Алгоритм Крускала.
К* Версия алгоритма Крускала с частичной сортировкой.
В Алгоритм Борувки.
е Исследованные ребра (операции union).
Соблазн таким способом минимизировать границы времени выполнения алгоритмов для худшего случая облегчается пониманием того факта, что части Vd logdV затрат избежать не удается (для операции remove the minimum мы должны исследовать d потомков в частично упорядоченном полном d-арном дереве по мере того, как мы продолжаем проверку ребер, перемещаясь вниз по дереву), однако части Е lgV, по-видимому, можно избежать (ибо большая часть ребер не требует обновления очереди с приоритетами, как было показано при обсуждении свойства 20.8).
Для типовых графов, подобных тем, результаты исследования которых отражены в таблице 20.2, уменьшение параметра d не оказывает влияния на время выполнения, а использование больших значений d может слегка замедлить реализацию. Тем не менее, небольшая защита, предусмотренная для производительности в худшем случае, делает целесообразной реализацию этого метода в силу ее простоты. В принципе, мы можем настроить реализацию таким образом, чтобы она выбирала оптимальное значение d для некоторых типов графов (выбирайте наибольшее значение, которое не замедляет выполнение алгоритма), но небольшое фиксированное значение (например, 3, 4 или 5) вполне подойдет, исключение могут представлять конкретные крупные классы графов с нестандартными характеристиками.
РИС. 20.17.2-, 3- И 4-АРНЫЕ ЧАСТИЧНО УПОРЯДОЧЕННЫЕ ПОЛНЫЕ ДЕРЕВЬЯ
Когда мы сохраняем стандартное бинарное полное частично упорядоченное дерево в виде массива (диаграмма вверху), мы используем косвенные связи для перехода из некоторого узла i вниз по дереву в его дочерние 2i и 2i+1 узлы и вверх по дереву в его предок //2. В 3-нарном полном частично упорядоченном дереве (диаграмма в центре) соответствующими связями узла i являются связи с дочерними узлами 3i—1, 3i и 3i+1 и с их родителем [ (i+1)/3]. Наконец, в 4-нарном полном частично упорядоченном дереве (диаграмма внизу) косвенными связями узла i являются связи с дочерними узлами 4i-2, 4i—1, 4i и 4i+1 и с их родителем [ (/+2)/4]. Увеличение коэффициента ветвления в реализации полного частично упорядоченного дерева может оказаться полезным в приложениях, подобных алгоритму Прима, в условиях которых требуется выполнение большого числа операций decrease key.
Часть 5, Алгоритмы на графах
Использование частично упорядоченных полных d-арных деревьев нецелесообразно для разреженных графов, поскольку d должно быть больше или равным 2, а из этого условия следует, что мы не можем получить асимптотическое время выполнения, меньше чем V lgV Если насыщенность принимает небольшое постоянное значение, то линейный по времени выполнения алгоритм построения дерева MST будет выполняться за время, пропорциональное V.
Цель разработки практических алгоритмов для вычисления дерева MST для разреженных графов, обеспечивающих построение дерева MST за линейное время, труднодостижима. Интенсивным исследованиям подверглись различные варианты алгоритма Борувки как базиса алгоритмов вычисления дерева MST на сильно разреженных графах за почти линейное время (см. раздел ссылок). Такие исследования позволяют надеяться на то, что нам, наконец, удастся получить линейный во времени алгоритм, пригодный для практических целей, и они даже показали существование рандомизированного линейного по времени алгоритма. И хотя в общем случае эти алгоритмы достаточно сложны, упрощенные версии некоторых из них могут зарекомендовать себя на практике как весьма полезные. В то же время, мы можем использовать рассмотренные здесь базовые алгоритмы для вычисления дерева MST за линейное время в большинстве практических ситуаций, хотя, возможно, потребуется заплатить дополнительную цену в виде множителя lgV для разреженных графов.
Программа 20.10. Реализация очереди с приоритетами в виде многопозиционного
частично упорядоченного полного дерева_____________________________________
Этот класс использует частично упорядоченное полное дерево с многократным ветвлением в узлах для реализации непрямого интерфейса для очереди с приоритетами, которая используется в данной книге. В его основе лежат изменения, внесенные в программу 9.12, в рамках которых конструктор принимает ссылки на вектор приоритетов, чтобы стала возможной реализация функций getmin и lower вместо delmax и change и обобщение функций fixUp и fixDown, благодаря которым они могут поддерживать d-арное сортирующее дерево (так, что операция remove the minimum выполняется за время, пропорциональное d logdV, в то же время операция decrease the key требует для своего выполнения logdV шагов).
template < class keyType> class PQi { int d, N;
vector< int> pq, qp; const vector< keyType> & a; void exch (int i, int j)
{ int t = pq[i]; pq[i] = pq[j]; pq[j] = t; qp[pq[i]] = i; qp[pq[j]] = j; > void fixUp (int k)
{ while (k > 1 & & a[pq[(k+d-2)/d]] > a[pq[k]])
{ exch(k, (k+d-2)/d); k = (k+d-2)/d; } } void fixDown (int k, int N) { int j;
while ((j = d*(k-l)+2) < = N) { for (int i a j+1; i < j+d & & i < = N; i++)
if (a[pq[j]] > a[pq[i]]) j = i; if (! (a[pq[k]] > a[pq[j]])) break; exch(k, j); k = j; } }