4551
правка
Распределенные алгоритмы для минимальных остовных деревьев: различия между версиями
Перейти к навигации
Перейти к поиску
Распределенные алгоритмы для минимальных остовных деревьев (посмотреть исходный код)
Версия от 23:25, 28 ноября 2013
, 28 ноября 2013→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Рассмотрим коммуникационную сеть, моделируемую неориентированным взвешенным графом G = (V, E), где |V| = n, |E| = m. Каждая вершина V представляет процессор неограниченной вычислительной мощности; процессоры имеют уникальные идентификационные номера и общаются друг с другом посредством дуг из E, по которым они пересылают друг другу сообщения. Кроме того, каждой дуге <math>e \in E</math> присвоен вес w(e), известный процессорам в концевых точках e. Таким образом, каждому процессору известны инцидентные ему дуги и их веса, однако никакой другой информации о графе G он не имеет. Сеть является [[асинхронная сеть|асинхронной]]: каждый процессор работает на произвольной скорости, не зависящей от скорости других процессоров. Процессор может «проснуться» спонтанным образом либо в результате получения сообщения от другого процессора. В сети не имеется конфликтов; каждое посланное сообщение прибывает по месту назначения с конечной, но произвольной задержкой. [[распределенный алгоритм|Распределенный алгоритм]] A для графа G представляет собой множество локальных алгоритмов, по одному для каждого процессора G, включающих команды для отправки и получения сообщений по ребрам графа. Предположим, что алгоритм A завершает работу (то есть все локальные алгоритмы в конечном итоге завершают работу); тогда его ''сложность в сообщениях'' представляет собой полное число сообщений, переданных при любом варианте исполнения алгоритма, в наихудшем случае. ''Временная сложность'' алгоритма представляет собой время исполнения в наихудшем случае, в предположении, что циклы процессора требуют пренебрежимо малого времени, а нормализованные задержки сообщений не превышают 1 единицы измерения. | Рассмотрим коммуникационную сеть, моделируемую неориентированным взвешенным графом G = (V, E), где |V| = n, |E| = m. Каждая вершина V представляет процессор неограниченной вычислительной мощности; процессоры имеют уникальные идентификационные номера и общаются друг с другом посредством дуг из E, по которым они пересылают друг другу сообщения. Кроме того, каждой дуге <math>e \in E</math> присвоен вес w(e), известный процессорам в концевых точках e. Таким образом, каждому процессору известны инцидентные ему дуги и их веса, однако никакой другой информации о графе G он не имеет. Сеть является [[асинхронная сеть|асинхронной]]: каждый процессор работает на произвольной скорости, не зависящей от скорости других процессоров. Процессор может «проснуться» спонтанным образом либо в результате получения сообщения от другого процессора. В сети не имеется конфликтов; каждое посланное сообщение прибывает по месту назначения с конечной, но произвольной задержкой. [[распределенный алгоритм|Распределенный алгоритм]] A для графа G представляет собой множество локальных алгоритмов, по одному для каждого процессора G, включающих команды для отправки и получения сообщений по ребрам графа. Предположим, что алгоритм A завершает работу (то есть все локальные алгоритмы в конечном итоге завершают работу); тогда его ''сложность в сообщениях'' представляет собой полное число сообщений, переданных при любом варианте исполнения алгоритма, в наихудшем случае. ''Временная сложность'' алгоритма представляет собой время исполнения в наихудшем случае, в предположении, что циклы процессора требуют пренебрежимо малого времени, а нормализованные задержки сообщений не превышают 1 единицы измерения. | ||
Минимальное остовное дерево (MST) графа G представляет собой подмножество E' множества дуг E, такое, что граф T = (V, E') представляет собой дерево (связное и ациклическое), а его общий вес <math>w(E') = \sum_{e \in E'} w(e)</math> является насколько возможно малым. Вычисление MST является центральной задачей комбинаторной оптимизации; оно ведет свою историю еще с 1926 года [2]. В работе [12] сведены воедино свойства, классические результаты, варианты применения и последние достижения исследователей в этой области. | [[минимальное остовное дерево|Минимальное остовное дерево]] (MST) графа G представляет собой подмножество E' множества дуг E, такое, что граф T = (V, E') представляет собой дерево (связное и ациклическое), а его общий вес <math>w(E') = \sum_{e \in E'} w(e)</math> является насколько возможно малым. Вычисление MST является центральной задачей комбинаторной оптимизации; оно ведет свою историю еще с 1926 года [2]. В работе [12] сведены воедино свойства, классические результаты, варианты применения и последние достижения исследователей в этой области. | ||
Целью задачи создания распределенного алгоритма для минимальных остовных деревьев является разработка такого распределенного алгоритма A, который всегда завершается и дает в результате минимальное остовное дерево (MST) T для графа G. В конце исполнения каждый процессор знает, какая из инцидентных ему дуг входит в T и какая – нет (т.е. процессор записывает соответствующие инцидентные дуги в локальный выходной регистр). Стоит отметить, что в распределенной версии алгоритма MST коммуникационная сеть решает задачу, входным параметром которой является она сама. Это одно из фундаментальных свойств сетевых алгоритмов. | Целью задачи создания распределенного алгоритма для минимальных остовных деревьев является разработка такого распределенного алгоритма A, который всегда завершается и дает в результате минимальное остовное дерево (MST) T для графа G. В конце исполнения каждый процессор знает, какая из инцидентных ему дуг входит в T и какая – нет (т.е. процессор записывает соответствующие инцидентные дуги в локальный выходной регистр). Стоит отметить, что в распределенной версии алгоритма MST коммуникационная сеть решает задачу, входным параметром которой является она сама. Это одно из фундаментальных свойств сетевых алгоритмов. | ||