Аноним

Рандомизированный алгоритм нахождения минимального остовного дерева: различия между версиями

Материал из WEGA
м
нет описания правки
мНет описания правки
 
(не показано 16 промежуточных версий этого же участника)
Строка 9: Строка 9:




Задача MST широко изучалась еще до формулировки задачи KKT; было разработано несколько эффективных детерминированных алгоритмов для ее решения. В основе всех этих детерминированных алгоритмов лежит метод, который жадным образом добавляет ребро к лесу, в любой момент представляющему собой подграф минимального остовного дерева. Ранние алгоритмы этого класса уже были достаточно эффективными: время исполнения составляло O(m log n). Среди них стоит упомянуть алгоритмы Борувки [ ], Ярника [8] (впоследствии переоткрытый Дейкстрой и Примом [ ]) и Крускала [5].
Задача MST широко изучалась еще до формулировки задачи KKT; было разработано несколько эффективных детерминированных алгоритмов для ее решения. В основе всех этих детерминированных алгоритмов лежит метод, который жадным образом добавляет ребро к лесу, в любой момент представляющему собой подграф минимального остовного дерева. Ранние алгоритмы этого класса уже были достаточно эффективными: время выполнения составляло O(m log n). Среди них стоит упомянуть алгоритмы Борувки [1], Ярника [8] (впоследствии переоткрытый Дейкстрой и Примом [5]) и Крускала [5].




Самый быстрый известный алгоритм MST до создания KKT исполнялся за время O(mlog/S(m, n)) [ ], где P(m, n) = minfijlog( и < m/и} [ ]; здесь log(i) n определяется как log n if i = 1 и как loglog^'"1' n if i > 1. Хотя это время исполнения близко к линейному, оно не является линейным в случае очень разреженных графов.
Самый быстрый известный алгоритм MST до создания KKT выполнялся за время <math>O(m \; log \; \beta (m, n))</math> [7], где <math>\beta (m, n) = min \{ i \; | \; log^{(i)} n \le m/n \}</math> [7]; здесь <math>log^{(i)} n \;</math> определяется как <math>log \; n</math>, если i = 1, и <math>log \; log^{(i - 1)} n \;</math>, если i > 1. Хотя это время выполнения близко к линейному, оно не является линейным в случае очень разреженных графов.




Строка 22: Строка 22:
• Основной компонент алгоритма Борувки [1] – «шаг Борувки», который выбирает ребро с минимальным весом, инцидентное каждой вершине, добавляет его к минимальному остовному дереву и затем выполняет сжатие данных ребер. Этот шаг выполняется за линейное время и поддается эффективному распараллеливанию. Он стал основой для самых эффективных параллельных алгоритмов поиска минимального остовного дерева; этот подход также используется алгоритмом KKT.
• Основной компонент алгоритма Борувки [1] – «шаг Борувки», который выбирает ребро с минимальным весом, инцидентное каждой вершине, добавляет его к минимальному остовному дереву и затем выполняет сжатие данных ребер. Этот шаг выполняется за линейное время и поддается эффективному распараллеливанию. Он стал основой для самых эффективных параллельных алгоритмов поиска минимального остовного дерева; этот подход также используется алгоритмом KKT.


• Родственная и более простая задача касается верификации минимального остовного дерева. В этой задаче имеется остовное дерево T для входного графа со взвешенными ребрами и необходимо определить, является ли оно минимальным. Алгоритм, решающий эту задачу при помощи линейного количества сравнений весов ребер, бал предложен Комлошем [ ]; позднее был разработан детерминированный алгоритм с линейным временем исполнения [6] (см. также более простой алгоритм в [12]).
• Родственная и более простая задача касается верификации минимального остовного дерева. В этой задаче имеется остовное дерево T для входного графа со взвешенными ребрами и необходимо определить, является ли оно минимальным. Алгоритм, решающий эту задачу при помощи линейного количества сравнений весов ребер, бал предложен Комлошем [13]; позднее был разработан детерминированный алгоритм с линейным временем выполнения [6] (см. также более простой алгоритм в [12]).


== Основные результаты ==
Основным результатом работы [9] является рандомизированный алгоритм нахождения минимального остовного дерева за ожидаемое линейное время. С весами ребер не выполняется никаких других действий, кроме попарных сравнений. Алгоритм не предполагает какого-либо конкретного представления весов ребер (т.е. должны ли их значения быть целыми или вещественными), он только считает, что любое сравнение весов для пары ребер может быть выполнено за единичное время. В статье также показано, что время выполнения алгоритма составляет O(m + n) с экспоненциально высокой вероятностью <math>1 - exp( - \Omega (m)) \;</math>, а время выполнения в наихудшем случае составит O(n + m log n).


