4501
правка
Параллельные алгоритмы вычисления компонент связности и минимальных остовных деревьев: различия между версиями
Перейти к навигации
Перейти к поиску
Параллельные алгоритмы вычисления компонент связности и минимальных остовных деревьев (посмотреть исходный код)
Версия от 21:07, 27 марта 2016
, 27 марта 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 19: | Строка 19: | ||
В случае EREW PRAM для решения задач CC и MST в начале восьмидесятых были разработаны алгоритмы с временем исполнения <math>O(log^2 \;n)</math>. Некоторое время считалось, что для моделей с эксклюзивной записью (как для случая одновременного чтения, так и для эксклюзивного) невозможно улучшить временную границу <math>O(log^2 \; n)</math> [8]. Первый прорыв совершили Джонсон и Метаксас [6], предложившие алгоритмы с временем исполнения <math>O(log^{1.5} \; n)</math> для обеих задач. Чонг и Лэм вскоре улучшили этот результат до O(log n log log n). Если допускается рандомизация, то временная сложность может быть уменьшена до ожидаемого времени O(log n) в оптимальном случае [7, 10, 11]. Наконец, Чонг, Хан и Лэм [1] получили алгоритм для задач MST и CC с временем исполнения O(log n) для n + m процессоров, не требующий рандомизации. Заметим, что время <math>\Theta (log \; n)</math> является оптимальным, поскольку данные графовые задачи имеют не меньшую сложность, чем выполнение операции OR для n бит, для которой Кук и коллеги [4] показали, что она требует | В случае EREW PRAM для решения задач CC и MST в начале восьмидесятых были разработаны алгоритмы с временем исполнения <math>O(log^2 \;n)</math>. Некоторое время считалось, что для моделей с эксклюзивной записью (как для случая одновременного чтения, так и для эксклюзивного) невозможно улучшить временную границу <math>O(log^2 \; n)</math> [8]. Первый прорыв совершили Джонсон и Метаксас [6], предложившие алгоритмы с временем исполнения <math>O(log^{1.5} \; n)</math> для обеих задач. Чонг и Лэм вскоре улучшили этот результат до O(log n log log n). Если допускается рандомизация, то временная сложность может быть уменьшена до ожидаемого времени O(log n) в оптимальном случае [7, 10, 11]. Наконец, Чонг, Хан и Лэм [1] получили алгоритм для задач MST и CC с временем исполнения O(log n) для n + m процессоров, не требующий рандомизации. Заметим, что время <math>\Theta (log \; n)</math> является оптимальным, поскольку данные графовые задачи имеют не меньшую сложность, чем выполнение операции OR для n бит, для которой Кук и коллеги [4] показали, что она требует <math>\Omega (log \; n)</math> времени для PRAM с эксклюзивной записью, независимо от количества используемых процессоров. | ||
Рассмотрим примерный подход к вычислению минимального остовного дерева параллельным образом без использования одновременных операций записи. | Рассмотрим примерный подход к вычислению минимального остовного дерева параллельным образом без использования одновременных операций записи. | ||
Без потери общности будем считать, что все веса ребер различны. В таком случае граф G имеет уникальное минимальное остовное дерево; обозначим его как | Без потери общности будем считать, что все веса ребер различны. В таком случае граф G имеет уникальное минимальное остовное дерево; обозначим его как <math>T^*_G \;</math>. Пусть B – подмножество ребер графа G, не содержащих циклов. B естественным образом порождает множество деревьев <math>F = {T_1, T_2, ..., T_l} \;</math>: две вершины G принадлежат к одному дереву, если они связаны ребром из множества B. B называется <math>\lambda</math>-лесом, если каждое дерево <math>T \in F \;</math> имеет не менее <math>\lambda</math> вершин. Например, если множество B пусто, то B является 1-лесом; остовное дерево является n-лесом. | ||
Предположим, что B является <math>\lambda</math>-лесом и все его ребра входят в <math>T^*_G \;</math>. Тогда B может быть дополнено для получения <math>2 \lambda</math>-леса при помощи жадного подхода: | |||
Пусть F' – произвольное подмножество F, включающее все деревья <math>T \in F \;</math> с числом вершин меньше <math>2 \lambda</math>. Для любого дерева из F' выберем его минимальное внешнее ребро (т.е. ребро с минимальным весом, соединяющее его с вершиной вне дерева). Обозначим множество таких ребер за B'. Можно показать, что B' состоит только из ребер, принадлежащих к <math>T^*_G \;</math>, а <math>B \cup B' \;</math> является <math>2 \lambda</math>-лесом. Это обстоятельство позволяет найти <math>T^*_G \;</math> за blog nc шагов следующим образом. | |||