4551
правка
Рандомизированный алгоритм нахождения минимального остовного дерева: различия между версиями
Материал из WEGA
Рандомизированный алгоритм нахождения минимального остовного дерева (посмотреть исходный код)
Версия от 23:38, 16 апреля 2016
, 16 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
== Основные результаты == | == Основные результаты == | ||
Основным результатом работы [9] является рандомизированный алгоритм нахождения минимального остовного дерева за ожидаемое линейное время. С весами ребер не выполняется никаких других действий, кроме попарных сравнений. Алгоритм не предполагает какого-либо конкретного представления весов ребер (т.е. должны ли их значения быть целыми или вещественными), он только считает, что любое сравнение весов для пары ребер может быть выполнено за единичное время. В статье также показано, что время исполнения алгоритма составляет O(m + n) с экспоненциально высокой вероятностью 1 | Основным результатом работы [9] является рандомизированный алгоритм нахождения минимального остовного дерева за ожидаемое линейное время. С весами ребер не выполняется никаких других действий, кроме попарных сравнений. Алгоритм не предполагает какого-либо конкретного представления весов ребер (т.е. должны ли их значения быть целыми или вещественными), он только считает, что любое сравнение весов для пары ребер может быть выполнено за единичное время. В статье также показано, что время исполнения алгоритма составляет O(m + n) с экспоненциально высокой вероятностью <math>1 - exp( - \Omega (m)) \;</math>, а время исполнения в наихудшем случае составит O(n + m log n). | ||
Простая и элегантная лемма выборки для задачи MST, сформулированная в данном случае в виде Леммы 1, явилась основным инструментом вывода и анализа алгоритма для задачи KKT. Перед тем, как сформулировать лемму, напомним пару необходимых определений и фактов: | Простая и элегантная [[лемма выборки]] для задачи MST, сформулированная в данном случае в виде Леммы 1, явилась основным инструментом вывода и анализа алгоритма для задачи KKT. Перед тем, как сформулировать лемму, напомним пару необходимых определений и фактов: | ||
1. Хорошо известное свойство циклов для минимальных остовных деревьев заключается в том, что самое тяжелое ребро любого цикла входного графа G не может входить в состав минимального остовного дерева. | 1. Хорошо известное [[свойство циклов]] для минимальных остовных деревьев заключается в том, что самое тяжелое ребро любого цикла входного графа G ''не может'' входить в состав минимального остовного дерева. | ||
2. Пусть F – лес графа G (т.е. ациклический подграф G). Ребро e | 2. Пусть F – лес графа G (т.е. ациклический подграф G). Ребро <math>e \in E \;</math> называется F-легким, если имеет место один из двух случаев: (1) <math>F \cup \{ e \} \;</math> продолжает оставаться лесом графа G; (2) самое тяжелое ребро цикла, содержащего e, не совпадает с e. Ребро G, не являющееся F-легким, называется F-тяжелым. Отметим, что согласно свойству циклов F-тяжелое ребро не может входить в состав минимального остовного дерева G н''езависимо от того, какой лес F используется''. Пусть имеется лес F графа G. Множество F-тяжелых ребер может быть вычислено за линейное время при помощи простой модификации существующих алгоритмов верификации минимального остовного дерева [6, 12]. | ||
Лемма 1 (лемма выборки для задачи MST). Пусть H = (v, | '''Лемма 1 (лемма выборки для задачи MST)'''. Пусть <math>H = (v, E_H) \;</math> создан из исходного графа с взвешенными ребрами G = (V, E) посредством включения каждого ребра с вероятностью p, не зависящей от других ребер. Пусть F – минимальный остовный лес H. Тогда ожидаемое количество F-легких дуг в G не превышает n/p. | ||
Алгоритм KKT определяет ребра минимального остовного дерева G, используя только шаги Борувки. После каждых двух шагов Борувки он выполняет удаление F-тяжелых ребер, используя минимальный остовный лес F подграфа, полученный посредством выборки ребер с вероятностью p = 1/2. Как упоминалось ранее, эти F-тяжелые ребра могут быть обнаружены за линейное время. Минимальный остовный лес графа-выборки вычисляется рекурсивным образом. | Алгоритм KKT определяет ребра минимального остовного дерева G, используя только шаги Борувки. После каждых двух шагов Борувки он выполняет удаление F-тяжелых ребер, используя минимальный остовный лес F подграфа, полученный посредством выборки ребер с вероятностью p = 1/2. Как упоминалось ранее, эти F-тяжелые ребра могут быть обнаружены за линейное время. Минимальный остовный лес графа-выборки вычисляется рекурсивным образом. | ||
| Строка 44: | Строка 44: | ||
Анализ ожидаемого времени исполнения и экспоненциально высокая граница вероятности для времени исполнения простейшим образом выводятся при помощи леммы выборки MST (леммы 1). | Анализ ожидаемого времени исполнения и экспоненциально высокая граница вероятности для времени исполнения простейшим образом выводятся при помощи леммы выборки MST (леммы 1). | ||
В работе [ ] доказываются следующие положения. | В работе [9] доказываются следующие положения. | ||
| Строка 54: | Строка 54: | ||
Лемма 1 была доказана в [ ] при помощи моделирования алгоритма Крускала и анализа вероятности того, что F-легкое ребро не будет выбрано. Еще одно доказательство, использующее обратный анализ, приведено в [ ]. | Лемма 1 была доказана в [ ] при помощи моделирования алгоритма Крускала и анализа вероятности того, что F-легкое ребро не будет выбрано. Еще одно доказательство, использующее обратный анализ, приведено в [ ]. | ||
== Дополнительные соображения == | == Дополнительные соображения == | ||