== Основные результаты ==
Основным результатом работы [9] является рандомизированный алгоритм нахождения минимального остовного дерева за ожидаемое линейное время. С весами ребер не выполняется никаких других действий, кроме попарных сравнений. Алгоритм не предполагает какого-либо конкретного представления весов ребер (т.е. должны ли их значения быть целыми или вещественными), он только считает, что любое сравнение весов для пары ребер может быть выполнено за единичное время. В статье также показано, что время исполнения алгоритма составляет O(m + n) с экспоненциально высокой вероятностью 1 — exp{—Q{m)), а время исполнения в наихудшем случае составит O(n + m log n).


Простая и элегантная [[лемма выборки]] для задачи MST, сформулированная в данном случае в виде Леммы 1, явилась основным инструментом вывода и анализа алгоритма для задачи KKT. Перед тем, как сформулировать лемму, напомним пару необходимых определений и фактов:


Простая и элегантная лемма выборки для задачи MST, сформулированная в данном случае в виде Леммы 1, явилась основным инструментом вывода и анализа алгоритма для задачи KKT. Перед тем, как сформулировать лемму, напомним пару необходимых определений и фактов:
1. Хорошо известное [[свойство циклов]] для минимальных остовных деревьев заключается в том, что самое тяжелое ребро любого цикла входного графа G ''не может'' входить в состав минимального остовного дерева.


1. Хорошо известное свойство циклов для минимальных остовных деревьев заключается в том, что самое тяжелое ребро любого цикла входного графа G не может входить в состав минимального остовного дерева.
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].


