Anton121 Test Buttons: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
 
Строка 1: Строка 1:
−
{{algorithm
+
== Постановка задачи ==
−
| name              = Алгоритм поиска в ширину (BFS)
 
−
| serial_complexity = <math>O(|V| + |E|)</math>
 
−
| pf_height        = <math>N/A, \max O(|V|) </math>
 
−
| pf_width          = <math>N/A, \max O(|E|) </math>
 
−
| input_data        = <math>O(|V| + |E|)</math>
 
−
| output_data      = <math>O(|V|)</math>
 
−
}}
 
  
−
Основные авторы описания: [[Участник:Elijah|И.В.Афанасьев]]
+
Пусть задан связный неориентированный граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math>. Подграф, являющийся деревом и проходящий через все вершины
 +
<math>G</math>, называется ''основным деревом''. Остовное дерево называется ''минимальным'', если суммарный вес его рёбер является минимальным среди всех остовных
 +
деревьев.
  
−
== Свойства и структура алгоритма ==
+
Постановка задачи и алгоритм её решения были впервые опубликованы в работе Отакара Борувки<ref name=boruvka>Borůvka, Otakar. “O Jistém Problému Minimálním.” Práce Moravské Přírodovědecké Společnosti Alexander Daryin, no. 3 (1926): 37–58.</ref>. Английское название задачи – Minimum Spanning Tree (MST).
  
−
=== Общее описание алгоритма ===
+
== Варианты задачи ==
  
−
'''Поиск в ширину''' (англ. Breadth-First Search, BFS) позволяет вычислить кратчайшие расстояния (в терминах количества рёбер) от выделенной вершины ориентированного графа до всех остальных вершин, и/или построить корневое направленное дерево, расстояния в котором совпадают с расстояниями в исходном графе. Кроме того, поиск в ширину позволяет решать задачу проверки достижимости (существуют ли пути между вершиной источником и остальными вершинами графа). Впервые алгоритм поиска в ширину описан в работах Мура<ref>Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.</ref> и Ли<ref>Lee, C Y. “An Algorithm for Path Connections and Its Applications.” IEEE Transactions on Electronic Computers 10, no. 3 (September 1961): 346–65. doi:10.1109/TEC.1961.5219222.</ref>.
+
Если исходный граф <math>G</math> несвязный, то набор минимальных остовных деревьев для всех компонент связности называется ''минимальным остовным лесом'' (Minimum
 +
Spanning Forest, MSF).
  
−
Алгоритм основан на обходе вершин графа "по слоям". На каждом шаге есть множество "передовых" вершин, для смежных к которым производится проверка, относятся ли они к еще не посещенным. Все еще не посещенные вершины добавляются в новое множество "передовых" вершин, обрабатываемых на следующем шаге. Изначально в множество "передовых" вершин входит только вершина-источник, от которой и начинается обход.
+
Для графа с целочисленными весами возможно использование специальных приёмов, таких как [[wikipedia:ru:Поразрядная сортировка|поразрядная сортировка]], что приводит к
 +
алгоритмам, решающим задачу за линейное время.
  
−
В последовательном случае алгоритм имеет алгоритмическую сложность <math>O(|V| + |E|)</math>, где <math>|V|</math> - число вершин в графе, <math>|E|</math> - число ребер в графе.
+
В распределённой задаче может присутствовать дополнительное требование, что обмен данными происходит только вдоль рёбер графа.
  
−
=== Математическое описание алгоритма ===
+
== Свойства задачи ==
  
−
Пусть задан граф <math>G = (V, E)</math> без весов, и с выделенной вершиной-источником <math>u</math>. Путем <math>P(u,v)</math> между вершинами <math>u</math> и <math>v</math> называется множество ребер <math>(u, v_1), (v_1, v_2), ... (v_{n-1}, v)</math>. Длиной пути <math>d(u,v)</math> обозначим число ребер в данном пути между вершинами <math>u</math> и <math>v</math>. Поиск в ширину находит кратчайшие пути <math>d(u,v)</math> от вершины <math>u</math> до всех остальных вершин графа описанным далее образом.
+
'''Веса'''. Решение задачи зависит не от значений весов, а от их порядка. Таким образом, вместо задания весов можно задать порядок – предикат «меньше или равно» на множестве пар рёбер графа. По этой причине можно без ограничения общности считать, что все веса рёбер различны – для этого следует упорядочить рёбра вначале по весу, а затем по номеру. Кроме того, к исходным весам можно применить любую возрастающую функцию и это не приведёт к изменению решения. Как следствие, можно считать, что все веса находятся в заданном интервале, например, <math>[0, 1]</math>.
  
