Допустим, необходимо проложить кабель по территории университета, связав все его здания, так, чтобы из каждого здания кабель по какому-либо пути доходил до любого другого здания. Кроме того, предположим, что надо минимизировать общую длину прокладываемого кабеля. Если рассматривать здания как вершины, а кабели между зданиями как ребра, то эта работа с прокладыванием кабеля превращается в задачу определения каркаса, охватывающего здания территории университета, в котором общая длина проложенного кабеля должна быть минимальной. Такую задачу называют нахождением каркаса минимального веса.
Определим понятие каркаса более формально. Если дан связный неориентированный граф G=(V, E), то каркас (также называемый остовным или стягивающим деревом) T=(V, E’), где E’E – это связный граф без циклов. Иными словами, каркас неориентированного графа G – это подграф графа G, дерево, содержащее все вершины графа. Понятно, что для того, чтобы T имело тот же набор вершин, что и связный граф G, и чтобы T не имело циклов, оно должно содержать ровно |V|–1 ребро.
Предположим, что для каждого ребра eE существует вес w(e), причем такой вес может выражать, например, цену, длину или время, необходимое для прохода по ребру (в нашем примере – длину кабеля между зданиями). Во взвешенном графе вес подграфа – это сумма весов его ребер. Тогда каркас T минимального веса (или минимальное остовное дерево) – это каркас G, в котором вес дерева минимизирован относительно всех остовных деревьев G (см. рис. 1). Интуитивно определяется, что вес дерева T=(V, E’) равен
???.
Рис. 1. Пример неориентированного графа
и его минимального остовного дерева
Если граф G несвязный, он не может иметь остовного дерева, но у него есть остовный лес. Далее по тексту будем считать, что граф G связный. Если G несвязный, то можно найти компоненты связности (существуют различные алгоритмы нахождения компонентов связности, которые можно реализовать как последовательно, так и параллельно, но это выходит за рамки вопросов, рассматриваемых в данной статье) и применить алгоритм нахождения минимального каркаса для каждого из них. Также можно изменить алгоритм нахождения остовного дерева минимального веса, чтобы на выходе получать минимальный остовный лес.
В целом, существует несколько алгоритмов определения минимального каркаса графа, в частности алгоритм Краскала, Прима и Соллина. Во всех трех этих алгоритмах используется жадный подход к решению задачи, т. е. в любой момент выполнения данных алгоритмов существует множество ребер E’, представляющее подмножество некоторого минимального остовного дерева графа G. На каждом шаге алгоритмов из оставшихся ребер выбирается «лучшее» ребро, обладающее определенными свойствами, и добавляется к формируемому каркасу минимального веса. Одним из важных свойств любого ребра, добавляемого к E’, является его безопасность, т. е. то, что обновленное множество ребер E’ будет продолжать представлять подмножество некоторого минимального остовного дерева.
В этой статье будет проведен сравнительный анализ последовательной (для однопроцессорной машины) и одного из вариантов параллельной (для многопроцессорного компьютера) реализаций алгоритма Прима.
Алгоритм Прима
Итак, рассмотрим алгоритм Прима определения минимального по стоимости остовного леса взвешенного связного неориентированного графа G=(V, E) с функцией веса ребер w. Подход, используемый в этом жадном алгоритме, состоит в непрерывном добавлении ребер к E’ E таким образом, что E’ всегда представляет дерево, являющееся поддеревом некоторого минимального остовного дерева графа G. Первоначально выбирается произвольная вершина r V как корневая вершина дерева, которое будет построено. Это может быть любая вершина исходного графа, поскольку в конечном итоге все вершины должны быть включены в каркас. Далее для инициализации E’ используется ребро (r, u), имеющее минимальный вес среди ребер, инцидентных r. В продолжение алгоритма выбирается ребро минимального веса между какой-либо вершиной текущего дерева, представленного в E’, и некоторой вершиной, не принадлежащей текущему дереву, и это ребро добавляется к E’. Таким образом каркас минимального веса наращивается путем выбора новой вершины и ребра, которые гарантированно попадают в остовное дерево минимального веса.
Приведем последовательную реализацию алгоритма Прима. Для нее необходимы две множественные величины. Первоначальным значением одной из них являются все вершины графа, а второе множество пусто. Если ребро (vi, vj) включается в каркас, то вершины (их номера i и j) добавляются во второе множество. Очевидно, что алгоритм должен выполняться до тех пор, пока не будут выбраны все вершины (пока множества не совпадут).
Пусть G = (V, E, w) – взвешенный неориентированный граф, для которого необходимо найти минимальное остовное дерево, и пусть A – его взвешенная матрица смежностей.
Алгоритм 1. Последовательный алгоритм Прима нахождения минимального остовного дерева
1 procedure PRIM (V, E, w, r)
{V – множество вершин, E – множество ребер,w – веса ребер, r – корень дерева}
2 begin
3 VT:=[r]; {первоначально в VT включена вершина r – корень дерева}
4 d[r]:=0; {вес пути от корня r до вершины r – 0}
5 for <всех вершин v (V-VT)> do
6 if <ребро (r, v) существует> then d[v]:=w(r, v)
7 else d[v]:=
8 while VT<>V dо
9 begin
10 <найти u, d[u]=min{d[v] | v (V-VT)}>
11 VT:=VT+[u];
12 for <всех вершин v (V-VT)> do
13 d[v]=min{d[v], w(u, v)}
14 end;
15 end
В этом алгоритме для хранения вершин каркаса минимального веса во время его построения используется множество VT. Также используется массив d[1..n], в котором для каждой вершины v (V-VT) d[v] содержит минимальный из весов всех ребер, инцидентных вершинам из VT и вершине v. Сначала VT содержит произвольную вершину r, которая становится корнем минимального остовного дерева. Кроме того d[r] = 0 и для всех v (V – VT) d[v] = w(r, v), если такое ребро (r, v) существует; иначе d[v] = . На каждой итерации алгоритма в VT добавляется новая вершина u такая, что d[u] = min{d[v]v (V – VT)}. После добавления этой вершины все значения d[v] для v (V – VT) обновляются, потому что может появиться ребро с меньшим весом между вершиной v и только что добавленной вершиной u. Выполнение алгоритма заканчивается, когда V = VT. На рис. 2 проиллюстрирована работа этого алгоритма. По окончании работы стоимость минимального остовного дерева равна vV d[v]. Добавим также, что данный алгоритм легко модифицировать для хранения ребер, входящих в каркас минимального веса.
В Алгоритме 1 тело цикла while (строки 10–13) выполняется n – 1 раз. Вычисление min{d[v]v (V – VT)} (строка 10) и цикл for (строки 12 и 13) выполняются за (n) шагов. Таким образом, общая сложность данной реализации алгоритма Прима равна (n2).
Далее рассмотрим параллельную реализацию алгоритма Прима. В целом этот алгоритм итерационный. Каждая итерация добавляет одну новую вершину к минимальному остовному дереву. Так как значение d[v] вершины v изменяется каждый раз после добавления вершины u в VT, трудно выбрать более одной вершины для включения в каркас минимального веса. Например, в графе на рис. 2 после выбора вершины b, минимальное остовное дерево не может быть найдено, если вершины d и c уже выбраны. Причина в том, что после выбора вершины d значение d[v] изменилось: было – 5, стало – 2. Итак, нелегко выполнить разные итерации цикла while параллельно.
Рис. 2. Алгоритм Прима нахождения минимального остовного дерева. Корень минимального остовного дерева – вершина b. Выбираемые на каждой итерации вершины из VT и ребра выделены. Кроме того, показано новое значение массива d для вершин из V – VT
Однако каждая итерация может быть распараллелена так, как описано далее. Пусть p – количество процессоров, а n – количество вершин в графе. Разобьем множество V на p подмножеств. В каждом множестве содержится по n / p последовательных вершин; обработка каждого подмножества будет выполняться разными процессорами. Пусть Vi – подмножество вершин, определенное процессору Pi, где i = 0, 1, …, p-1. Каждый процессор Pi хранит часть массива d, которая соответствует Vi (то есть процессор Pi хранит d[v] для v Vi). На рис. 3(а) показано разбиение.
Рис. 3. Разбиение массива расстояний d и матрицы смежности между p процессорами
Каждый процессор Pi вычисляет di[u] = min{d[v]v (V – VT) Vi} за каждую итерацию цикла while. Затем вычисляется общий минимум из всех di[u] (уменьшение типа «все к одному», т. е. из результатов, получившихся на каждом процессоре, вычисляется один итоговый результат) и запоминается в процессоре P0. Процессор P0 сейчас содержит новую вершину u, которая будет вставлена в VТ. Процессор P0 пересылает u всем процессорам (трансляция «один ко всем», т. е. широковещательная передача данных от одного процессора всем). Процессор Pi, ответственный за вершину u, отмечает, что u принадлежит множеству VT. В итоге каждый процессор обновляет значения d[v] для своих локальных вершин.
Когда новая вершина u внесена в VT, значения d[v] для v (V – VT) должны быть обновлены. Процессор, вычисляющий значение для v, должен знать вес ребра (u, v). Поэтому каждому процессору Pi нужно хранить столбцы взвешенной матрицы смежностей, соответствующие множеству Vi вершин, присвоенных ему. Объем памяти для хранения необходимой части матрицы смежностей на каждом процессоре равен (n2 / p). На рис. 3(б) показано разбиение взвешенной матрицы смежностей.
Вычисление, производимое процессором, чтобы минимизировать и обновить значения d[v] на каждой итерации, выполняется за время (n / p). При передаче данных, выполняемой на каждой итерации, происходит уменьшение «все к одному» и трансляция «один ко всем». Для p-процессорного передающего сообщения параллельного компьютера на передачу одного слова требуется время, пропорциональное log p. Для нахождения общего минимума на каждой итерации требуется такое же время. Таким образом, общее время на передачу информации на каждой итерации равно (log p), а время параллельного выполнения программы в такой реализации задается так:
TP=Θ(n2/p) + Θ(n log p).
???
Так как время последовательного выполнения равно (n2), то коэффициенты ускорения и эффективности таковы:
???
Из Равенства 1 мы видим, что для оптимальной по затратам параллельной реализации должно выполняться равенство (p log p) / n = (1). Таким образом, в этой реализации алгоритма Прима нужно использовать только p = (n / log n) процессоров. Кроме того, из Равенства 1, выводится функция изоэффективности передачи данных, она равна (p2 log2 p). Так как n должно расти по крайней мере так же быстро как и p, в этой реализации функция изоэффективности параллелизма равна (p2). Таким образом суммарная изоэффективность этой реализации – (p2 log2 p), что является весьма не плохим результатом.
Итак, мы увидели, что даже те последовательные алгоритмы, которые по сути итерационны, т. е. выполняются пошагово при реализации на однопроцессорном компьютере, могут быть эффективно распараллелены для выполнения на многопроцессорных машинах. В этой статье был рассмотрен один из алгоритмов нахождения минимального остовного дерева – алгоритм Прима. Мы обсудили последовательный и параллельный варианты этого алгоритма и могли увидеть, что второй алгоритм имеет лучшее время выполнения, а именно Θ(n2/p) + Θ(n log p), против времени (n2) последовательной реализации, где n – количество вершин исходного графа, p – число используемых процессоров. В целом, распараллеливание алгоритмов является весьма перспективным направлением современной вычислительной науки в связи с распространением многопроцессорных компьютеров и с тем, что может быть достигнуто гораздо более хорошее время выполнения алгоритмов на таких машинах по сравнению с последовательными вариантами этих же алгоритмов.
Tiger cheap phone cards shop
Хотите узнать, что такое настоящее продвижение сайтов - заходите и читайте!
Интернет бизнес идеи которые способны перевернуть вашу жизнь и сделать ее лучше!
