1294
правки
Минимальное остовное дерево: различия между версиями
Перейти к навигации
Перейти к поиску
Минимальное остовное дерево (посмотреть исходный код)
Версия от 10:44, 14 ноября 2018
, 14 ноября 2018нет описания правки
Irina (обсуждение | вклад) м (→См. также) |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача нахождения минимального остовного дерева (MST) заключается в следующем: имеется связный взвешенный неориентированный граф G = (V, E, w), необходимо найти дерево с минимальным общим весом, содержащее все вершины из V. Здесь <math>w: \mathbb{E} \Rightarrow \mathbb{R} \;</math> – весовая функция. Задачу часто формулируют в геометрических терминах, где V – множество точек в d-мерном пространстве, а w соответствует евклидову расстоянию. Основное различие между двумя подходами заключается в виде входных данных. В графовой формулировке входной граф имеет размер O(m + n) и состоит из перечисления n = |V| вершин и m = |E| ребер, а также весов ребер. В геометрической формулировке на входе имеется перечисление координат каждой точки (пространство O(dn)): все <math>\left ( \frac{V}{2} \right ) \;</math> ребер представлены неявно, веса неявно приписаны к координатам точек. В [ | Задача нахождения минимального остовного дерева (MST) заключается в следующем: имеется связный взвешенный неориентированный граф G = (V, E, w), необходимо найти дерево с минимальным общим весом, содержащее все вершины из V. Здесь <math>w: \mathbb{E} \Rightarrow \mathbb{R} \;</math> – весовая функция. Задачу часто формулируют в геометрических терминах, где V – множество точек в d-мерном пространстве, а w соответствует евклидову расстоянию. Основное различие между двумя подходами заключается в виде входных данных. В графовой формулировке входной граф имеет размер O(m + n) и состоит из перечисления n = |V| вершин и m = |E| ребер, а также весов ребер. В геометрической формулировке на входе имеется перечисление координат каждой точки (пространство O(dn)): все <math>\left ( \frac{V}{2} \right ) \;</math> ребер представлены неявно, веса неявно приписаны к координатам точек. В [15] обсуждается задача нахождения минимального евклидова остовного дерева. | ||
== История вопроса == | == История вопроса == | ||
Задача MST обычно рассматривается [7, | Задача MST обычно рассматривается [7, 11] как одна из первых комбинаторных задач, исследовавшихся с алгоритмической точки зрения. Формальное определение было дано Борувкой в 1926 году [1] (еще до возникновения теории вычислимости, комбинаторной оптимизации и в немалой степени – теории графов), и с тех пор этот базовый алгоритм широко использовался. Задача MST способствовала исследованиям в таких сферах, как оптимизация матроидов [3], и разработке эффективных структур данных – таких как очереди с приоритетами (или кучи) и структуры непересекающихся множеств [2, 18]. | ||
== Родственные задачи == | == Родственные задачи == | ||
| Строка 14: | Строка 14: | ||
[[Разрез]] представляет собой разбиение (V', V") вершин графа V. Ребро (u, v) пересекает разрез (V, V"), если <math>u \in V' \;</math> и <math>v \in V'' \;</math>. Последовательность <math>(v_0, v_1,..., v_{k-1}, v_0) \;</math> является [[цикл|циклом]], если <math>(v_i, v_{i+1(mod k)}) \in E \;</math> для <math>0 \le i < k \;</math> . | [[Разрез]] представляет собой разбиение (V', V") вершин графа V. Ребро (u, v) пересекает разрез (V, V"), если <math>u \in V' \;</math> и <math>v \in V'' \;</math>. Последовательность <math>(v_0, v_1,..., v_{k-1}, v_0) \;</math> является [[цикл|циклом]], если <math>(v_i, v_{i+1(mod k)}) \in E \;</math> для <math>0 \le i < k \;</math> . | ||
Корректность всех алгоритмов нахождения MST устанавливается при помощи двух свойств, [[свойство разрезов|разрезов]] и [[свойство циклов|циклов]], также известных как [[синее правило|синее]] и [[красное правило|красное]] правила [ | Корректность всех алгоритмов нахождения MST устанавливается при помощи двух свойств, [[свойство разрезов|разрезов]] и [[свойство циклов|циклов]], также известных как [[синее правило|синее]] и [[красное правило|красное]] правила [17]. | ||
| Строка 36: | Строка 36: | ||
== Основные результаты == | == Основные результаты == | ||
Основным результатом [ | Основным результатом [13] является явный MST-алгоритм, '''доказуемо''' оптимальный, несмотря на то, что его асимптотическое время исполнения в настоящее время неизвестно. | ||
'''Теорема 1. Существует явный детерминированный алгоритм нахождения минимального остовного дерева с временем исполнения порядка <math>D_{MST}(m, n) \;</math>, где m – количество ребер, n – количество вершин, а <math>D_{MST}(m, n) \;</math> – максимальная глубина оптимального дерева решений для любого графа с n вершинами и m ребрами.''' | '''Теорема 1. Существует явный детерминированный алгоритм нахождения минимального остовного дерева с временем исполнения порядка <math>D_{MST}(m, n) \;</math>, где m – количество ребер, n – количество вершин, а <math>D_{MST}(m, n) \;</math> – максимальная глубина оптимального дерева решений для любого графа с n вершинами и m ребрами.''' | ||
Из этого следует, что алгоритм Петти-Рамачандрана [ | Из этого следует, что алгоритм Петти-Рамачандрана [13] является асимптотически не худшим, чем ''любой'' MST-алгоритм, выводящий решение при помощи сравнения весов ребер. Лучшая известная верхняя граница <math>D_{MST}(m, n) \;</math>, а именно <math>O(m \alpha(m, n)) \;</math>, была получена Шазелем [2]. Она тривиально составляет <math>\Omega(m) \;</math>. | ||
Вкратце опишем принцип работы алгоритма Петти-Рамачандрана. Экземпляр (m, n) представляет собой граф с m ребрами и n вершинами. Доказательство теоремы 1 выполняется при помощи процедуры [[декомпозиция|декомпозиции]] с линейным временем исполнения, разбивающей любой экземпляр (m, n) задачи MST на экземпляры размеров <math>(m^*, n^*), (m_1, n_1), ..., (m_s, n_s) \;</math>, где <math>m = m^* + \sum_i m_i \;</math>, <math>n = \sum_i n_i \;</math>, <math>n^* \le n / log \; log \; log \; n</math> и каждый <math>n_i \le log \; log \; log \; n</math>. Экземпляр (m*,n*) может быть обработан за время O(m + n) при помощи существующих MST-алгоритмов [2]. Для обработки других экземпляров алгоритм Петти-Рамачандрана выполняет поиск перебором для нахождения дерева решений минимальной глубины для '''каждого''' графа, число вершин которого не превышает log log log n. После нахождения этих деревьев решений оставшиеся экземпляры можно обработать за время <math>O(\sum_i D_{MST}(m_i, n_i)) = O(D_{MST}(m, n)) \;</math>. В силу ограниченного размера этих экземпляров <math>(n_i \le log \; log \; log \; n) \;</math> время работы алгоритма поиска перебором незначительно – o(n). Процедура декомпозиции использует понятие мягкой кучи, введенное Шазелем [2] (приближенной очереди с приоритетами), и расширение свойства сжимаемости. | Вкратце опишем принцип работы алгоритма Петти-Рамачандрана. Экземпляр (m, n) представляет собой граф с m ребрами и n вершинами. Доказательство теоремы 1 выполняется при помощи процедуры [[декомпозиция|декомпозиции]] с линейным временем исполнения, разбивающей любой экземпляр (m, n) задачи MST на экземпляры размеров <math>(m^*, n^*), (m_1, n_1), ..., (m_s, n_s) \;</math>, где <math>m = m^* + \sum_i m_i \;</math>, <math>n = \sum_i n_i \;</math>, <math>n^* \le n / log \; log \; log \; n</math> и каждый <math>n_i \le log \; log \; log \; n</math>. Экземпляр (m*,n*) может быть обработан за время O(m + n) при помощи существующих MST-алгоритмов [2]. Для обработки других экземпляров алгоритм Петти-Рамачандрана выполняет поиск перебором для нахождения дерева решений минимальной глубины для '''каждого''' графа, число вершин которого не превышает log log log n. После нахождения этих деревьев решений оставшиеся экземпляры можно обработать за время <math>O(\sum_i D_{MST}(m_i, n_i)) = O(D_{MST}(m, n)) \;</math>. В силу ограниченного размера этих экземпляров <math>(n_i \le log \; log \; log \; n) \;</math> время работы алгоритма поиска перебором незначительно – o(n). Процедура декомпозиции использует понятие мягкой кучи, введенное Шазелем [2] (приближенной очереди с приоритетами), и расширение свойства сжимаемости. | ||
| Строка 49: | Строка 49: | ||
Второй результат исследований [ | Второй результат исследований [13] заключается в том, что время исполнения оптимального алгоритма фактически является линейным для графов почти любой топологии, с любыми перестановками весов ребер. | ||
| Строка 64: | Строка 64: | ||
== Применение == | == Применение == | ||
Борувка [1] сформулировал задачу MST в процессе решения практической проблемы электрификации сельской местности Моравии (ныне Чешская Республика) при помощи кратчайшей сети линий электропередач. MST часто используются в качестве отправной точки для эвристических аппроксимаций оптимальных алгоритмов решения задачи коммивояжера и создания дерева Штейнера, а также в других задачах построения сетей. Кроме того, MST являются компонентами других алгоритмов оптимизации графов, в частности, алгоритмов нахождения кратчайшего пути с единственным источником, предложенных Торупом [ | Борувка [1] сформулировал задачу MST в процессе решения практической проблемы электрификации сельской местности Моравии (ныне Чешская Республика) при помощи кратчайшей сети линий электропередач. MST часто используются в качестве отправной точки для эвристических аппроксимаций оптимальных алгоритмов решения задачи коммивояжера и создания дерева Штейнера, а также в других задачах построения сетей. Кроме того, MST являются компонентами других алгоритмов оптимизации графов, в частности, алгоритмов нахождения кратчайшего пути с единственным источником, предложенных Торупом [18] и Петти-Рамачандраном [14]. Также MST используются как инструмент визуализации данных, предположительно имеющих древовидную структуру; например, если матрица содержит данные о расхождениях для множества видов животных, минимальное остовное дерево соответствующего графа будет предположительно группировать близкородственные виды вместе (см. [7]). Среди других современных вариантов применения MST – моделирование физических систем [16] и сегментация изображений [8]. В [4] вы найдете много других вариантов использования алгоритма. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
| Строка 70: | Строка 70: | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Морет и Шапиро [ | Морет и Шапиро [10] оценили эффективность жадных MST-алгоритмов, используя разные очереди с приоритетами. Они обнаружили, что лучшим является алгоритм Ярника [7] (также его авторами считаются Прим и Дейкстра, см. [3, 7, 11]) в варианте реализации с кучей для пар [12]. Катриэль, Сандерс и Трафф [9] разработали и реализовали нежадный рандомизированный MST-алгоритм на базе алгоритма Карджера и коллег [8]. Они пришли к выводу, что на относительно плотных графах он работает значительно быстрее жадных алгоритмов, протестированных Моретом и Шапиро. | ||
== См. также == | == См. также == | ||
| Строка 76: | Строка 76: | ||
== Литература == | == Литература == | ||
1. Boruvka, O.: O jistem problemu | 1. Boruvka, O.: O jistem problemu minimalnim. Prace Moravske Pfirodovedecke Spolecnosti 3, 37-58 (1926). In Czech | ||
2. Chazelle, B.: A minimum spanning tree algorithm with inverse-Ackermann type complexity. J. ACM 47(6), 1028-1047 (2000) Cormen, TH., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001) | 2. Chazelle, B.: A minimum spanning tree algorithm with inverse-Ackermann type complexity. J. ACM 47(6), 1028-1047 (2000) Cormen, TH., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001) | ||
| Строка 92: | Строка 92: | ||
8. Karger, D.R., Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm for finding minimum spanning trees. J. ACM 42, 321-329(1995) | 8. Karger, D.R., Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm for finding minimum spanning trees. J. ACM 42, 321-329(1995) | ||
9. | 9. Katriel, I., Sanders, P., Traff, J.L.: A practical minimum spanning tree algorithm using the cycle property. In: Proc. 11th Annual European Symposium on Algorithms. LNCS, vol. 2832, pp. 679- 690. Springer, Berlin (2003) | ||
10. | 10. Moret, B.M.E., Shapiro, H.D.: An empirical assessment of algorithms for constructing a minimum spanning tree. In: DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 15, Am. Math. Soc., Providence, RI (1994) | ||
11. | 11. Pettie, S.: On the shortest path and minimum spanning tree problems. Ph.D. thesis, The University of Texas, Austin, August 2003 | ||
12. Pettie, S.: | 12. Pettie, S.: Towards a final analysis of pairing heaps. In: Proc. 46th Annual Symposium on Foundations of Computer Science (FOCS), 2005, pp. 174-183 | ||
13. Pettie, S.: | 13. Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. J. ACM 49( 1), 16-34 (2002) | ||
14. Pettie, S., Ramachandran, V.: | 14. Pettie, S., Ramachandran, V.: A shortest path algorithm for real-weighted undirected graphs. SIAM J. Comput. 34(6), 1398-1431 (2005) | ||
15. | 15. Preparata, F.P., Shamos, M.I.: Computational geometry. Springer, New York (1985) | ||
16. | 16. Subramaniam, S., Pope, S.B.: A mixing model for turbulent reactive flows based on euclidean minimum spanning trees. Combust. Flame 115(4),487-514 (1998) | ||
17. | 17. Tarjan, R.E.: Data structures and network algorithms. In: CBMS-NSF Reg. Conf. Ser. Appl. Math., vol. 44. SIAM, Philadelphia (1983) | ||
18 | 18. Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. J. ACM 46(3), 362-394 (1999) | ||