−
В начале работы алгоритма расстояние до вершины-источника <math>d(u)=0</math>, до остальных вершин <math>d(v) = \infty, \forall v \neq u </math>. Также в начале работы алгоритма инициализируется множество <math>F = \{u\}</math>.
+
'''Существование и единственность'''. Минимальный опорный лес всегда существует, а если все веса рёбер различны, то он единственный. Как уже отмечалось, всегда можно сделать веса рёбер различными. Если условие различных весов не выполняется, легко построить пример, в котором будет существовать более одного минимального остовного дерева.
  
−
Далее на каждом шаге алгоритма строится множество вершин <math>P = {w} </math>, таких, что для <math>\forall v \in F \exists (v, w) \in E | d(w) = \infty </math>, при этом обновляются расстояния <math>d(w)=d(v)+1</math> для <math>\forall w \in P </math>. Затем производится переход на следующий шаг до тех пор, пока <math>P \neq \emptyset</math>; при этом в начале каждого шага множество F заменяется на P.
+
'''Схлопывание фрагментов'''. Пусть <math>F</math> – фрагмент минимального остовного дерева графа <math>G</math>, а граф <math>G'</math> получен из <math>G</math> склеиванием вершин, принадлежащих
 +
<math>F</math>. Тогда объединение <math>F</math> и минимального остовного дерева графа <math>G'</math> даёт минимальное остовное дерево исходного графа <math>G</math>.
  
