Разделенные множества и их применение Гвоздева Елена Малова Анна Розенштейн Полина

Определение Разделенные множества (disjoint-set) – это абстрактный тип данных, предназначенный для представления набора (коллекции) попарно непересекающихся подмножеств, т.е,. 2 Разделенные множества и их применение

Определение Формирование новых множеств происходит с помощью: создания одноэлементного множества; объединения уже существующих в коллекции множеств. Имя множества – один из его элементов (представитель), выбираемый по определенному правилу. представитель x S x – обозначение множества 3 Разделенные множества и их применение

Основные операции Make_Set(x) – создает новое множество, состоящее из единственного элемента x, при этом предполагается, что x не входит ни в одно из множеств S, созданных к моменту выполнения этой операции. Именем созданного множества будет считаться сам элемент x. 4 Разделенные множества и их применение

Основные операции Find_Set(x) – возвращает имя множества, в котором содержится x. Union(x,y) – объединяет S x и S y в новое множество, именем которого становится некоторый элемент из, при этом объединяемые множества удаляются из набора. 5 Разделенные множества и их применение

Способы представления разделенных множеств с помощью массива; с помощью связного списка; с помощью древовидной структуры (лес непересекающихся множеств). 6 Разделенные множества и их применение

Представление с помощью массива - множество, из элементов которого будет строиться коллекция разделенных множеств. a1a1 a2a2 x … anan … y ……… yyxx -1 7 Разделенные множества и их применение S M S – массив значений M – массив меток

Реализация основных операций Make_Set(a i ) = запись элемента a i в i ю позицию массива M О( 1 ) ; Find_Set(a i ) = возвратить значение i ой ячейки M О( 1 ) ; Union(x,y) = запись y в ячейки М, содержащие x О( n ); Выполнение m операций, n из которых Union O( mn ). Разделенные множества и их применение 8

Представление с помощью связных списков Первый объект в каждом связанном списке является его именем. Каждый объект в связанном списке содержит указатель на имя множества. head – указатель на представителя tail – указатель на последний объект в списке. 9 Разделенные множества и их применение

Представление с помощью связных списков a8a8 head tail a1a1 a5a5 a2a2 a7a7 head tail a4a4 a6a6 a3a3 head tail 10 Разделенные множества и их применение

Реализации основных операций Make_Set(x) = создание нового списка с единственным объектом х О( 1 ) ; Find_Set(x) = возвратить указатель на представителя объекта, содержащего x О( 1 ). 11 Разделенные множества и их применение

Реализации основных операций Union(x,y) = выбирать, какой из списков длиннее, добавить в конец более короткий, обновить указатели на представителя у каждого объекта, присоединяемого списка Ω( n ). m операций, n = Make_Set(x) О( m+n lg n ) a8a8 head tail a4a4 a6a6 a3a3 head tail a8a8 12 Разделенные множества и их применение

Лес непересекающихся множеств Множества представляются в виде корневых деревьев, где каждый узел содержит один элемент множества, а каждое дерево представляет одно подмножество. Корень дерева – имя множества, является родительским узлом для самого себя. 13 Разделенные множества и их применение

Лес непересекающихся множеств a1a1 a5a5 a2a2 a7a7 a4a4 a3a3 a6a6 a8a8 14 Разделенные множества и их применение a 1 a 2 a4a4 a7a7 a8a8 a6 a6 a1a1 a4a4 a5a5 a1a1 a4a4 a4a4 a1a1 a8a8 S M a3a3 a5a5 S – массив значений M – массив меток

Реализации основных операций Make_Set(x) = создание корневого дерева с одним узлом х О (1) ; Find_Set(x) = передвижение от элемента x до корня дерева по указателям на родительские узлы О (n) ; Union(x,y) = корень одного дерева указывает на корень другого О (1). Выполнение m операций, n из которых найти O( mn ) 15 Разделенные множества и их применение

Лес непересекающихся множеств a1a1 a5a5 a2a2 a7a7 a4a4 a3a3 a6a6 a8a8 Find_Set(a 7 ) Union(a 1,a 4 ) Make_Set(a 8 ) a2a2 16 Разделенные множества и их применение

Эвристики для повышения эффективности Объединение по рангу: при проведении операции Union корень дерева с меньшим количеством указывает на корень дерева с большим количеством узлов. ранг (rank) – верхняя граница высоты узла. При объединении по рангу корень с меньшим рангом должен указывать на корень с большим рангом. 17 Разделенные множества и их применение

Основных операций с применением эвристик Процедура Make_Set создает дерево с корнем x, начальный ранг узла = 0 Разделенные множества и их применение 18

Основных операций с применением эвристик При применении процедуры Union(x,y) две ситуации: rank( x )rank( y ) делаем корень с большим рангом родительским узлом по отношению к корню с меньшим рангом; rank( x )=rank( y ) произвольным образом выбираем один из корней в качестве родительского и увеличиваем его ранг. 19 Разделенные множества и их применение

