4551
правка
Распределенные алгоритмы для минимальных остовных деревьев: различия между версиями
Материал из WEGA
Распределенные алгоритмы для минимальных остовных деревьев (посмотреть исходный код)
Версия от 23:29, 28 ноября 2013
, 28 ноября 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 13: | Строка 13: | ||
== Основные результаты == | == Основные результаты == | ||
Задача создания распределенного алгоритма MST изучается с 1977 года, ей посвящены десятки статей. В 1983 году был опубликован фундаментальный алгоритм GHS [5] – первый алгоритм решения задачи MST со сложностью в сообщениях, равной O(m + n log n). Эта статья имела огромное влияние на исследования в этой области и была удостоена премии Дейкстры 2004 года в области распределенных вычислений. | Задача создания распределенного алгоритма MST изучается с 1977 года, ей посвящены десятки статей. В 1983 году был опубликован фундаментальный алгоритм GHS [5] – первый алгоритм решения задачи MST со сложностью в сообщениях, равной <math>O(m + n \; log n)</math>. Эта статья имела огромное влияние на исследования в этой области и была удостоена премии Дейкстры 2004 года в области распределенных вычислений. | ||
Нетрудно увидеть, что любой распределенный MST-алгоритм должен иметь сложность в сообщениях, равную <math>\Omega (m) \; </math> (интуитивно понятно, что по каждой дуге должно пройти хотя бы одно сообщение). В [3, 4] было показано, что нижней границей сложности в сообщениях служит <math>\Omega (n \; log n)</math>. Таким образом, алгоритм GHS является оптимальным по сложности в сообщениях. | Нетрудно увидеть, что любой распределенный MST-алгоритм должен иметь сложность в сообщениях, равную <math>\Omega (m) \; </math> (интуитивно понятно, что по каждой дуге должно пройти хотя бы одно сообщение). В [3, 4] было показано, что нижней границей сложности в сообщениях служит <math>\Omega (n \; log n)</math>. Таким образом, алгоритм GHS является оптимальным по сложности в сообщениях. | ||
Нижняя граница сложности в сообщениях <math>\Omega (m + n \; log n)</math> при построении MST наблюдается также при решении задачи нахождения произвольного остовного дерева графа. Однако для конкретных топологий графов может оказаться проще найти произвольное остовное дерево, чем минимальное. В случае полного графа для построения MST требуется <math>\Omega (n^2) \; </math> сообщений [8], тогда как произвольное остовное дерево может быть построено за <math> | Нижняя граница сложности в сообщениях <math>\Omega (m + n \; log n)</math> при построении MST наблюдается также при решении задачи нахождения произвольного остовного дерева графа. Однако для конкретных топологий графов может оказаться проще найти произвольное остовное дерево, чем минимальное. В случае полного графа для построения MST требуется <math>\Omega (n^2) \; </math> сообщений [8], тогда как произвольное остовное дерево может быть построено за <math>O(n \; log n)</math> сообщений [7]. | ||
Временная сложность алгоритма GHS составляет O(n log n). В [ ] предложен механизм улучшения временной сложности до O(n) при сохранении оптимальной сложности в сообщениях – O(m + nlog n). Очевидно, что построение остовного дерева требует времени Q{D), где D – диаметр графа. В случае минимального остовного дерева временная сложность может зависеть и от других параметров графа. К примеру, в силу необходимости потока информации между процессорами, входящими в цикл (как это бывает при построении MST), по крайней мере одна дуга цикла должна быть исключена из MST. В случае, если разрешены сообщения неограниченного размера, MST можно легко построить за время O(D), путем сбора данных о топологии графа и весах дуг в корневом процессоре. Задача становится более сложной в реалистичной модели, в которой сообщения имеют размер O(log n), а вес дуги может быть отправлен отдельным сообщением. Если число сообщений не имеет значения, без потери общности можно предположить, что модель является синхронной. Сведения об алгоритмах, близких к оптимальным по времени, и нижних границах см. в [ ] и соответствующих ссылках. | Временная сложность алгоритма GHS составляет <math>O(n \; log n)</math>. В [1] предложен механизм улучшения временной сложности до O(n) при сохранении оптимальной сложности в сообщениях – O(m + nlog n). Очевидно, что построение остовного дерева требует времени Q{D), где D – диаметр графа. В случае минимального остовного дерева временная сложность может зависеть и от других параметров графа. К примеру, в силу необходимости потока информации между процессорами, входящими в цикл (как это бывает при построении MST), по крайней мере одна дуга цикла должна быть исключена из MST. В случае, если разрешены сообщения неограниченного размера, MST можно легко построить за время O(D), путем сбора данных о топологии графа и весах дуг в корневом процессоре. Задача становится более сложной в реалистичной модели, в которой сообщения имеют размер O(log n), а вес дуги может быть отправлен отдельным сообщением. Если число сообщений не имеет значения, без потери общности можно предположить, что модель является синхронной. Сведения об алгоритмах, близких к оптимальным по времени, и нижних границах см. в [ ] и соответствующих ссылках. | ||
== Применение == | == Применение == | ||
