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