4511
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
(не показано 16 промежуточных версий этого же участника) | |||
Строка 9: | Строка 9: | ||
Задача MST широко изучалась еще до формулировки задачи KKT; было разработано несколько эффективных детерминированных алгоритмов для ее решения. В основе всех этих детерминированных алгоритмов лежит метод, который жадным образом добавляет ребро к лесу, в любой момент представляющему собой подграф минимального остовного дерева. Ранние алгоритмы этого класса уже были достаточно эффективными: время | Задача MST широко изучалась еще до формулировки задачи KKT; было разработано несколько эффективных детерминированных алгоритмов для ее решения. В основе всех этих детерминированных алгоритмов лежит метод, который жадным образом добавляет ребро к лесу, в любой момент представляющему собой подграф минимального остовного дерева. Ранние алгоритмы этого класса уже были достаточно эффективными: время выполнения составляло O(m log n). Среди них стоит упомянуть алгоритмы Борувки [1], Ярника [8] (впоследствии переоткрытый Дейкстрой и Примом [5]) и Крускала [5]. | ||
Самый быстрый известный алгоритм MST до создания KKT | Самый быстрый известный алгоритм 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 для входного графа со взвешенными ребрами и необходимо определить, является ли оно минимальным. Алгоритм, решающий эту задачу при помощи линейного количества сравнений весов ребер, бал предложен Комлошем [ ]; позднее был разработан детерминированный алгоритм с линейным временем | • Родственная и более простая задача касается верификации минимального остовного дерева. В этой задаче имеется остовное дерево T для входного графа со взвешенными ребрами и необходимо определить, является ли оно минимальным. Алгоритм, решающий эту задачу при помощи линейного количества сравнений весов ребер, бал предложен Комлошем [13]; позднее был разработан детерминированный алгоритм с линейным временем выполнения [6] (см. также более простой алгоритм в [12]). | ||
== Основные результаты == | |||
Основным результатом работы [9] является рандомизированный алгоритм нахождения минимального остовного дерева за ожидаемое линейное время. С весами ребер не выполняется никаких других действий, кроме попарных сравнений. Алгоритм не предполагает какого-либо конкретного представления весов ребер (т.е. должны ли их значения быть целыми или вещественными), он только считает, что любое сравнение весов для пары ребер может быть выполнено за единичное время. В статье также показано, что время выполнения алгоритма составляет O(m + n) с экспоненциально высокой вероятностью <math>1 - exp( - \Omega (m)) \;</math>, а время выполнения в наихудшем случае составит O(n + m log n). | |||
Простая и элегантная [[лемма выборки]] для задачи MST, сформулированная в данном случае в виде Леммы 1, явилась основным инструментом вывода и анализа алгоритма для задачи KKT. Перед тем, как сформулировать лемму, напомним пару необходимых определений и фактов: | |||
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]. | |||
'''Лемма 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-тяжелые ребра могут быть обнаружены за линейное время. Минимальный остовный лес графа-выборки вычисляется рекурсивным образом. | ||
Корректность алгоритма KKT очевидна, | Корректность алгоритма KKT очевидна, так как каждое удаляемое им F-тяжелое ребро не может входить в состав минимального остовного дерева (МОД) графа G, поскольку F – лес G, а каждое ребро, добавляемое им к минимальному остовному дереву, входит в состав МОД, поскольку добавляется при помощи шага Борувки. | ||
Анализ ожидаемого времени | Анализ ожидаемого времени выполнения и экспоненциально высокая граница вероятности для времени выполнения простейшим образом выводятся при помощи леммы выборки MST (леммы 1). | ||
В работе [9] доказываются следующие положения. | |||
'''Теорема 2. Алгоритм KKT представляет собой рандомизированный алгоритм, вычисляющий минимальное остовное дерево неориентированного графа с n вершин и m взвешенных ребер за время O(n + m) с вероятностью не менее <math>1 - exp( - \Omega (m)) \;</math>. Ожидаемое время выполнения составляет O(n + m), а в наихудшем случае – O(m + n log n).''' | |||
В качестве модели вычислений в [9] использовалась [[RAM]]-модель с единичной стоимостью, поскольку известные алгоритмы верификации минимального остовного дерева были разработаны именно для этой модели, а не для более ограничивающей модели [[машина с указателями|машины с указателями]]. Впоследствии было показано, что результат верификации МОД и, следовательно, алгоритм KKT работают также и для машины с указателями [2]. | |||
Лемма 1 была доказана в [9] при помощи моделирования алгоритма Крускала и анализа вероятности того, что F-легкое ребро не будет выбрано. Еще одно доказательство, использующее обратный анализ, приведено в [3]. | |||
== Дополнительные соображения == | == Дополнительные соображения == | ||
• После создания в 1995 году алгоритма KKT были разработаны два новых детерминированных алгоритма для нахождения минимального остовного дерева, предложенные Шазелем [4] и Петти-Рамачандраном [ ]. Первый [4] | • После создания в 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-алгоритм, выполняющийся за ожидаемое линейное время и использующий только <math>O(log^* \; n)</math> случайных бит, приведен в работах [16, 17]. Для сравнения, алгоритм KKT использует линейное количество случайных бит. | |||
== Применение == | == Применение == | ||
Задача нахождения минимального остовного дерева широко применяется на практике; подробнее об этом – в Минимальное остовное дерево|соответствующей статье. | Задача нахождения минимального остовного дерева широко применяется на практике; подробнее об этом – в [[Минимальное остовное дерево|соответствующей статье]]. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Остаются нерешенными следующие задачи: | Остаются нерешенными следующие задачи: | ||
1. Можно ли устранить рандомизированность из алгоритма KKT? Гибридный алгоритм, использующий KKT внутри модифицированной версии алгоритма Петти-Рамачандрана [14], приведен в работах [16, 17]; он | 1. Можно ли устранить рандомизированность из алгоритма KKT? Гибридный алгоритм, использующий KKT внутри модифицированной версии алгоритма Петти-Рамачандрана [14], приведен в работах [16, 17]; он выполняется за ожидаемое линейное время и использует только <math>O(log^* \; n)</math> случайных бит. Можно ли избавиться и от этого небольшого влияния случайности? Если устранить из алгоритма KKT все случайные факторы, это позволит достичь линейной временной границы для алгоритма Петти-Рамачандрана [14] и создать еще один оптимальный детерминированный алгоритм MST – на сей раз на базе KKT. | ||
2. Можно ли устранить рандомизированность из оптимальных с точки зрения операций параллельных алгоритмов [ | 2. Можно ли устранить рандомизированность из оптимальных с точки зрения операций параллельных алгоритмов [10] для MST? Линейный по числу операций параллельный MST-алгоритм с ожидаемым логарифмическим временем выполнения для EREW PRAM приведен в [15]. Этот алгоритм является оптимальным и с точки зрения операций, и с точки зрения временных затрат. Однако он использует линейное количество случайных бит. В [16, 17] приведен оптимальный с точки зрения операций параллельный алгоритм, выполняющийся за ожидаемое полилогарифмическое время и использующий только полилогарифмическое число случайных бит. В силу этого интересны следующие, пока открытые, вопросы, касающиеся параллельных алгоритмов для задачи MST: | ||
• До какой степени может быть снижена зависимость от случайных бит (по сравнению с нынешней линейной границей) в оптимальном с точки зрения времени и операций параллельном алгоритме MST? | • До какой степени может быть снижена зависимость от случайных бит (по сравнению с нынешней линейной границей) в оптимальном с точки зрения времени и операций параллельном алгоритме MST? | ||
• До какой степени может быть снижена зависимость от случайных бит (по сравнению с нынешней полилогарифмической границей) в оптимальном с точки зрения операций параллельном алгоритме с разумной степенью параллелизма (скажем, имеющем полилогарифмическое время параллельного | • До какой степени может быть снижена зависимость от случайных бит (по сравнению с нынешней полилогарифмической границей) в оптимальном с точки зрения операций параллельном алгоритме с разумной степенью параллелизма (скажем, имеющем полилогарифмическое время параллельного выполнения)? | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Катриэль, Сандерс и Трафф [ ] выполнили экспериментальную оценку алгоритма KKT и показали, что он демонстрирует высокую эффективность на относительно плотных графах. | Катриэль, Сандерс и Трафф [11] выполнили экспериментальную оценку алгоритма KKT и показали, что он демонстрирует высокую эффективность на относительно плотных графах. | ||
== См. также == | == См. также == |
правок