Эвристики для повышения эффективности Сжатие пути: в процессе выполнения операции Find_Set делает каждый узел пути указывающим непосредственно на корень. Сжатие пути не изменяет ранги узлов. 20 Разделенные множества и их применение a1a1 a5a5 a7a7 a2a2 a1a1 a7a7 a2a2 a5a5

Основных операций с применением эвристик Find_Set выполняется в два прохода : 1. поиск пути к корню дерева; 2. по найденному пути происходит обновление узлов, которые теперь указывают непосредственно на корень дерева. O(log n ) 21 Разделенные множества и их применение

Оценка временной сложности Время выполнения последовательности операций, состоящей из n операций Make_Set, операций u n–1 Union и f операций Find_Set, при использовании рангов и сжатия путей = 0 (( f + n )log*( u )). log*( u ) – суперлогарифм: log*(0)=0; log*( k )=. Разделенные множества и их применение 22 k012345…151617… … log*( k )

Оценка временной сложности Время выполнения последовательности m операций, u из которых операций Union, при совместном использовании обеих эвристик O( m α( u )) где α( u ) –очень медленно растущая функция. Для любых реальных приложений α(n)4. Разделенные множества и их применение 23

Применение распределенных множеств Построение компонент связности графа. Поиск минимального остовного дерева для заданного взвешенного неориентированного графа (алгоритм Краскала). Сегментирование изображений. Генерация лабиринтов. 24 Разделенные множества и их применение

Сегментирование изображений Задача заключается в том, чтобы выделить на изображении одинаковые смысловые зоны, например, похожего цвета, и уметь для двух пикселей быстро определять, находятся ли они в одной зоне. Разделенные множества и их применение 25

Генерация лабиринтов Генерируем лабиринт с одним входом и одним выходом. Начнем с состояния, когда установлены все стены. На каждом шаге алгоритма выберем случайную стену. Если ячейки, между которыми она стоит, еще никак не соединены, т.е находятся в разных подмножествах, то уничтожаем её. Разделенные множества и их применение 26

Построение компонент связности графа V[G] – множество вершин графа G; E[G] – множество ребер. for v V[G] Make_Set(v); for ребро (u,v) E[G] if Find_Set(u)Find_Set(v) Union(u,v); 27 Разделенные множества и их применение

Проведение экспериментов Разделенные множества и их применение 28 Параметры тестового окружения: Процессор Intel (r) Core(TM)2 Quard CPU, 2.4 GHz Память 4 Gb Компилятор Intel® Parallel Studio XE 2011 Сравнение с библиотекой: Boost_1_47_0

Сравнение реализаций Число вершинBoostOur, forestOur, lists 25000,0780,0320, ,2650,1560, ,5930,3430, ,080,5920,155 Разделенные множества и их применение 29 Время работы алгоритма определения числа связных компонент, секунды.

Сравнение реализаций Разделенные множества и их применение 30

Поиск минимального остовного дерева G – взвешенный граф без петель. Требуется построить остовное дерево, накрывающее все вершины графа и имеющее минимальный суммарный вес входящих в него ребер. Разделенные множества и их применение

Поиск минимального остовного дерева V[G] – множество вершин взвешенного графа G; E[G] – множество ребер; T – пустое множество. Алгоритм Краскала: CountComp = n; for v V[G] Make_Set(v); for ребро (u,v) E[G] и CountComp>1 if (u,v)-минимально и Find_Set(u)Find_Set(v) { Union(u,v); CountComp --; добавить (u,v) в T; } Разделенные множества и их применение 32

Сравнение реализаций Число вершинBoostOur, forestOur, lists 25002,2150, ,5930,9991, ,5862,1842, ,2533,9314,04 Разделенные множества и их применение 33 Время работы алгоритма Краскала нахождения минимального остовного дерева, секунды.

Сравнение реализаций Разделенные множества и их применение 34

Выводы Реализации разделенных множеств на списках и с использованием леса непересекающихся множеств дают близкие результаты. Разделенные множества рационально использовать в задачах, требующих динамического поддержания отношения эквивалентности. Часто используются в графовых задачах. Разделенные множества и их применение 35

Литература Кормен Томас Х., Лейзерсон Чарльз И., Ривест Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. М. Издательский дом Вильямс, с. Алексеев В.Е., Таланов В.А. Структуры данных и модели вычислений// Система непересекающихся множеств и её применения//habrahabr.ru/blogs/algorithm/104772/habrahabr.ru/blogs/algorithm/104772/ Disjoint-set data structure//en.wikipedia.org/wiki/Disjoint- set_data_structureen.wikipedia.org/wiki/Disjoint- set_data_structure The Boost Graph Library (BGL)// Разделенные множества и их применение 36