Аннотация 2
ВВЕДЕНИЕ 6
1 ПОСТАНОВКА И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ ПОИСКА МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА 8
1.1 Постановка задачи поиска минимального остовного дерева 8
1.2 Построение минимального остовного дерева в общем виде 9
1.3 Исследование алгоритмов поиска минимального остовного дерева 11
1.3.1 Исследование алгоритма Крускала и построение его модели 11
1.3.2 Исследование алгоритма Прима и построение его модели 15
1.3.3 Исследование алгоритма Борувки и построение его модели 18
2 ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ПОИСКА МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА 23
2.1 Подход применяемый к организации параллельных вычислений 23
2.2 Оценка возможности организовать параллельные вычисления в алгоритме Крускала 23
2.3 Особенности реализации алгоритма Крускала 25
2.4 Оценка возможности организовать параллельные вычисления в алгоритме Прима 26
2.5 Оценка возможности организовать параллельные вычисления в алгоритме Борувки 27
3 АНАЛИЗ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ ПОИСКА МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА 30
3.1 Графы для тестирования алгоритмов 30
3.2 Анализ последовательных алгоритмов поиска минимального остовного дерева 33
3.2.1 Сравнения последовательных алгоритмов поиска MST на графе цепочка 33
3.2.2 Сравнения последовательных алгоритмов поиска MST на полном графе 35
3.2.3 Сравнения последовательных алгоритмов поиска MST на разреженном графе 37
3.2.4 Сравнения последовательных алгоритмов поиска MST на графе-звезда 39
3.3 Анализ параллельных алгоритмов поиска минимального остовного дерева 40
3.3.1 Параметры оценки параллельных алгоритмов поиска MST 40
3.3.2 Оценка параллельного алгоритма Крускала 41
3.3.3 Оценка параллельного алгоритма Борувки 42
3.3.4 Оценка параллельного алгоритма Прима 44
3.4 Сравнение параллельных алгоритмов поиска MST 45
ЗАКЛЮЧЕНИЕ 46
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 47
Минимальным остовным деревом (MST) связного взвешенного графа называется его связный подграф, состоящий из всех вершин исходного графа и некоторых его ребер, причем сумма весов ребер минимально возможная. Нахождение такого дерева встречается в многих прикладных задачах и решение этой задачи позволяет минимизировать затраты на связь компонент принятых за вершины графа.
Примером такой задачи может являться поиск способа соединения городов дорогами так чтобы их общая длинна или стоимость была минимальной. Также задача поиска минимального островного дерева возникает в компьютерных сетях, а именно в протоколе STP, который устраняет петли в сети выбирая при этом лучшие по скорости соединения.
Актуальность данной работы заключается в том, что появляются новые области, где возникает задача поиска MST и сложно определить по получившемуся графу какой алгоритм решит эту задачу оптимально.
Объектом исследования процесс выбора оптимального алгоритма поиска минимального остовного дерева для графа определенного вида.
Предметом исследования являются различные алгоритмы поиска минимального остовного дерева и их модификации.
Цель работы: оценка производительности на различных графах однопоточных и многопоточные алгоритмы поиска минимального остовного дерева.
Для достижения поставленной цели необходимо решить следующие задачи:
• проанализировать однопоточные алгоритмы поиска MST;
• реализовать однопоточные алгоритмы MST;
• разработать генераторы тестовых графов;
• составить тесты;
• протестировать однопоточные алгоритмы MST;
• проанализировать многопоточные алгоритмы MST;
• реализовать многопоточные алгоритмы MST;
• протестировать многопоточные алгоритмы MST;
• провести анализ полученных на этапе тестирования данных.
Работа состоит из введения, трех глав, заключения и списка литературы. Введение отражает основные характеристики работы определяет тему работы и ее актуальность, описывает объект и предмет исследования, цели и задачи, которые необходимо рассмотреть в настоящем документе.
В первой главе рассмотрена задача поиска минимального остовного дерева и алгоритмы решения этой задачи.
Во второй главе произведен анализ параллельных алгоритмов поиска минимального остовного дерева, а также их реализация.
В третьей главе произведено тестирование и анализ полученных результатов.
В выпускной квалификационной работе произведен анализ основных алгоритмов поиска минимального остовного дерева.
Были проанализированы такие алгоритмы как алгоритм Крускала, алгоритм Прима и алгоритм Борувки. Разработаны их параллельные модели. Реализована тестирующая система для генерации графов, тестирования алгоритмов и сбора результатов. Проанализированы полученные результаты.
Каждый алгоритм имеет свои особенности и по-разному ведет себя на различных графах. Так было выяснено, что алгоритм Крускала по сравнению с другими алгоритмами потребляет наименьшее число оперативной памяти и показывает на разряженных графах лучший результат. Асимптотика работы алгоритма значительно зависит от используемой сортировки. Однако его параллельная версия обладает небольшим ускорением.
Алгоритм Прима отлично подходит для полных графов и выбирать его следует если граф хранится в виде списка смежности или матрицы смежности. Минусом алгоритма является высокое потребление памяти и отсутствием ускорением при использовании параллельных вычислений.
Алгоритм Борувки показывает хорошие результаты на более плотных графах и не высокое потребление памяти. Идеальным графом для алгоритма Борувки является граф-звезда. Также алгоритм Борувки обладает хорошим ускорением при использовании параллельных вычислений.
Полученные данные в результате выполнения выпускной квалификационной работы могут быть использованы для определения лучшего алгоритма для конкретной практической задачи.
