|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[161] 24.2. Алгоритмы Крускала и Прима Оба этих алгоритма следуют описанной схеме, но по-разному выбирают безопасное ребро. В алгоритме Крускала множество рёбер А представляет собой лес, состоящий из нескольких связных компонент (деревьев). Добавляется ребро минимального веса среди всех рёбер, концы которых лежат в разных компонентах. В алгоритме Приме множество А представляет собой одно дерево, Безопасное ребро, добавляемое к А, выбирается как ребро наименьшего веса, соединяющее это уже построенное дерево с некоторой новой вершиной. Алгоритм Крускала В любой момент работы алгоритма Крускала множество А выбранных рёбер (часть будущего остова) не содержит циклов. Оно соединяет вершины графа в несколько связных компонент, каждая из которых является деревом. Среди всех рёре, соединяющих вершины из разных компонент, берётся ребро наименьшего веса. Надо проверить, что оно является безопасным. Пусть (и, v) - такое ребро, соединяющее вершины из компонент С\ и CV Это ребро является лёгким ребром для разреза С\, V\C\, и можно воспользоваться теоремой 24.1 (или прямо следствием 24.2). Реализация алгоритма Крускала напоминает алгоритм вычисления связных компонент (разд. 22.1) и использует структуры данных для непересекающихся множеств (гл. 22), Элементами множеств являются вершины графа. Напомним, что Find-Set(m) возвращает представителя множества, содержащего элемент и. Две вершины и и v принадлежат одному множеству (компоненте), если Find-Set (и) = Find-Set (и). Объединение деревьев выполняется процедурой Union. \textsc{MST-Kruskal}$(G,w)$ 1$A \leftarrow \emptyset$ 2{\bf for} $v\in V[G]$ 3{\bf do} \textsc{Make-Set}$(v)$ 4упорядочить р\"~~а5бра $E$ по весам 5{\bf for} $(u,v)\in E$ (в порядке возрастания веса) 6{\bf do if} \textsc{Find-Set}$(u) \noteq$ \textsc{Find-Set}$(v)$ 7{\bf then} $A \leftarrow A \cup \{(u,v)\}$ 8\textsc{Union} $(u,v)$ 9{\bf return} $A$ На рисунке 24.4 показа работа алгоритма. Сначала (строки 1-3) множество А пусто, и есть \V\ деревьев, каждое из которых содержит по одной вершине. В строке 4 рёбра из Е упорядочиваются по неубыванию веса. В цикле (строки 5-8) мы проверяем, лежат Рис. 24.4 24.4 Работа алгоритма Крускала на графе рис. 24.1. Рёбра растущего леса (А) выделены серым цветом. Рёбра рассматриваются в порядке неубывания весов (текущее ребро показано стрелкой). Если ребро соединяет два различных дерева, оно добавляется к лесу, а деревья сливаются. ли концы ребра в одном дереве. Если да, то ребро нельзя добавить к лесу (не создавая цикла), и оно отбрасывается. Если нет, то ребро добавляется к А (строка 7), и два соединённых им дерева объединяются в одно (строка 8). Подсчитаем время работы алгоритма Крускала. Будем считать, что для хранения непересекающихся множеств используется метод раздела 22.3 (с объединением по рангу и сжатием путей - самый быстрый из известных). Инициализация занимает время 0(V), упорядочение рёбер в строке 4 - O(ElgE). Далее производится О(Е) операций, в совокупности занимающих время 0(Еа(Е,V)), где а - функция, обратная к функции Аккермана (см. раздел 22.4). Поскольку а(Е, V) = o(lgE), общее время работы алгоритма Крускала составляет O(ElgE) (основное время уходит на сортировку). Алгоритм Прима Как и алгоритм Крускала, алгоритм Прима следует общей схеме алгоритма построения минимального остова из раздела 24.1. Он похож на алгоритм Дейкстры поиска кратчайшего пути в графе (раздел 25.2). В этом алгоритме растущая часть остова представляет собой дерево (множество рёбер которого есть А). Как показано на рис. 24.5, формирование дерева начинается с произвольной корневой вершины г. На каждом шаге добавляется ребро наименьшего веса среди рёбер соединяющих вершины этого дерева с вершинами не из дерева. По следствию 24.2 такие рёбра являются безопасными для А, так что в результате получается минимальный остов. При реализации важно быстро выбирать лёгкое ребро. Алгоритм получает на вход связный граф G и корень г минимального покрывающего дерева. В ходе алгоритма все вершины, ещё не попавшие в дерево, хранятся в очереди с приоритетами. Приоритет вершины v определяется значением key[v], которое равно минимальному весу рёбер, соединяющих v с вершинами дерева А. (Если таких рёбер нет, полагаем key[v] = оо.) Поле ir[v] для вершин дерева указывает на родителя, а для вершины v £ Q указывает на вершину дерева, в которую ведёт ребро веса fcet/[u] (одно из таких рёбер, если их несколько). Мы не храним множество А вершин строимого дерева явно; его можно восстановить как A = {(v,jr[v]):veV\{r}\Q}. В конец работы алгоритма очередь Q пуста, и множество A = {(v,n[v]):veV\{r}}. Рис. 24.5 24.5 Работа алгоритма Прима на графе рис. 24.1 с корневой вершиной а Рёбра, входящие в дерево А. выделены серым; вершины дерева - чёрным. На каждом шаге к А добавляется ребро, пересекающее разрез между деревом и его дополнением. Например, на втором шаге можно было бы добавить любое из рёбер (Ь, с) и (а, К). есть множество вершин покрывающего дерева. \textsc{MST-Prim}$(G,W,г)$ 1$Q \leftarrow V[G]$ 2{\bf for} $u\in Q$ 3{\bf do} $key[u] \gets \infty$ 4$key[r] \gets 0$ 5$\pi[r] \gets \textsc{nil}$ 6{\bf while} $Q \noteq \emptyset$ 7{\bf do} $u \leftarrow \textsc{Extract-Min}(Q)$ 8{\bf for} $v\in Adj[u]$ 9{\bf do if} $v\in Q$ и $w(u,v)<key[v]$ 10{\bf then} $\pi(v) \leftarrow u$ 11$key(v) \leftarrow w(u,v)$ На рис. 24.5 показана работа алгоритма Прима. После исполнения строк 1-5 и первого прохода цикла в строках 6--11 дерево состоит из единственной вершины г, все остальные вершины находятся в очереди, и значение &ey[u] для них равно длине ребра из г в v или +оо, если такого ребра нет (в первом случае ir[v] = г. Таким образом, выполнен описанный выше инвариант (дерево есть часть некоторого остова, для вершин дерева поле тг указывает на родителя, а для остальных вершин на «ближайшую» вершину дерева - вес ребра до неё хранится в &еи[и]. Время работы алгоритма Прима зависит от того, как равлизо-вана очередь Q. Если использовать двоичную кучу (глава 7), инициализацию в строках 1-4 можно выполнить с помощью процедуры Build-Heap за время 0(V). Далее цикл выполняется \V\ раз, и каждая операция Extract-Min занимает время 0(lgV), всего 0(V\gV). Цикл for в строках 8-11 выполняется в общей сложности О(Е) раз, поскольку сумма степеней вершин графа равна 2\Е\. Проверку принадлежности в строке 9 внутри цикла for можно реализовать за время 0(1), если хранить состояние очереди ещё и как битовый вектор размера \V\. Присваивание в строке 11 подразумевает выполнение операции уменьшения ключа (Decrease-Key), которая для двоичной кучи может быть выполнена за время 0(lgV). Таким образом, всего получаем 0(V lg V + Elg V) = 0(E\gV) - та же самая оценка, что была для алгоритма Крускала. Однако эта оценка может быть улучшена, если использовать в алгоритме Прима фибоначчиевы кучи. Как мы видели в главе 21, с помощью фиббоначиевой кучи можно выполнять операцию |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||