![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 20. Минимальные остовные деревья. MST (const Graph &G) : G(G),
MST (const Graph & G): G(G), mst(G.V()), wt(G.V(), G.V()), fr(G.V()) { int min = -1; for (int v = 0; min! = 0; v = min) { min = 0; for (int w = 1; w < G.V(); w++) if (mst[w] == 0) { double P; Edge* e = G.edge(v, w); if (e) if ((P = e-> wt()) < wt[w]) { wt[w] = P; fr[w] = e; } if (wt[w] < wt[min]) min = w; } if (min) mst[min] = fr[min]; } } void show() { for (int v = 1; v < G.V(); v++) if (mst[v]) mst[v]-> show(); } };
Как и в случае реализации алгоритма в общей форме, в нашем распоряжении имеется несколько подходов для обеспечения интерфейсов с АТД, реализующих очередь по приоритету. Один из подходов заключается в том, чтобы использовать очередь ребер, упорядоченную по их приоритетам, аналогично обобщенному поиску на графах, реализованному нами в виде программы 18.10. Программа 20.7 представляет собой реализацию, которая, по существу, эквивалентна программе 18.10, но в то же время она использует подход, в основу которого положены вершины, благодаря чему она может использовать индексированную очередь по приоритетам, в соответствии с изложенным в разделе 9.6. (Мы рассматриваем полную реализацию специального интерфейса с очередью с приоритетами, используемую программой 20.7, в программе 20.10, текст которой приводится в конце данной главы.) Будем называть краевыми вершинами (fringe vertices) подмножество недревесных вершин, которые соединены посредством ребер из бахромы с вершинами дерева, и будем использовать те же векторы mst, fr и wt, индексированные именами вершин, какие применялись в программе 20.6. Очередь с приоритетами содержит индекс каждой краевой вершины (этот элемент очереди обеспечивает доступ к самому короткому ребру, соединяющему краевую вершину с деревом), а также длину этого ребра во втором и третьем векторах. Часть 5. Алгоритмы на графах
Свойство 20.7. Использование реализации алгоритма Прима с поиском по приоритету, в котором для реализации очереди с приоритетами применяется полное бинарное дерево, позволяет вычислить дерево MST за время, пропорциональное Е IgV Доказательство: Этот алгоритм напрямую реализует обобщенную идею алгоритма Прима (добавлять в дерево MST в качестве очередного минимальное ребро, которое соединяет некоторую вершину MST с вершиной, не входящей в MST). Каждая операция для очереди с приоритетами требует выполнения действий, число которых не превосходит значения lgV Каждая вершина выбирается при помощи операции удалить минимальное ребро (remove the minimum); при этом в худшем случае каждое ребро может потребовать выполнения операции изменить приоритет (change priority). ■ Поиск по приоритету представляет собой подходящее обобщение поиска ширину и поиска в глубину, ибо эти методы также могут быть получены за счет соответствующего выбора установок. Например, мы можем (в какой-то степени искусственно) использовать переменную cnt для присвоения уникального приоритета cnt++ каждой вершине, когда помещаем ее в очередь по приоритетам. Если мы определим, что Р есть cnt, мы получаем нумерацию узлов при обходе в прямом порядке и поиск в глубину, поскольку вновь встреченные узлы имеют наивысший приоритет. Если мы определим, что Р есть V-cnt, мы получаем поиск в ширину, поскольку наивысший приоритет в этом случае имеют старые узлы. Присвоение таких значений приоритетов приводят к тому, что очереди с приоритетами ведут себя, соответственно, как стеки и как собственно очереди. Такая эквивалентность представляет чисто академический интерес, поскольку операции на очередях по приоритету не обязательны для поиска в глубину и для поиска в ширину. Кроме того, как уже отмечалось в разделе 18.8, формальное доказательство эквивалентности требует строгого соблюдения правила замены, чтобы получить ту же последовательность вершин как результат выполнения классических алгоритмов. Как мы сможем убедиться далее, поиск по приоритетам охватывает поиск в глубину, поиск в ширину и алгоритм прима, обеспечивающий построение дерева MST, а также несколько других классических алгоритмов. Таким образом, время выполнения всех этих алгоритмов зависит от АТД очереди с приоритетами. В самом деле, мы приходим к общему результату, который охватывает не только две реализации алгоритма Прима, с которыми мы ознакомились в этом разделе, но также и широкий класс фундаментальных алгоритмов обработки графов. Свойство 20.8. Для всех графов и приоритетных функций можно вычислить остовное дерево при помощи поиска по приоритетам за линейное время плюс время, пропорциональное продолжительности выполнения V операций вставок (insert), V операций удалить минимальное ребро (delete the minimum) и Е операций уменьшить ключ (decrease key) в очереди с приоритетами, размер которой не превышает V. Глава 20. Минимальные остовные деревья
В частности, использование реализации очереди с приоритетами на неупорядоченном массиве позволяет получить оптимальное решение для насыщенных графов, которые показывают ту же производительность в худшем случае, что и классическая реализация алгоритма Прима (программа 20.6). То есть, свойства 20.6 и 20.7 представляют собой частные случаи свойства 20.8; на протяжении этой книги мы рассмотрим другие многочисленные алгоритмы, которые существенно отличаются друг от друга только в части выбора функций назначения приоритетов и реализации очередей с приоритетами. Свойство 20.7 представляет собой важный общий результат: устанавливаемая им временная граница есть верхняя граница для худшего случая, которая гарантирует для широкого класса задач обработки графов производительность, отличающуюся от оптимальной (линейное время) не более чем в lgV paз. Однако существуют две причины, в силу которых оно дает в некотором смысле пессимистическую оценку производительности на многих видах графов, с которыми нам приходится сталкиваться на практике. Во-первых, граница lgМ для операций с очередями с приоритетами сохраняется только в тех случаях, когда количество вершин в бахроме пропорционально V, и даже в таком случае это всего лишь верхняя граница. В случае реального фа-фа из практического приложения бахрома может быть небольшим множеством (см. рис. 20.10 и 20.11), а на выполнение реализаций некоторых операций на очереди с приоритетами будет затрачено существенно меньше, чем l gV действий. Хотя этот эффект и заметен, тем не менее он определяет только небольшую составляющую постоянного коэффициента, на который умножается время выполнения; например, доказательство того, что множество составных ребер не может содержать более √ V вершин улучшит граничное значение всего лишь в два раза. Что еще более важно, в общем случае мы выполняем намного меньше, чем E, РИСУНОК 20.10. РЕАЛИЗАЦИЯ АЛГОРИТМА ПРИМА, ОБЕСПЕЧИВАЮЩЕГО ПОСТРОЕНИЕ ДЕРЕВА MST С ИСПОЛЬЗОВАНИЕМ ПОИСКА ПО ПРИОРИТЕТАМ. Используя поиск по приоритетам, алгоритм Прима выполняет обработку вершин и ребер, наиболее близких к дереву МST (показаны серым цветом). Часть 5. Алгоритмы на графах
операций уменьшить ключ, поскольку мы выполняем эту операцию, только когда находим ребро, ведущее в узел, содержащийся в бахроме, которое короче известного на текущий момент ребра такого же типа. Такое событие происходит довольно редко: большая часть ребер не оказывает на очередь с приоритетами никакого влияния (см. упражнение 20.40), Целесообразно в большинстве случаев рассматривать поиск по приоритету как линейный по времени выполнения алгоритм при условии, что V lgV значительно больше Е. АДТ очереди с приоритетами и абстракции обобщенного поиска на графах позволяют проследить связи между различными алгоритмами. Поскольку эти абстракции (и программные механизмы, обеспечивающие поддержку их использования) были разработаны спустя много лет после открытия базовых методов, соответствие алгоритмов их классическим описаниям может интересовать разве что историков. Тем не менее, знания всех основных исторических фактов полезно, когда мы сталкиваемся с описаниями алгоритмов построения дерева MTS в публикациях по научным исследованиям или в других текстах, а понимание того, как эти немногочисленные простые абстракции связывают многих исследователей, разделенных во времени многими десятилетиями, служит убедительным доказательством их значимости и могущества. Учитывая вышесказанное, кратко рассмотрим здесь происхождение этих алгоритмов. Реализация дерева MTS для насыщенных графов, которая фактически эквивалентна программе 20.6, была впервые опубликована Примом (Prim) в 1961 г. и, независимо от него, Дейкстрой (Dijkstra) - несколько позже. Обычно она называется алгоритмом РИСУНОК 20.11. РАЗМЕР МНОЖЕСТВА СОСТАВНЫХ РЕБЕР В УСЛОВИЯХ РЕАЛИЗАЦИИ АЛГОРИТМА ПРИМА, ИСПОЛЬЗУЮЩЕГО ПОИСК ПО ПРИОРИТЕТАМ. Чертеж в нижней части рисунка показывает размеры множества составных ребер по мере продвижения поиска по приоритетам для примера, приведенного на рис. 20.10. Для сравнения соответствующие чертежи для поиска в глубину, для рандомизированного поиска и для поиска в ширину из рис. 18.28, показаны вверху серым цветом. Глава 20. Минимальные остовные деревья 20.6, с тех пор многие исследователи направили свои усилия на поиск эффективных реализаций как ключевого момента отыскания эффективных алгоритмов построения деревьев MTS для разреженных графов.
|