Нахождение минимально охватывающего дерева
Охватывающим деревом (или остовом) неориентированного графа называется подграф графа , который является деревом и содержит все вершины из . Определив вес подграфа для взвешенного графа как сумму весов входящих в подграф дуг, тогда под минимально охватывающим деревом (МОД) будем понимать охватывающее дерево минимального веса. Содержательная интерпретация задачи нахождения МОД может состоять, например, в практическом примере построения локальной сети персональных компьютеров с прокладыванием наименьшего количества соединительных линий связи. Дадим краткое описание алгоритма решения поставленной задачи, известного под названием метода Прима (Prim) [8]. Алгоритм начинает работу с произвольной вершины графа, выбираемого в качестве корня дерева, и в ходе последовательно выполняемых итераций расширяет конструируемое дерево до МОД. Пусть есть множество вершин, уже включенных алгоритмом в МОД, а величины , , характеризуют дуги минимальной длины от вершин, еще не включенных в дерево, до множества , т.е. (если для какой либо вершины не существует ни одной дуги в , значение устанавливается в ). В начале работы алгоритма выбирается корневая вершина МОД и полагается , . Действия, выполняемые на каждой итерации алгоритма Прима, состоят в следующем: - определяются значения величин для всех вершин, еще не включенные в состав МОД; - выбирается вершина графа , имеющая дугу минимального веса до множества ; - включение выбранной вершины в . После выполнения итераций метода МОД будет сформировано; вес этого дерева может быть получен при помощи выражения . Трудоемкость нахождения МОД характеризуется квадратичной зависимостью от числа вершин графа . Оценим возможности для параллельного выполнения рассмотренного алгоритма нахождения минимально охватывающего дерева. Итерации метода должны выполняться последовательно и, тем самым, не могут быть распараллелены. С другой стороны, выполняемые на каждой итерации алгоритма действия являются независимыми и могут реализовываться одновременно. Так, например, определение величин может осуществляться для каждой вершины графа в отдельности, нахождение дуги минимального веса может быть реализовано по каскадной схеме и т.д. Распределение данных между процессорами вычислительной системы должно обеспечивать независимость перечисленных операций алгоритма Прима. В частности, это может быть обеспечено, если каждая вершина графа располагается на процессоре вместе со всей связанной с вершиной информацией. Соблюдение данного принципа приводит к тому, что при равномерной загрузке каждый процессор , , будет содержать набор вершин , , , соответствующий этому набору блок из величин , , и вертикальную полосу матрицы инцидентности графа из соседних столбцов, а также общую часть набора и формируемого в процессе вычислений множества вершин . С учетом такого разделения данных итерация параллельного варианта алгоритма Прима состоит в следующем: - определяются значения величин для всех вершин, еще не включенные в состав МОД; данные вычисления выполняются независимо на каждом процессоре в отдельности; трудоемкость такой операции ограничивается сверху величиной (на первой итерации алгоритма необходим перебор всех вершин, что требует вычислений порядка ); - выбирается вершина графа , имеющая дугу минимального веса до множества ; для выбора такой вершины необходимо осуществить поиск минимума в наборах величин , имеющихся на каждом из процессоров (количество параллельных операций ), и выполнить сборку полученных значений (длительность такой операции передачи данных на гиперкубе, например, пропорциональна величине ); - рассылка номера выбранной вершины для включения в охватывающее дерево всем процессорам (для гиперкуба сложность этой операции также определяется величиной ). Получение МОД обеспечивается при выполнении итераций алгоритма Прима; как результат, общая трудоемкость метода определяется соотношением . С учетом данной оценки показатели эффективности параллельного алгоритма имеют вид: , . Анализ выражений показывает, что достижение асимптотически ненулевого значения показателя становится возможным при количестве процессоров, пропорциональном величине .
Популярное: Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (333)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |