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

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

Самый быстрый известный алгоритм 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. Хотя это время исполнения близко к линейному, оно не является линейным в случае очень разреженных графов.

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

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

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

1. Хорошо известное свойство циклов для минимальных остовных деревьев заключается в том, что самое тяжелое ребро любого цикла входного графа G не может входить в состав минимального остовного дерева.

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). Пусть H = (v, EH) создан из исходного графа с взвешенными ребрами G = (V, E) посредством включения каждого ребра с вероятностью p, не зависящей от других ребер. Пусть F – минимальный остовный лес H. Тогда ожидаемое количество F-легких дуг в G составляет < n/p.

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

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

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

• После создания в 1995 году алгоритма KKT были разработаны два новых детерминированных алгоритма для нахождения минимального остовного дерева, предложенные Шазелем [4] и Петти-Рамачандраном [ ]. Первый [4] исполняется за время O(n + ma(m, n)), где a – обратная функция Аккермана, которая растет даже медленнее, чем функция f$, ранее упоминавшаяся в качестве наилучшего результата, известного до публикации алгоритма KKT [ ]. Второй алгоритм [ ] доказуемо исполняется за время, не более чем на константный множитель отличающееся от сложности дерева решений задачи минимального остовного дерева и, следовательно, являющееся оптимальным; его временные границы составляют O(n + ma(m, n)) и Q(n + m), точные границы еще не определены.

 

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

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

 

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

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

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

 

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