−
=== Вычислительное ядро алгоритма ===
+
'''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны [[алгоритм Борувки]] и [[алгоритм Прима]].
  
−
Вычислительным ядром алгоритма является обход вершин, смежных с выбранной вершиной <math>v</math>, с последующим добавлением еще не посещенных вершин в множество <math>P</math>. Данная операция выполняется на каждом шаге для каждой вершины <math>v \in F</math>.
+
'''Минимальное ребро графа'''. Если <math>e^*</math> – единственное ребро графа с минимальным весом, то оно принадлежит минимальному остовному дереву. На этом свойстве основан [[алгоритм Крускала]].
  
−
=== Макроструктура алгоритма ===
+
'''Ассоциативность по рёбрам'''. Пусть <math>MSF(E)</math> – минимальный остовный лес графа с рёбрами <math>E</math>. Тогда
  
−
Алгоритм последовательно уточняет значения функции <math>d(v)</math>.
+
:<math>
 +
        MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)).
 +
</math>
  
−
Структуру можно описать следующим образом:
+
'''Количество рёбер''' остовного леса для графа с <math>n</math> вершинами и <math>c</math> компонентами связности равно <math>n-c</math>. Это свойство может использоваться для более быстрого завершения работы алгоритмов, если число компонент связности известно заранее.
  
−
1. Инициализация: всем вершинам присваивается предполагаемое расстояние <math>d(v)=\infty</math>, кроме вершины-источника, для которой <math>d(u)=0</math> .
+
== Описание входных и выходных данных ==
  
−
2. Помещение вершины источника <math>v</math> в множество "передовых" вершин <math>F</math>.
+
'''Входные данные''': взвешенный граф <math>(V, E, W)</math> (<math>n</math> вершин <math>v_i</math> и <math>m</math> рёбер <math>e_j = (v^{(1)}_{j},
 +
v^{(2)}_{j})</math> с весами <math>f_j</math>).
  
−
3.    Обход вершин множества <math>F</math>.  
+
'''Объём входных данных''': <math>O(m + n)</math>.
  
−
а) Инициализация множества <math>P=\emptyset</math>.
+
'''Выходные данные''': список рёбер минимального остовного дерева (для несвязного графа – список минимальных остовных деревьев для всех компонент связности).
  
−
б) Для каждой вершины <math>v \in F</math> обход всех вершин <math>w | \exists (v, w)</math> (смежных с ней), c помещением в множество <math>P</math> таких вершин <math>w |    d(w)=\infty</math>.
+
'''Объём выходных данных''': <math>O(n)</math>.
  
−
в) Замена множества <math>F</math> на <math>P</math> и переход на шаг 3 в случае, если множество <math>F \neq \emptyset</math>.
+
== Алгоритмы решения задачи ==
  
−
=== Схема реализации последовательного алгоритма ===
+
Существует три классических подхода к решению задачи:
 +
* [[Алгоритм Борувки]];<ref name=boruvka />
 +
* [[Алгоритм Крускала]];<ref>Kruskal, Joseph B. “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.” Proceedings of the American Mathematical Society 7, no. 1 (1956): 48–48. doi:10.1090/S0002-9939-1956-0078686-7.</ref>
 +
* [[Алгоритм Прима]].<ref>Jarník, Vojtěch. “O Jistém Problému Minimálním (Z Dopisu Panu O. Borůvkovi).” Práce Moravské Přírodovědecké Společnosti 6, no. 4 (1930): 57–63.</ref><ref>Prim, R C. “Shortest Connection Networks and Some Generalizations.” Bell System Technical Journal 36, no. 6 (November 1957): 1389–1401. doi:10.1002/j.1538-7305.1957.tb01515.x.</ref>
 +
Во всех случаях последовательная сложность алгоритма <math>O(m \ln n)</math> при использовании обычных структур данных. (Обозначения: <math>m</math> – число рёбер, <math>n</math> – число вершин.)
  
−
Простейшая версия алгоритма поиск в ширину может быть реализована при помощи очередей на языке C++ следующим образом.
+
Все другие алгоритмы, как правило, являются вариацией на тему одного из трёх перечисленных, или их комбинацией.
−
Код приведен в предположении, что граф хранится в формате сжатого списка смежности: для каждой вершины в массиве vertices_to_edges_ptrs хранятся индекс начала и индекс конца списка смежных с ней вершин из массива dst_ids.
+
* '''Алгоритм GHS''' (Gallager, Humblet, Spira)<ref>Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.</ref> и его последующие версии<ref>Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.</ref><ref>Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.</ref> являются распределённым вариантом алгоритма Борувки. Это алгоритм обычно используется для автоматического распределённого построения остовного дерева сетью коммутаторов.
 +
* '''Алгоритм Габова''' и др.<ref>Gabow, Harold N, Zvi Galil, Thomas H Spencer, and Robert Endre Tarjan. “Efficient Algorithms for Finding Minimum Spanning Trees in Undirected and Directed Graphs.” Combinatorica 6, no. 2 (June 1986): 109–22. doi:10.1007/BF02579168.</ref> использует [[wikipedia:ru:Фибоначчиева куча|фибоначчиеву кучу]] для упорядочения рёбер в алгоритме Борувки. Сложность <math>O(m \ln \beta (m, n))</math>.
 +
* '''Алгоритм Фредмана и Уилларда'''<ref>Fredman, Michael L, and Dan E Willard. “Trans-Dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths.” Journal of Computer and System Sciences 48, no. 3 (June 1994): 533–51. doi:10.1016/S0022-0000(05)80064-9.</ref> предназначен для графов с целочисленными весами и имеет линейную оценку сложности <math>O(m)</math>. Используется алгоритм Прима в сочетании со специально разработанным алгоритмом кучи ([[wikipedia:AF-heap|AF-heap]]).
 +
* '''Алгоритм Каргера''' и др.<ref>Karger, David R, Philip N Klein, and Robert Endre Tarjan. “A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees.” Journal of the ACM 42, no. 2 (March 1, 1995): 321–28. doi:10.1145/201019.201022.</ref> решает задачу ''в среднем'' за линейное время <math>O(m)</math>. (Существование детерминированного алгоритма с линейной оценкой сложности является открытым вопросом.)
  
−
<source lang="C++">
+
Следует отметить, что алгоритмы, имеющие асимптотическую сложность лучшую, чем <math>O(m \ln n)</math>, как правило, на практике работают медленнее классических алгоритмов: константа в оценке настолько велика, что выигрыш от лучшей асимптотике будет заметен только на графах очень больших размеров.
  
−
// init distances
+
== Ресурс параллелизма ==
−
for(int i = 0; i < vertices_count; i++)
 
−
    _result[i] = MAX_INT;
 
−
   
 
−
// init queue and first vertex
 
−
std::queue<int> vertex_queue;
 
−
vertex_queue.push(_source_vertex);
 
−
_result[_source_vertex] = 1;
 
−
   
 
−
// do bfs
 
−
while(vertex_queue.size() > 0)
 
−
{
 
−
    int cur_vertex = vertex_queue.front();
 
−
    vertex_queue.pop();
 
−
       
 
−
    long long first = vertices_to_edges_ptrs[cur_vertex];
 
−
    long long last = vertices_to_edges_ptrs[cur_vertex + 1];
 
−
    for(long long i = first; i < last; i++)
 
−
    {
 
−
        int dst_id = dst_ids[i];
 
−
        if(_result[dst_id] == MAX_INT)
 
−
        {
 
−
            _result[dst_id] = _result[src_id] + 1;
 
−
            vertex_queue.push(dst_id);
 
−
        }
 
−
    }
 
−
}
 
  
−
</source>
+
# Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
 +
# Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
 +
# Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.
  
−
=== Последовательная сложность алгоритма ===
+
== Ссылки ==
−
 
 
−
Алгоритм имеет последовательную сложность <math>O(|V| + |E|)</math>, где <math>|V|</math> и <math>|E|</math> - число вершин и ребер графа соответственно: алгоритм инициализирует начальный массив расстояний - <math>O(|V|)</math> операций, а затем обходит каждую вершину один единственный раз -  <math>O(|E|)</math> операций. Данная оценка верна в случае, если формат хранения графа позволяет обходить вершины, смежные к выбранной (к примеру форматы списка смежности, сжатого списка смежности). При использовании других форматов оценка сложности может быть большей.
 
−
 
 
−
=== Информационный граф ===
 
−
 
 
−
Информационный граф классического алгоритма поиска в ширину приведен на рисунке 1.
 
−
 
 
−
[[Файл:Classical_BFS_ig.png|thumb|center|500px|Рисунок 1. Информационный граф алгоритма BFS.]]
 
−
 
 
−
На рисунке 1 используются следующие обозначения:
 
−
 
 
−
[1] - добавление вершины-источника <math>u</math> к множеству <math>F</math>.
 
−
 
 
−
[2] - извлечение добавленной вершины <math>v</math> из множества <math>F</math>.
 
−
 
 
−
[3] - проверка расстояний до вершин, смежных с вершиной <math>v</math>.
 
−
 
 
−
[4] - добавление еще не посещенных вершин в множество <math>P</math>.
 
−
 
 
−
[5] - замена множества <math>F</math> на  <math>P</math> и проверка его пустоты. В случае непустого множества - переход на следующую итерацию, иначе завершение работы алгоритма.
 
−
 
 
−
Данный алгоритм имеет один важный недостаток при реализации: операция [4] требует бесконфликтной возможности добавления элементов в множество P, что, на практике, всегда будет сводиться к сериализации обращений к структуре данных, моделирующей данное множество.
 
−
 
 
−
В результате часто используется модификация алгоритма (далее алгоритм-2), использующая набор независимых структур данных для каждого из параллельных процессов. Информационный граф данного подхода приведен на рисунке 2.
 
−
 
 
−
[[Файл:BFS_ig_parallel_queues.png|thumb|center|500px|Рисунок 2. Информационный граф алгоритма BFS (независимые структуры данных).]]
 
−
 
 
−
Обозначения для рисунка 2:
 
−
 
 
−
[1] - добавление вершины-источника в множество <math>F</math>.
 
−
 
 
−
[2] - разделение данных множества <math>F</math> между процессами
 
−
 
 
−
[3] - помещение в множества <math>F_i</math> соответствующих данных из <math>F</math> каждым процессом с номером i.
 
−
 
 
−
[4] - извлечение очередной вершины из множеств <math>F_i</math>, обход её соседей и добавление их в множество <math>P_i</math> в случае, если они еще не посещены
 
−
 
 
−
[5] - попарное слияние множеств <math>P_i</math> для различных процессов, итоговое преобразование их в множество <math>F</math>.
 
−
 
 
−
[6] - проверка условия выхода из цикла
 
−
 
 
−
Кроме того, в случае, если реализация структур данных, моделирующих множества <math>F</math> и <math>P</math>, невозможна, может использоваться квадратичный по сложности алгоритм, схожий с алгоритм Беллмана-Форда. Основная идея заключается в том, что на каждом шаге производится обход всех ребер графа с обновлением текущего массива дистанций. Информационный граф данной модификации алгоритма приведен на рисунке 3.
 
−
 
 
−
[[Файл:quadratic_BFS_ig.png|thumb|center|500px|Рисунок 3. Информационный граф алгоритма BFS (квадратичный подход к распараллеливанию).]]
 
−
 
 
−
Обозначения для рисунка 3:
 
−
 
 
−
[1] - инициализация расстояний до вершины-источника
 
−
 
 
−
[2] - инициализация расстояний до остальных вершин графа
 
−
 
 
−
[3] - загрузка информации об очередном ребре и обновление дистанций до соответствующих вершин.
 
−
 
 
−
[4] - проверка условия выхода из цикла
 
−
 
 
−
=== Ресурс параллелизма алгоритма ===
 
−
 
 
−
В ходе работы классический вариант алгоритма обходит граф по слоям. В каждый слой добавляются еще не посещенные вершины, достижимые из вершин предыдущего слоя. Обход вершин каждого слоя, как и их соседей, может производиться параллельно. Точно оценить число вершин в каждом слое невозможно в силу того, что их количество зависит от структуры связанности входного графа. Аналогично невозможно оценить число шагов алгоритма, за которое будут найдены все кратчайшие пути.
 
−
 
 
−
Произведем оценку ширины ярусно-параллельной формы алгоритма через максимальное число вершин p в слое среди всех шагов алгоритма. Тогда число параллельных операций на данном слое будет равно сумме числа смежных вершин для каждой вершины слоя: <math>\sum_{n=1}^{p} degree(v_i)</math>, при этом для каждого слоя данное значение будет различным. Высота ярусно-параллельной формы будет равна числу шагов в алгоритме и может быть оценена только сверху (не более <math>|V|</math>).
 
−
 
 
−
При квадратичном подходе к параллельной реализации алгоритма на каждом шаге выполняется <math>O(|E|)</math> операций, которые могут быть выполнены параллельно; таким образом, ширина ЯПФ данной модификации алгоритма равна <math>O(|E|)</math>. Число шагов алгоритма, как и в классическом случае, зависит от структуры графа и может быть оценено сверху как <math>O(|V|)</math>.
 
−
 
 
−
=== Входные и выходные данные алгоритма ===
 
−
'''Входные данные''': граф <math>G(V, E)</math>, <math>|V|</math> вершин <math>v_i</math> и <math>|E|</math> рёбер <math>e_j = (v^{(1)}_{j}, v^{(2)}_{j})</math>, вершина-источник <math>u</math>.
 
−
 
 
−
'''Объём входных данных''': <math>O(|V| + |E|)</math>.
 
−
 
 
−
'''Выходные данные''' (возможные варианты):
 
−
# для каждой вершины <math>v</math> исходного графа расстояние <math>d(v)</math>, определенное как число ребер, лежащих на кратчайшем пути от вершины <math>u</math> к <math>v</math>.
 
−
# для каждой вершины <math>v</math> исходного графа значение достижимости (достижима или нет) от вершины-источника <math>u</math>.
 
−
 
−
'''Объём выходных данных''': <math>O(|V|)</math>.
 
−
 
 
−
=== Свойства алгоритма ===
 
−
 
 
−
== Программная реализация алгоритма ==
 
−
=== Особенности реализации последовательного алгоритма ===
 
−
=== Локальность данных и вычислений ===
 
−
==== Локальность реализации алгоритма ====
 
−
===== Структура обращений в память и качественная оценка локальности =====
 
−
===== Количественная оценка локальности =====
 
−
=== Возможные способы и особенности параллельной реализации алгоритма ===
 
−
=== Масштабируемость алгоритма и его реализации ===
 
−
==== Масштабируемость алгоритма ====
 
−
==== Масштабируемость реализации алгоритма ====
 
−
=== Динамические характеристики и эффективность реализации алгоритма ===
 
−
=== Выводы для классов архитектур ===
 
−
=== Существующие реализации алгоритма ===
 
−
 
 
−
* Распределённый алгоритм поиска вширь является вычислительным ядром бенчмарка [http://www.graph500.org Graph500].
 
−
** MPI: {{Buttonlinkimp|12}}
 
−
* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функции <code>[http://www.boost.org/libs/graph/doc/breadth_first_search.html breadth_first_search]</code>, <code>[http://www.boost.org/libs/graph/doc/breadth_first_visit.html breadth_first_visit]</code>).
 
−
* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/breadth_first_search.html breadth_first_search]</code>).{{Buttonlinkimp|11}}
 
−
* Java: [http://webgraph.di.unimi.it WebGraph] (класс <code>[http://webgraph.di.unimi.it/docs/it/unimi/dsi/webgraph/algo/ParallelBreadthFirstVisit.html ParallelBreadthFirstVisit]</code>), многопоточная реализация.
 
−
* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.traversal.breadth_first_search.bfs_edges.html bfs_edges]</code>).
 
−
* Python/C++: [https://networkit.iti.kit.edu NetworKit] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/graph.html#networkit.graph.BFS networkit.graph.BFS]</code>).
 
−
* RCC for CPU {{Buttonlinkimp|9}}
 
−
* RCC for GPU {{Buttonlinkimp|26}}
 
−
* Gap {{Buttonlinkimp|36}}
 
−
* Litra {{Buttonlinkimp|39}}
 
−
== Литература ==
 
  
 
<references />
 
<references />
−
 
−
[[Категория:Статьи в работе]]
 
−
 
−
[[En:Breadth-first search (BFS)]]
 
 
== '''<u>LinkButtons</u>''' ==
 
== '''<u>LinkButtons</u>''' ==
  

Текущая версия на 17:52, 7 ноября 2021

1 Постановка задачи

Пусть задан связный неориентированный граф [math]G = (V, E)[/math] с весами рёбер [math]f(e)[/math]. Подграф, являющийся деревом и проходящий через все вершины [math]G[/math], называется основным деревом. Остовное дерево называется минимальным, если суммарный вес его рёбер является минимальным среди всех остовных деревьев.

Постановка задачи и алгоритм её решения были впервые опубликованы в работе Отакара Борувки[1]. Английское название задачи – Minimum Spanning Tree (MST).

2 Варианты задачи

Если исходный граф [math]G[/math] несвязный, то набор минимальных остовных деревьев для всех компонент связности называется минимальным остовным лесом (Minimum Spanning Forest, MSF).

Для графа с целочисленными весами возможно использование специальных приёмов, таких как поразрядная сортировка, что приводит к алгоритмам, решающим задачу за линейное время.

В распределённой задаче может присутствовать дополнительное требование, что обмен данными происходит только вдоль рёбер графа.

3 Свойства задачи

Веса. Решение задачи зависит не от значений весов, а от их порядка. Таким образом, вместо задания весов можно задать порядок – предикат «меньше или равно» на множестве пар рёбер графа. По этой причине можно без ограничения общности считать, что все веса рёбер различны – для этого следует упорядочить рёбра вначале по весу, а затем по номеру. Кроме того, к исходным весам можно применить любую возрастающую функцию и это не приведёт к изменению решения. Как следствие, можно считать, что все веса находятся в заданном интервале, например, [math][0, 1][/math].

Существование и единственность. Минимальный опорный лес всегда существует, а если все веса рёбер различны, то он единственный. Как уже отмечалось, всегда можно сделать веса рёбер различными. Если условие различных весов не выполняется, легко построить пример, в котором будет существовать более одного минимального остовного дерева.

Схлопывание фрагментов. Пусть [math]F[/math] – фрагмент минимального остовного дерева графа [math]G[/math], а граф [math]G'[/math] получен из [math]G[/math] склеиванием вершин, принадлежащих [math]F[/math]. Тогда объединение [math]F[/math] и минимального остовного дерева графа [math]G'[/math] даёт минимальное остовное дерево исходного графа [math]G[/math].

Минимальное ребро фрагмента. Пусть [math]F[/math] – фрагмент минимального остовного дерева и [math]e_F[/math] – ребро наименьшего веса, исходящее из [math]F[/math] (т.е. ровно один его конец является вершиной из [math]F[/math]). Если ребро [math]e_F[/math] единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны алгоритм Борувки и алгоритм Прима.

Минимальное ребро графа. Если [math]e^*[/math] – единственное ребро графа с минимальным весом, то оно принадлежит минимальному остовному дереву. На этом свойстве основан алгоритм Крускала.

Ассоциативность по рёбрам. Пусть [math]MSF(E)[/math] – минимальный остовный лес графа с рёбрами [math]E[/math]. Тогда

[math] MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)). [/math]

Количество рёбер остовного леса для графа с [math]n[/math] вершинами и [math]c[/math] компонентами связности равно [math]n-c[/math]. Это свойство может использоваться для более быстрого завершения работы алгоритмов, если число компонент связности известно заранее.

4 Описание входных и выходных данных

Входные данные: взвешенный граф [math](V, E, W)[/math] ([math]n[/math] вершин [math]v_i[/math] и [math]m[/math] рёбер [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math] с весами [math]f_j[/math]).

Объём входных данных: [math]O(m + n)[/math].

Выходные данные: список рёбер минимального остовного дерева (для несвязного графа – список минимальных остовных деревьев для всех компонент связности).

Объём выходных данных: [math]O(n)[/math].

5 Алгоритмы решения задачи

Существует три классических подхода к решению задачи:

Во всех случаях последовательная сложность алгоритма [math]O(m \ln n)[/math] при использовании обычных структур данных. (Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин.)

Все другие алгоритмы, как правило, являются вариацией на тему одного из трёх перечисленных, или их комбинацией.

  • Алгоритм GHS (Gallager, Humblet, Spira)[5] и его последующие версии[6][7] являются распределённым вариантом алгоритма Борувки. Это алгоритм обычно используется для автоматического распределённого построения остовного дерева сетью коммутаторов.
  • Алгоритм Габова и др.[8] использует фибоначчиеву кучу для упорядочения рёбер в алгоритме Борувки. Сложность [math]O(m \ln \beta (m, n))[/math].
  • Алгоритм Фредмана и Уилларда[9] предназначен для графов с целочисленными весами и имеет линейную оценку сложности [math]O(m)[/math]. Используется алгоритм Прима в сочетании со специально разработанным алгоритмом кучи (AF-heap).
  • Алгоритм Каргера и др.[10] решает задачу в среднем за линейное время [math]O(m)[/math]. (Существование детерминированного алгоритма с линейной оценкой сложности является открытым вопросом.)

Следует отметить, что алгоритмы, имеющие асимптотическую сложность лучшую, чем [math]O(m \ln n)[/math], как правило, на практике работают медленнее классических алгоритмов: константа в оценке настолько велика, что выигрыш от лучшей асимптотике будет заметен только на графах очень больших размеров.

6 Ресурс параллелизма

  1. Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
  2. Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
  3. Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.

7 Ссылки

  1. ↑ 1,0 1,1 Borůvka, Otakar. “O Jistém Problému Minimálním.” Práce Moravské Přírodovědecké Společnosti Alexander Daryin, no. 3 (1926): 37–58.
  2. ↑ Kruskal, Joseph B. “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.” Proceedings of the American Mathematical Society 7, no. 1 (1956): 48–48. doi:10.1090/S0002-9939-1956-0078686-7.
  3. ↑ Jarník, Vojtěch. “O Jistém Problému Minimálním (Z Dopisu Panu O. Borůvkovi).” Práce Moravské Přírodovědecké Společnosti 6, no. 4 (1930): 57–63.
  4. ↑ Prim, R C. “Shortest Connection Networks and Some Generalizations.” Bell System Technical Journal 36, no. 6 (November 1957): 1389–1401. doi:10.1002/j.1538-7305.1957.tb01515.x.
  5. ↑ Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.
  6. ↑ Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.
  7. ↑ Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.
  8. ↑ Gabow, Harold N, Zvi Galil, Thomas H Spencer, and Robert Endre Tarjan. “Efficient Algorithms for Finding Minimum Spanning Trees in Undirected and Directed Graphs.” Combinatorica 6, no. 2 (June 1986): 109–22. doi:10.1007/BF02579168.
  9. ↑ Fredman, Michael L, and Dan E Willard. “Trans-Dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths.” Journal of Computer and System Sciences 48, no. 3 (June 1994): 533–51. doi:10.1016/S0022-0000(05)80064-9.
  10. ↑ Karger, David R, Philip N Klein, and Robert Endre Tarjan. “A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees.” Journal of the ACM 42, no. 2 (March 1, 1995): 321–28. doi:10.1145/201019.201022.

8 LinkButtons

Все кнопки ниже ведут на "yandex.ru" (Просто показано их разное "оформление")
Yandex Yandex Yandex Yandex Yandex Yandex

Yandex Yandex

Источник — https://algowiki-project.org/w/ru/index.php?title=Anton121_Test_Buttons&oldid=28671