4430
правок
Распределенные алгоритмы для минимальных остовных деревьев: различия между версиями
Перейти к навигации
Перейти к поиску
м
Распределенные алгоритмы для минимальных остовных деревьев (посмотреть исходный код)
Версия от 14:25, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Рассмотрим коммуникационную сеть, моделируемую неориентированным взвешенным графом G = (V, E), где |V| = n, |E| = m. Каждая вершина V представляет процессор неограниченной вычислительной мощности; процессоры имеют уникальные идентификационные номера и общаются друг с другом посредством ребер из E, по которым они пересылают друг другу сообщения. Кроме того, каждому ребру <math>e \in E</math> присвоен вес w(e), известный процессорам в концевых точках e. Таким образом, каждому процессору известны инцидентные ему ребра и их веса, однако никакой другой информации о графе G он не имеет. Сеть является [[асинхронная сеть|асинхронной]]: каждый процессор работает на произвольной скорости, не зависящей от скорости других процессоров. Процессор может «проснуться» спонтанным образом либо в результате получения сообщения от другого процессора. В сети не имеется конфликтов; каждое посланное сообщение прибывает по месту назначения с конечной, но произвольной задержкой. [[распределенный алгоритм|Распределенный алгоритм]] A для графа G представляет собой множество локальных алгоритмов, по одному для каждого процессора G, включающих команды для отправки и получения сообщений по ребрам графа. Предположим, что алгоритм A завершает работу (то есть все локальные алгоритмы в конечном итоге завершают работу); тогда его ''сложность в сообщениях'' представляет собой полное число сообщений, переданных при любом варианте | Рассмотрим коммуникационную сеть, моделируемую неориентированным взвешенным графом 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. В конце | Целью задачи создания распределенного алгоритма для минимальных остовных деревьев является разработка такого распределенного алгоритма A, который всегда завершается и дает в результате минимальное остовное дерево (MST) T для графа G. В конце выполнения каждый процессор знает, какая из инцидентных ему ребер входит в T и какая – нет (т.е. процессор записывает соответствующие инцидентные ребра в локальный выходной регистр). Стоит отметить, что в распределенной версии алгоритма MST коммуникационная сеть решает задачу, входным параметром которой является она сама. Это одно из фундаментальных свойств сетевых алгоритмов. | ||
Нетрудно заметить, что в случае, если все ребра имеют разные веса, минимальное остовное дерево является единственным. В силу предположения, что все процессоры имеют уникальные идентификаторы, можно предположить, что все веса ребер различны: если веса двух ребер равны, можно выбрать нужное, используя идентификаторы процессоров на концевых точках ребер. Наличие уникального MST способствует разработке распределенных алгоритмов, так как процессоры могут локально выбирать ребра, принадлежащие уникальному MST. Заметим, что если процессоры не имеют уникальных идентификаторов, а веса ребер не являются различными, не существует детерминированного распределенного алгоритма нахождения минимального остовного дерева (и просто остовного дерева), поскольку в таком случае может оказаться невозможным разрушить симметрию графа – например, в случае цикла, в котором веса всех ребер равны. | Нетрудно заметить, что в случае, если все ребра имеют разные веса, минимальное остовное дерево является единственным. В силу предположения, что все процессоры имеют уникальные идентификаторы, можно предположить, что все веса ребер различны: если веса двух ребер равны, можно выбрать нужное, используя идентификаторы процессоров на концевых точках ребер. Наличие уникального MST способствует разработке распределенных алгоритмов, так как процессоры могут локально выбирать ребра, принадлежащие уникальному MST. Заметим, что если процессоры не имеют уникальных идентификаторов, а веса ребер не являются различными, не существует детерминированного распределенного алгоритма нахождения минимального остовного дерева (и просто остовного дерева), поскольку в таком случае может оказаться невозможным разрушить симметрию графа – например, в случае цикла, в котором веса всех ребер равны. | ||