2. Пусть F – лес графа G (т.е. ациклический подграф G). Ребро e 2 E называется F-легким, если имеет место один из двух случаев: (1) F [ feg продолжает оставаться лесом графа G; (2) самое тяжелое ребро цикла, содержащего e, не совпадает с e. Ребро G, не являющееся F-легким, называется F-тяжелым. Отметим, что согласно свойству циклов F-тяжелое ребро не может входить в состав минимального остовного дерева G независимо от того, какой лес F используется. Пусть имеется лес F графа G. Множество F-тяжелых ребер может быть вычислено за линейное время при помощи простой модификации существующих алгоритмов верификации минимального остовного дерева [6, 12].


'''Лемма 1 (лемма выборки для задачи MST)'''. Пусть <math>H = (v, E_H) \;</math> создан из исходного графа с взвешенными ребрами G = (V, E) посредством включения каждого ребра с вероятностью p, не зависящей от других ребер. Пусть F – минимальный остовный лес H. Тогда ожидаемое количество F-легких дуг в G не превышает n/p.


Лемма 1 (лемма выборки для задачи MST). Пусть H = (v, EH) создан из исходного графа с взвешенными ребрами 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-тяжелые ребра могут быть обнаружены за линейное время. Минимальный остовный лес графа-выборки вычисляется рекурсивным образом.




Корректность алгоритма KKT очевидна, поскольку каждое удаляемое им F-тяжелое ребро не может входить в состав минимального остовного дерева (МОД) графа G, поскольку F – лес G, а каждое ребро, добавляемое им к минимальному остовному дереву, входит в состав МОД, поскольку добавляется при помощи шага Борувки.
Корректность алгоритма KKT очевидна, так как каждое удаляемое им F-тяжелое ребро не может входить в состав минимального остовного дерева (МОД) графа G, поскольку F – лес G, а каждое ребро, добавляемое им к минимальному остовному дереву, входит в состав МОД, поскольку добавляется при помощи шага Борувки.




Анализ ожидаемого времени исполнения и экспоненциально высокая граница вероятности для времени исполнения простейшим образом выводятся при помощи леммы выборки MST (леммы 1).
Анализ ожидаемого времени выполнения и экспоненциально высокая граница вероятности для времени выполнения простейшим образом выводятся при помощи леммы выборки MST (леммы 1).
В работе [ ] доказываются следующие положения.


В работе [9] доказываются следующие положения.


Теорема 2. Алгоритм KKT представляет собой рандомизированный алгоритм, вычисляющий минимальное остовное дерево неориентированного графа с n вершин и m взвешенных ребер за время O(n + m) с вероятностью не менее 1 — exp (— Q{m)). Ожидаемое время исполнения составляет O(n + m), а в наихудшем случае – O(m + n log n).


'''Теорема 2. Алгоритм KKT представляет собой рандомизированный алгоритм, вычисляющий минимальное остовное дерево неориентированного графа с n вершин и m взвешенных ребер за время O(n + m) с вероятностью не менее <math>1 - exp( - \Omega (m)) \;</math>. Ожидаемое время выполнения составляет O(n + m), а в наихудшем случае – O(m + n log n).'''


В качестве модели вычислений в [ ] использовалась RAM-модель с единичной стоимостью, поскольку известные алгоритмы верификации минимального остовного дерева были разработаны именно для этой модели, а не для более ограничивающей модели машины с указателями. Впоследствии было показано, что результат верификации МОД и, следовательно, алгоритм KKT работают также и для машины с указателями [2].


В качестве модели вычислений в [9] использовалась [[RAM]]-модель с единичной стоимостью, поскольку известные алгоритмы верификации минимального остовного дерева были разработаны именно для этой модели, а не для более ограничивающей модели [[машина с указателями|машины с указателями]]. Впоследствии было показано, что результат верификации МОД и, следовательно, алгоритм KKT работают также и для машины с указателями [2].


Лемма 1 была доказана в [ ] при помощи моделирования алгоритма Крускала и анализа вероятности того, что F-легкое ребро не будет выбрано. Еще одно доказательство, использующее обратный анализ, приведено в [ ].


Лемма 1 была доказана в [9] при помощи моделирования алгоритма Крускала и анализа вероятности того, что F-легкое ребро не будет выбрано. Еще одно доказательство, использующее обратный анализ, приведено в [3].


== Дополнительные соображения ==
== Дополнительные соображения ==
• После создания в 1995 году алгоритма KKT были разработаны два новых детерминированных алгоритма для нахождения минимального остовного дерева, предложенные Шазелем [4] и Петти-Рамачандраном [ ]. Первый [4] исполняется за время O(n + ma(m, n)), где a – обратная функция Аккермана, которая растет даже медленнее, чем функция f$, ранее упоминавшаяся в качестве наилучшего результата, известного до публикации алгоритма KKT [ ]. Второй алгоритм [ ] доказуемо исполняется за время, не более чем на константный множитель отличающееся от сложности дерева решений задачи минимального остовного дерева и, следовательно, являющееся оптимальным; его временные границы составляют O(n + ma(m, n)) и Q(n + m), точные границы еще не определены.
• После создания в 1995 году алгоритма KKT были разработаны два новых детерминированных алгоритма для нахождения минимального остовного дерева, предложенные Шазелем [4] и Петти-Рамачандраном [14]. Первый [4] выполняется за время <math>O(n + m \alpha(m, n)) \;</math>, где <math>\alpha \;</math> – обратная функция Аккермана, которая растет даже медленнее, чем функция <math>\beta \;</math>, ранее упоминавшаяся в качестве наилучшего результата, известного до публикации алгоритма KKT [4]. Второй алгоритм [14] доказуемо выполняется за время, не более чем на константный множитель отличающееся от сложности дерева решений задачи минимального остовного дерева и, следовательно, являющееся оптимальным; его временные границы составляют <math>O(n + m \alpha (m, n)) \;</math> и <math>\Omega (n + m) \;</math>, точные границы еще не определены.
 
• Хотя ожидаемое время исполнения алгоритма KKT является линейным (с экспоненциально высокой вероятностью), это не лучший показатель среди рандомизированных MST-алгоритмов. Рандомизированный MST-алгоритм, исполняющийся за ожидаемое линейное время и использующий только O(log* n) случайных бит, приведен в работах [16, 17]. Для сравнения, алгоритм KKT использует линейное количество случайных бит.


• Хотя ожидаемое время выполнения алгоритма KKT является линейным (с экспоненциально высокой вероятностью), это не лучший показатель среди рандомизированных MST-алгоритмов. Рандомизированный MST-алгоритм, выполняющийся за ожидаемое линейное время и использующий только <math>O(log^* \; n)</math> случайных бит, приведен в работах [16, 17]. Для сравнения, алгоритм KKT использует линейное количество случайных бит.


== Применение ==
== Применение ==
Задача нахождения минимального остовного дерева широко применяется на практике; подробнее об этом – в Минимальное остовное дерево|соответствующей статье.
Задача нахождения минимального остовного дерева широко применяется на практике; подробнее об этом – в [[Минимальное остовное дерево|соответствующей статье]].
 


== Открытые вопросы ==
== Открытые вопросы ==
Остаются нерешенными следующие задачи:
Остаются нерешенными следующие задачи:


1. Можно ли устранить рандомизированность из алгоритма KKT? Гибридный алгоритм, использующий KKT внутри модифицированной версии алгоритма Петти-Рамачандрана [14], приведен в работах [16, 17]; он исполняется за ожидаемое линейное время и использует только O(log* n) случайных бит. Можно ли избавиться и от этого небольшого влияния случайности? Если устранить из алгоритма KKT все случайные факторы, это позволит достичь линейной временной границы для алгоритма Петти-Рамачандрана [14] и создать еще один оптимальный детерминированный алгоритм MST – на сей раз на базе KKT.
1. Можно ли устранить рандомизированность из алгоритма KKT? Гибридный алгоритм, использующий KKT внутри модифицированной версии алгоритма Петти-Рамачандрана [14], приведен в работах [16, 17]; он выполняется за ожидаемое линейное время и использует только <math>O(log^* \; n)</math> случайных бит. Можно ли избавиться и от этого небольшого влияния случайности? Если устранить из алгоритма KKT все случайные факторы, это позволит достичь линейной временной границы для алгоритма Петти-Рамачандрана [14] и создать еще один оптимальный детерминированный алгоритм MST – на сей раз на базе KKT.


2. Можно ли устранить рандомизированность из оптимальных с точки зрения операций параллельных алгоритмов [] для MST? Линейный по числу операций параллельный MST-алгоритм с ожидаемым логарифмическим временем исполнения для EREW PRAM приведен в [ ]. Этот алгоритм является оптимальным и с точки зрения операций, и с точки зрения временных затрат. Однако он использует линейное количество случайных бит. В [16, 17] приведен оптимальный с точки зрения операций параллельный алгоритм, исполняющийся за ожидаемое полилогарифмическое время и использующий только полилогарифмическое число случайных бит. В силу этого интересны следующие, пока открытые, вопросы, касающиеся параллельных алгоритмов для задачи MST:
2. Можно ли устранить рандомизированность из оптимальных с точки зрения операций параллельных алгоритмов [10] для MST? Линейный по числу операций параллельный MST-алгоритм с ожидаемым логарифмическим временем выполнения для EREW PRAM приведен в [15]. Этот алгоритм является оптимальным и с точки зрения операций, и с точки зрения временных затрат. Однако он использует линейное количество случайных бит. В [16, 17] приведен оптимальный с точки зрения операций параллельный алгоритм, выполняющийся за ожидаемое полилогарифмическое время и использующий только полилогарифмическое число случайных бит. В силу этого интересны следующие, пока открытые, вопросы, касающиеся параллельных алгоритмов для задачи MST:


• До какой степени может быть снижена зависимость от случайных бит (по сравнению с нынешней линейной границей) в оптимальном с точки зрения времени и операций параллельном алгоритме MST?
• До какой степени может быть снижена зависимость от случайных бит (по сравнению с нынешней линейной границей) в оптимальном с точки зрения времени и операций параллельном алгоритме MST?


• До какой степени может быть снижена зависимость от случайных бит (по сравнению с нынешней полилогарифмической границей) в оптимальном с точки зрения операций параллельном алгоритме с разумной степенью параллелизма (скажем, имеющем полилогарифмическое время параллельного исполнения)?
• До какой степени может быть снижена зависимость от случайных бит (по сравнению с нынешней полилогарифмической границей) в оптимальном с точки зрения операций параллельном алгоритме с разумной степенью параллелизма (скажем, имеющем полилогарифмическое время параллельного выполнения)?
 


== Экспериментальные результаты ==
== Экспериментальные результаты ==
Катриэль, Сандерс и Трафф [ ] выполнили экспериментальную оценку алгоритма KKT и показали, что он демонстрирует высокую эффективность на относительно плотных графах.
Катриэль, Сандерс и Трафф [11] выполнили экспериментальную оценку алгоритма KKT и показали, что он демонстрирует высокую эффективность на относительно плотных графах.
 


== См. также ==
== См. также ==
4511

правок