Тема: Оценка производительности алгоритмов поиска минимального остовного дерева

Минимальным остовным деревом (MST) связного взвешенного графа называется его связный подграф, состоящий из всех вершин исходного графа и некоторых его ребер, причем сумма весов ребер минимально возможная. Нахождение такого дерева встречается в многих прикладных задачах и решение этой задачи позволяет минимизировать затраты на связь компонент принятых за вершины графа.
Примером такой задачи может являться поиск способа соединения городов дорогами так чтобы их общая длинна или стоимость была минимальной. Также задача поиска минимального островного дерева возникает в компьютерных сетях, а именно в протоколе STP, который устраняет петли в сети выбирая при этом лучшие по скорости соединения.
Актуальность данной работы заключается в том, что появляются новые области, где возникает задача поиска MST и сложно определить по получившемуся графу какой алгоритм решит эту задачу оптимально.
Объектом исследования процесс выбора оптимального алгоритма поиска минимального остовного дерева для графа определенного вида.
Предметом исследования являются различные алгоритмы поиска минимального остовного дерева и их модификации.
Цель работы: оценка производительности на различных графах однопоточных и многопоточные алгоритмы поиска минимального остовного дерева.
Для достижения поставленной цели необходимо решить следующие задачи:
• проанализировать однопоточные алгоритмы поиска MST;
• реализовать однопоточные алгоритмы MST;
• разработать генераторы тестовых графов;
• составить тесты;
• протестировать однопоточные алгоритмы MST;
• проанализировать многопоточные алгоритмы MST;
• реализовать многопоточные алгоритмы MST;
• протестировать многопоточные алгоритмы MST;
• провести анализ полученных на этапе тестирования данных.
Работа состоит из введения, трех глав, заключения и списка литературы. Введение отражает основные характеристики работы определяет тему работы и ее актуальность, описывает объект и предмет исследования, цели и задачи, которые необходимо рассмотреть в настоящем документе.
В первой главе рассмотрена задача поиска минимального остовного дерева и алгоритмы решения этой задачи.
Во второй главе произведен анализ параллельных алгоритмов поиска минимального остовного дерева, а также их реализация.
В третьей главе произведено тестирование и анализ полученных результатов.
Купить

В выпускной квалификационной работе произведен анализ основных алгоритмов поиска минимального остовного дерева.
Были проанализированы такие алгоритмы как алгоритм Крускала, алгоритм Прима и алгоритм Борувки. Разработаны их параллельные модели. Реализована тестирующая система для генерации графов, тестирования алгоритмов и сбора результатов. Проанализированы полученные результаты.
Каждый алгоритм имеет свои особенности и по-разному ведет себя на различных графах. Так было выяснено, что алгоритм Крускала по сравнению с другими алгоритмами потребляет наименьшее число оперативной памяти и показывает на разряженных графах лучший результат. Асимптотика работы алгоритма значительно зависит от используемой сортировки. Однако его параллельная версия обладает небольшим ускорением.
Алгоритм Прима отлично подходит для полных графов и выбирать его следует если граф хранится в виде списка смежности или матрицы смежности. Минусом алгоритма является высокое потребление памяти и отсутствием ускорением при использовании параллельных вычислений.
Алгоритм Борувки показывает хорошие результаты на более плотных графах и не высокое потребление памяти. Идеальным графом для алгоритма Борувки является граф-звезда. Также алгоритм Борувки обладает хорошим ускорением при использовании параллельных вычислений.
Полученные данные в результате выполнения выпускной квалификационной работы могут быть использованы для определения лучшего алгоритма для конкретной практической задачи.
Купить