Поиск минимального оставного дерева (Машеров) (547752)
Текст из файла
Национальный исследовательский институт
Московский Энергетический Институт (Технический Университет)
Институт автоматики и вычислительной техники
Кафедра Прикладной математики
Лабораторная работа №2
по дисциплине «Параллельные системы и параллельное программирование»
тема: «Поиск минимального оставного дерева.»
Выполнил:
Машеров Д.Е.
Проверил:
Панков Н.А.
Москва
2012 г.
Постановка задачи
Дана граф, требуется найти минимальное оставное дерева этого графа.
Охватывающим деревом (или остовом ) неориентированного графа G называется подграф T графа G, который является деревом и содержит все вершины из G. Определив вес подграфа для взвешенного графа как сумму весов входящих в подграф дуг, под минимально охватывающим деревом (МОД) T понимается охватывающее дерево минимального веса.
Последовательный алгоритм.
Используется алгоритм Прима.
Алгоритм начинает работу с произвольной вершины графа, выбираемой в качестве корня дерева, и в ходе последовательно выполняемых итераций расширяет конструируемое дерево до МОД. Пусть 
есть множество вершин, уже включенных алгоритмом в МОД, а величины 
, 1<=
<=n, характеризуют дуги минимальной длины от вершин, еще не включенных в дерево, до множества , т.е.
(если для какой-либо вершины не существует ни одной дуги в , значение устанавливается равным ). В начале работы алгоритма выбирается корневая вершина МОД s и полагается ={s}, 
=0.
Действия, выполняемые на каждой итерации алгоритма Прима, состоят в следующем:
-
определяются значения величин di для всех вершин, еще не включенных в состав МОД;
-
выбирается вершина t графа G, имеющая дугу минимального веса до множества ;
-
вершина t включается в VT.
После выполнения n-1 итерации метода МОД будет сформировано. Вес этого дерева может быть получен при помощи выражения
Параллельный алгоритм.
Итерации метода должны выполняться последовательно и, тем самым, не могут быть распараллелены. С другой стороны, выполняемые на каждой итерации алгоритма действия являются независимыми и могут реализовываться одновременно.
Распределение данных между процессорами вычислительной системы должно обеспечивать независимость перечисленных операций алгоритма Прима. Это может быть реализовано, если каждая вершина графа располагается на процессоре вместе со всей связанной с вершиной информацией.
-
набор вершин
-
соответствующий этому набору блок из k величин
-
вертикальную полосу матрицы смежности графа G из k соседних столбцов
,
есть s-ый стольбец матрицы А
-
общую часть набора Vj и формируемого в процессе вычислений множества вершин
![]()
.
Результаты вычислительного эксперимента
-
Количество вершин графа: 1 000
| Число исполнителей | Время решения | Ускорение |
| 1 | 5,547534 | |
| 2 | 2,791276 | 1,91 |
| 3 | 1,88332 | 2,98 |
| 4 | 1,433112 | 4,02 |
| 8 | 0,774494 | 8,03 |
| 12 | 0,556577 | 11,28 |
| 16 | 0,418985 | 13,79 |
| 20 | 0,367053 | 15,22 |
| 24 | 0,326834 | 16,40 |
| 28 | 0,299249 | 17,41 |
| 32 | 0,266754 | 18,56 |
| 36 | 0,277727 | 11,41 |
| 40 | 0,346345 | 14,27 |
| 44 | 0,323366 | 12,07 |
| 48 | 0,296411 | 13,43 |
| 52 | 0,295205 | 11,27 |
| 56 | 0,31282 | 8,62 |
| 60 | 0,285301 | 7,52 |
| 64 | 0,242074 | 17,69 |
-
Количество вершин графа: 5 000
| Число исполнителей | Время решения | Ускорение |
| 1 | 902,03109 | |
| 2 | 342,68127 | 2,63 |
| 3 | 232,899105 | 3,93 |
| 4 | 175,10955 | 5,14 |
| 8 | 90,308224 | 10,24 |
| 12 | 47,578303 | 15,07 |
| 16 | 39,038579 | 19,43 |
| 20 | 32,30373 | 23,46 |
| 24 | 27,843325 | 27,85 |
| 28 | 25,298673 | 31,91 |
| 32 | 22,473695 | 36,01 |
| 36 | 20,695048 | 39,49 |
| 40 | 18,728376 | 43,14 |
| 44 | 17,164971 | 46,54 |
| 48 | 16,130638 | 49,27 |
| 52 | 15,016155 | 51,99 |
| 56 | 13,954162 | 55,59 |
| 60 | 13,285935 | 57,88 |
| 64 | 10,253616 | 61,45 |
-
Количество вершин графа: 10 000
| Число исполнителей | Время решения |
| 2 | 2774,1043 |
| 3 | 1882,915374 |
| 4 | 1416,6679 |
| 8 | 713,6579 |
| 12 | 482,27567 |
| 16 | 368,15783 |
| 20 | 294,24421 |
| 24 | 250,46335 |
| 28 | 214,14437 |
| 32 | 188,42947 |
| 36 | 171,45674 |
| 40 | 152,31577 |
| 44 | 140,24903 |
| 48 | 129,80971 |
| 52 | 120,93132 |
| 56 | 112,64522 |
| 60 | 105,99757 |
| 64 | 100,04801 |
-
Количество вершин графа: 20 000
| Число исполнителей | Время решения |
| 8 | 5698,3759 |
| 12 | 3838,5841 |
| 16 | 2909,7297 |
| 20 | 2333,4545 |
| 24 | 1962,7721 |
| 28 | 1698,1574 |
| 32 | 1486,6888 |
| 36 | 1347,5227 |
| 40 | 1206,1265 |
| 44 | 1101,3858 |
| 48 | 1021,4873 |
| 52 | 942,69882 |
| 56 | 888,52427 |
| 60 | 829,63986 |
| 64 | 771,18603 |
-
Количество вершин графа: 30 000
| Число исполнителей | Время решения |
| 24 | 6444,4012 |
| 28 | 5578,5286 |
| 32 | 4897,1726 |
| 36 | 4381,5045 |
| 40 | 3946,59 |
| 44 | 3647,9182 |
| 48 | 3344,2485 |
| 52 | 3089,6803 |
| 56 | 2862,2789 |
| 60 | 2680,8999 |
| 64 | 2549,2176 |
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
