Anton121 Test Buttons: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Anton121 (обсуждение | вклад) |
Anton121 (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
| + | == Постановка задачи == | ||
| + | |||
| + | Пусть задан связный неориентированный граф <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). | ||
| + | |||
| + | == Варианты задачи == | ||
| + | |||
| + | Если исходный граф <math>G</math> несвязный, то набор минимальных остовных деревьев для всех компонент связности называется ''минимальным остовным лесом'' (Minimum | ||
| + | Spanning Forest, MSF). | ||
| + | |||
| + | Для графа с целочисленными весами возможно использование специальных приёмов, таких как [[wikipedia:ru:Поразрядная сортировка|поразрядная сортировка]], что приводит к | ||
| + | алгоритмам, решающим задачу за линейное время. | ||
| + | |||
| + | В распределённой задаче может присутствовать дополнительное требование, что обмен данными происходит только вдоль рёбер графа. | ||
| + | |||
| + | == Свойства задачи == | ||
| + | |||
| + | '''Веса'''. Решение задачи зависит не от значений весов, а от их порядка. Таким образом, вместо задания весов можно задать порядок – предикат «меньше или равно» на множестве пар рёбер графа. По этой причине можно без ограничения общности считать, что все веса рёбер различны – для этого следует упорядочить рёбра вначале по весу, а затем по номеру. Кроме того, к исходным весам можно применить любую возрастающую функцию и это не приведёт к изменению решения. Как следствие, можно считать, что все веса находятся в заданном интервале, например, <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>. Это свойство может использоваться для более быстрого завершения работы алгоритмов, если число компонент связности известно заранее. | ||
| + | |||
| + | == Описание входных и выходных данных == | ||
| + | |||
| + | '''Входные данные''': взвешенный граф <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>. | ||
| + | |||
| + | == Алгоритмы решения задачи == | ||
| + | |||
| + | Существует три классических подхода к решению задачи: | ||
| + | * [[Алгоритм Борувки]];<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> – число вершин.) | ||
| + | |||
| + | Все другие алгоритмы, как правило, являются вариацией на тему одного из трёх перечисленных, или их комбинацией. | ||
| + | * '''Алгоритм 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>. (Существование детерминированного алгоритма с линейной оценкой сложности является открытым вопросом.) | ||
| + | |||
| + | Следует отметить, что алгоритмы, имеющие асимптотическую сложность лучшую, чем <math>O(m \ln n)</math>, как правило, на практике работают медленнее классических алгоритмов: константа в оценке настолько велика, что выигрыш от лучшей асимптотике будет заметен только на графах очень больших размеров. | ||
| + | |||
| + | == Ресурс параллелизма == | ||
| + | |||
| + | # Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов. | ||
| + | # Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными. | ||
| + | # Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента. | ||
| + | |||
| + | == Ссылки == | ||
| + | |||
| + | <references /> | ||
== '''<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 Ресурс параллелизма
- Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
- Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
- Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.
7 Ссылки
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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" (Просто показано их разное "оформление")
