Из Википедии, свободной энциклопедии
  (Перенаправлено из структуры данных Disjoint set )
Перейти к навигации Перейти к поиску
Disjoint-set / Союз-найти лес
Типмногостороннее дерево
Изобрел1964 г.
ИзобретенныйБернард А. Галлер и Майкл Дж. Фишер
Сложность времени в большой нотации O
АлгоритмВ среднемХудший случай
КосмосO ( n ) [1]O ( n ) [1]
ПоискO ( α ( n )) [1]O ( α ( n )) [1]
ОбъединитьO ( α ( n )) [1]O ( α ( n )) [1]
MakeSet создает 8 синглтонов.
После некоторых операций Union некоторые наборы группируются вместе.

В информатике , система непересекающиеся множеств , называются также профсоюз структура данных или набор слияния находки , это структура данных , которая хранит совокупность непересекающегося (неперекрывающаяся) множества. Точно так же он хранит разбиение набора на непересекающиеся подмножества. Он предоставляет операции для добавления новых наборов, слияния наборов (замены их объединением ) и поиска представительного члена набора. Последняя операция позволяет оперативно узнать, находятся ли какие-либо два элемента в одном или разных наборах.

Хотя существует несколько способов реализации структур данных с непересекающимися наборами, на практике они часто отождествляются с конкретной реализацией, называемой лесом с непересекающимися наборами . Это специализированный тип леса, который выполняет союзы и находки в почти постоянное амортизированное время. Для выполнения последовательности из m операций сложения, объединения или поиска в лесу с непересекающимися множествами с n узлами требуется общее время O ( m α ( n )) , где α ( n ) - чрезвычайно медленно растущая обратная функция Аккермана.. Леса с непересекающимися наборами не гарантируют такую ​​производительность для каждой операции. Отдельные операции объединения и поиска могут занимать больше времени, чем постоянное время, умноженное на α ( n ) , но каждая операция заставляет непересекающийся лес настраиваться таким образом, чтобы последующие операции выполнялись быстрее. Непересекающиеся леса асимптотически оптимальны и практически эффективны.

Структуры данных с непересекающимися наборами играют ключевую роль в алгоритме Крускала для поиска минимального остовного дерева графа. Важность минимальных остовных деревьев означает, что структуры данных с непересекающимися наборами лежат в основе множества алгоритмов. Кроме того, структуры данных с непересекающимся набором также имеют приложения для символьных вычислений, а также в компиляторах, особенно для проблем с распределением регистров .

История [ править ]

Дизъюнктные посаженные леса были впервые описаны Bernard A. Galler и Michael J. Фишер в 1964 году [2] В 1973 году , их временная сложность была ограничена до , то повторного логарифма из , по Hopcroft и Ульмана . [3] В 1975 году Роберт Тарьян первым доказал ( обратную функцию Аккермана ) верхнюю границу временной сложности алгоритма [4], а в 1979 году показал, что это была нижняя граница для ограниченного случая. [5] В 1989 году Фредман и Сакс показали, что(амортизированные) слова должны быть доступны любой структуре данных с непересекающимся набором для каждой операции [6], тем самым доказывая оптимальность структуры данных.

В 1991 году Галил и Итальяно опубликовали обзор структур данных для непересекающихся множеств. [7]

В 1994 году Ричард Дж. Андерсон и Хизер Уолл описали распараллеленную версию Union-Find, которая никогда не требует блокировки. [8]

В 2007 году Сильвен Коншон и Жан-Кристоф Филлиатр разработали стойкую версию структуры данных с непересекающимся набором данных, позволяющую эффективно сохранять предыдущие версии структуры, и формализовали ее правильность с помощью помощника по доказательству Coq . [9] Однако реализация является асимптотической только в том случае, если используется эфемерно или если одна и та же версия структуры используется повторно с ограниченным поиском с возвратом.

Представление [ править ]

Каждый узел в лесу непересекающихся множеств состоит из указателя и некоторой вспомогательной информации, будь то размер или ранг (но не оба сразу). Указатели используются для создания родительских деревьев указателей , где каждый узел, не являющийся корнем дерева, указывает на своего родителя. Чтобы отличать корневые узлы от других, их родительские указатели имеют недопустимые значения, такие как циклическая ссылка на узел или контрольное значение. Каждое дерево представляет собой набор, хранящийся в лесу, при этом элементы набора являются узлами в дереве. Корневые узлы предоставляют представителей множества: два узла находятся в одном наборе тогда и только тогда, когда корни деревьев, содержащих узлы, равны.

Узлы в лесу можно хранить любым удобным для приложения способом, но обычно их хранят в массиве. В этом случае родители могут быть обозначены индексом их массива. Для каждой записи массива требуется как минимум O (lg n ) бит памяти для родительского указателя. Для остальной части записи требуется сопоставимый или меньший объем памяти, поэтому количество битов, необходимых для хранения леса, равно O ( n lg n ) . Если реализация использует узлы фиксированного размера (тем самым ограничивая максимальный размер леса, который может быть сохранен), то необходимое хранилище линейно по n .

Операции [ править ]

Структуры данных с непересекающимся набором поддерживают три операции: создание нового набора, содержащего новый элемент; Нахождение представителя множества, содержащего заданный элемент; и Слияние двух наборов.

Изготовление новых наборов [ править ]

Операция MakeSet добавляет новый элемент. Этот элемент помещается в новый набор, содержащий только новый элемент, и новый набор добавляется в структуру данных. Если вместо этого структура данных рассматривается как раздел набора, то операция MakeSet увеличивает набор, добавляя новый элемент, и расширяет существующий раздел, помещая новый элемент в новое подмножество, содержащее только новый элемент.

В непересекающемся лесу MakeSet инициализирует родительский указатель узла и размер или ранг узла. Если корень представлен узлом, который указывает на себя, то добавление элемента можно описать с помощью следующего псевдокода:

function  MakeSet ( x ) -  если  x еще не в лесу, то  x .parent: = x  x .size: = 1 // если узлы хранят размер  x .rank: = 0 // если узлы хранят ранг  end if end function

Эта операция имеет постоянную временную сложность. В частности, инициализация леса непересекающихся множеств с n узлами требует времени O ( n ) .

На практике MakeSet должна предшествовать операция, которая выделяет память для хранения x . Пока выделение памяти является амортизированной операцией с постоянным временем, как и в случае хорошей реализации динамического массива , оно не меняет асимптотическую производительность леса случайного набора.

Поиск представителей множества [ править ]

Операция Find следует по цепочке родительских указателей от указанного узла запроса x до тех пор, пока не достигнет корневого элемента. Этот корневой элемент представляет собой набор, которому принадлежит x, и может быть самим x . Find возвращает корневой элемент, которого он достигает.

Выполнение операции поиска представляет собой важную возможность для улучшения леса. Время в операции поиска тратится на погоню за родительскими указателями, поэтому более плоское дерево приводит к ускорению операций поиска . Когда выполняется поиск , нет более быстрого способа достичь корня, чем последовательное отслеживание каждого родительского указателя. Однако родительские указатели, посещенные во время этого поиска, могут быть обновлены, чтобы они указывали ближе к корню. Поскольку каждый элемент, посещаемый на пути к корню, является частью одного и того же набора, это не меняет наборы, хранящиеся в лесу. Но это делает будущую находкуоперации выполняются быстрее не только для узлов между узлом запроса и корнем, но и для их потомков. Это обновление является важной частью гарантии амортизированной производительности несвязанного леса.

Существует несколько алгоритмов поиска, которые обеспечивают асимптотически оптимальную временную сложность. Одно семейство алгоритмов, известное как сжатие пути , делает каждый узел между узлом запроса и корнем точкой к корню. Сжатие пути может быть реализовано с помощью простой рекурсии следующим образом:

function  Find ( x ) is  if  x .parent ≠ x  then  x .parent: = Find ( x .parent) return  x .parent else  return  x  end if end function

Эта реализация делает два прохода: один вверх по дереву, а другой - вниз. Требуется достаточно оперативной памяти для хранения пути от узла запроса к корню (в приведенном выше псевдокоде путь неявно представлен с помощью стека вызовов). Его можно уменьшить до постоянного объема памяти, выполняя оба прохода в одном направлении. Реализация постоянной памяти проходит от узла запроса к корню дважды: один раз для поиска корня и один раз для обновления указателей:

функция  Find ( x ) является  root  : = x,  а  root .parent ≠ root  do  root  : = root .parent end while в то время как  x .parent ≠ root  do  parent  : = x .parent x .parent: = root  x  : = родительский  конец while вернуть  корневую конечную функцию

Тарьян и Ван Левен также разработали однопроходные алгоритмы поиска , которые сохраняют ту же сложность наихудшего случая, но более эффективны на практике. [4] Это называется разделением пути и делением пути пополам. Оба они обновляют родительские указатели узлов на пути между узлом запроса и корнем. Разделение пути заменяет каждый родительский указатель на этом пути указателем на прародителя узла:

функция  Find ( x ) - это  while  x .parent ≠ x  do ( x , x .parent): = ( x .parent, x .parent.parent) end while  return  x end function

Деление пути пополам работает аналогично, но заменяет только все остальные родительские указатели:

функция  Find ( x ) - это  while  x .parent ≠ x  do  x .parent: = x .parent.parent x  : = x .parent end while  return  x end function

Объединение двух наборов [ править ]

Операция Union ( x , y ) заменяет набор, содержащий x, и набор, содержащий y, их объединением. Сначала Union использует Find для определения корней деревьев, содержащих x и y . Если корни одинаковые, делать больше нечего. В противном случае необходимо объединить два дерева. Это делается либо установкой родительского указателя x на y , либо установкой родительского указателя y на x .

Выбор того, какой узел станет родительским, имеет последствия для сложности будущих операций с деревом. Если это сделать неаккуратно, деревья могут стать слишком высокими. Например, предположим, что Union всегда делал дерево, содержащее x, поддеревом дерева, содержащего y . Начните с леса, который только что был инициализирован элементами 1, 2, 3, ..., n , и выполните Union (1, 2) , Union (2, 3) , ..., Union ( n - 1, n ) . Результирующий лес содержит одно дерево, корень которого равен n , и путь от 1 до n.проходит через каждый узел в дереве. Для этого леса время выполнения Find (1) составляет O ( n ) .

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

В случае объединения по размеру узел сохраняет свой размер, который представляет собой просто количество его потомков (включая сам узел). Когда деревья с корнями x и y объединяются, узел с большим количеством потомков становится родителем. Если у двух узлов одинаковое количество потомков, то любой из них может стать родителем. В обоих случаях размер нового родительского узла устанавливается равным новому общему количеству потомков.

function  Union ( x , y ) is  // Заменим узлы корнями  x  : = Find ( x ) y  : = Find ( y ) if  x = y  then  return  // x и y уже находятся в одном наборе  end if // При необходимости переименуйте переменные, чтобы  // у x было не меньше потомков, чем у y,  если  x .size < y .size then ( x , y ): = ( y , x ) end if // Сделать x новым корнем  y .parent: = x  // Обновить размер x  x .size: = x .size + y .size end function

Количество битов, необходимых для хранения размера, явно равно количеству битов, необходимых для хранения n . Это добавляет постоянный коэффициент к требуемому хранилищу леса.

Для объединения по рангу узел сохраняет свой ранг , который является верхней границей его высоты. Когда узел инициализируется, его ранг устанавливается на ноль. Чтобы объединить деревья с корнями x и y , сначала сравните их ранги. Если ранги различны, тогда большее дерево рангов становится родителем, и ранги x и y не меняются. Если ранги одинаковы, то любой из них может стать родителем, но ранг нового родителя увеличивается на единицу. Хотя ранг узла явно связан с его высотой, хранение рангов более эффективно, чем сохранение высот. Высота узла может изменяться во время поиска.операции, поэтому хранение рядов позволяет избежать дополнительных усилий по поддержанию правильной высоты. В псевдокоде объединение по рангу:

function  Union ( x , y ) is  // Заменим узлы корнями  x  : = Find ( x ) y  : = Find ( y ) if  x = y  then  return  // x и y уже находятся в одном наборе  end if // При необходимости переименовать переменные, чтобы  // x имел ранг не меньше, чем ранг y,  если  x .rank < y .rank then ( x , y ): = ( y , x ) end if // Сделать x новым корнем  y .parent: = x  // При необходимости увеличить ранг x, если  x .rank = y .rank, затем  x .rank: = x .rank + 1 end if end function

Можно показать , что каждый узел имеет ранг ⌊lg п ⌋ или меньше. [10] Следовательно, ранг может храниться в O (log log n ) битах, что делает его асимптотически незначительной частью размера леса.

Из приведенных выше реализаций ясно, что размер и ранг узла не имеют значения, если только узел не является корнем дерева. Как только узел становится дочерним, его размер и ранг больше не доступны.

Сложность времени [ править ]

Реализация леса с непересекающимся набором, в которой Find не обновляет родительские указатели и в которой Union не пытается управлять высотой дерева, может иметь деревья с высотой O ( n ) . В такой ситуации операции Find и Union требуют времени O ( n ) .

Если реализация использует только сжатие пути, то последовательность из n операций MakeSet , за которыми следуют до n - 1 операций Union и f операций поиска , имеет время выполнения в наихудшем случае . [10]

Используя объединение по рангу, но без обновления родительских указателей во время Находки , дает время выполнения для м операций любого типа, вплоть до п из которых являются MakeSet операция. [10]

Комбинация сжатия, разделения или деления пути пополам с объединением по размеру или рангу сокращает время выполнения m операций любого типа, до n из которых являются операциями MakeSet , до . [4] [5] Это делает амортизированное время работы каждой операции . Это асимптотически оптимально, что означает, что каждая структура данных непересекающегося набора должна использовать амортизированное время на операцию. [6] Здесь функция - обратная функция Аккермана . Обратная функция Аккермана растет чрезвычайно медленно, поэтому этот множитель равен 4 или меньше для любого n.это действительно может быть записано в физической вселенной. Это делает операции с непересекающимися множествами практически амортизированными с постоянным временем.

Доказательство O (log * (n)) временной сложности Union-Find [ править ]

Точный анализ производительности непересекающегося леса несколько сложен. Однако существует гораздо более простой анализ, который доказывает, что амортизированное время для любых m операций поиска или объединения в лесу с непересекающимися множествами, содержащем n объектов, равно O (log * n ) , где log * обозначает повторный логарифм . [11] [12] [13] [14]

Лемма 1. По мере того, как функция find следует по пути к корню, ранг узла, с которым она сталкивается, увеличивается.

Доказательство: заявите, что, поскольку операции Find и Union применяются к набору данных, этот факт остается верным с течением времени. Изначально, когда каждый узел является корнем своего собственного дерева, это тривиально верно. Единственный случай, когда ранг узла может быть изменен, - это когда применяется операция объединения по рангу . В этом случае дерево с меньшим рангом будет прикреплено к дереву с большим рангом, а не наоборот. И во время операции поиска все узлы, посещенные по пути, будут привязаны к корню, который имеет больший ранг, чем его дочерние элементы, поэтому эта операция также не изменит этого факта.

Лемма 2: узел u, который является корнем поддерева ранга r, имеет не менее 2 r узлов.

Доказательство: изначально, когда каждый узел является корнем своего собственного дерева, это тривиально верно. Предположим, что узел u ранга r имеет не менее 2 r узлов. Затем, когда два дерева с рангом r объединяются по рангу и образуют дерево с рангом r + 1, новый узел имеет не менее 2 r + 2 r = 2 r + 1 узлов.

Лемма 3: максимальное количество узлов ранга r не превосходит n / 2 r .

Доказательство. Из леммы 2 мы знаем, что узел u, являющийся корнем поддерева ранга r, имеет не менее 2 r узлов. Мы получим максимальное количество узлов ранга r, когда каждый узел ранга r является корнем дерева, которое имеет ровно 2 r узлов. В этом случае количество узлов ранга r равно n / 2 r

Для удобства мы определяем здесь «ведро»: ведро - это набор, содержащий вершины с определенными рангами.

Мы создаем несколько ведер и индуктивно помещаем в них вершины в соответствии с их рангами. То есть вершины с рангом 0 попадают в нулевое ведро, вершины с рангом 1 - в первое, а вершины с рангом 2 и 3 - во второе ведро. Если B-й блок содержит вершины с рангами из интервала [ r , 2 r - 1] = [r, R - 1], то (B + 1) -ое ведро будет содержать вершины с рангами из интервала [R, 2 R - 1] .

Доказательство поиска союза

Мы можем сделать два замечания по поводу ведер.

  1. Общее количество сегментов не превышает log * n.
    Доказательство: когда мы переходим от одного ведра к другому, мы добавляем еще два к мощности, то есть следующее ведро к [ B , 2 B - 1] будет [2 B , 2 2 B - 1].
  2. Максимальное количество элементов в сегменте [ B , 2 B - 1] не превышает 2 n / 2 B.
    Доказательство: максимальное количество элементов в корзине [ B , 2 B - 1] не превышает n / 2 B + n / 2 B +1 + n / 2 B +2 +… + n / 2 2 B - 1 ≤ 2. n / 2 B

Пусть F представляет список выполненных операций "поиска", и пусть

Тогда общая стоимость m находок составит T = T 1 + T 2 + T 3.

Поскольку каждая операция поиска выполняет ровно один обход, ведущий к корню, мы имеем T 1 = O ( m ).

Кроме того, исходя из приведенной выше оценки количества ведер, мы имеем T 2 = O ( m log * n ).

Для T 3 предположим, что мы пересекаем ребро от u до v , где u и v имеют ранг в ведре [ B , 2 B - 1], а v не является корнем (во время этого обхода, иначе обход был бы учитываться в Т 1 ). Зафиксируем u и рассмотрим последовательность v 1 , v 2 , ..., v k, которые играют роль v в различных операциях поиска. Из-за сжатия пути и без учета края до корня эта последовательность содержит только разные узлы и из-заПо лемме 1 мы знаем, что ранги узлов в этой последовательности строго возрастают. По тому, что оба узла находятся в ведре, мы можем заключить, что длина последовательности k (количество раз, когда узел u присоединяется к другому корню в одном и том же ведре) не превосходит количество рангов в корзинах B , т. Е. не более 2 B - 1 - B <2 B .

Следовательно,

Из наблюдений 1 и 2 можно сделать вывод, что

Следовательно, T = T 1 + T 2 + T 3 = O ( m log * n ).

Приложения [ править ]

Демонстрация Union-Find при использовании алгоритма Крускала для поиска минимального остовного дерева.

Дизъюнктные-набор структур данных моделировать разбиение множества , например , чтобы следить за компонент связности в качестве неориентированного графа . Затем эту модель можно использовать, чтобы определить, принадлежат ли две вершины одному и тому же компоненту, или добавление ребра между ними приведет к возникновению цикла. Алгоритм Union – Find используется в высокопроизводительных реализациях унификации . [15]

Эта структура данных используется библиотекой Boost Graph Library для реализации своих функций инкрементальных подключенных компонентов . Это также ключевой компонент в реализации алгоритма Крускала для поиска минимального остовного дерева графа.

Обратите внимание, что реализация в виде непересекающихся лесов не позволяет удалять ребра даже без сжатия пути или эвристики ранжирования.

Шарир и Агарвал сообщают о связи между наихудшим поведением непересекающихся множеств и длиной последовательностей Давенпорта – Шинцеля , комбинаторной структуры из вычислительной геометрии. [16]

См. Также [ править ]

  • Уточнение разделов , другая структура данных для поддержки непересекающихся наборов, с обновлениями, которые разделяют, а не объединяют их вместе.
  • Динамическое подключение

Ссылки [ править ]

  1. ^ a b c d e f Тарьян, Роберт Эндре (1975). «Эффективность хорошего, но не линейного алгоритма объединения множеств». Журнал ACM . 22 (2): 215–225. DOI : 10.1145 / 321879.321884 . hdl : 1813/5942 . S2CID  11105749 .
  2. ^ Галлер, Бернард А .; Фишер, Майкл Дж. (Май 1964 г.). «Улучшенный алгоритм эквивалентности». Коммуникации ACM . 7 (5): 301–303. DOI : 10.1145 / 364099.364331 . S2CID 9034016 . . Бумага, порождающая непересекающиеся леса.
  3. ^ Хопкрофт, JE ; Ульман, JD (1973). «Установить алгоритмы слияния». SIAM Journal on Computing . 2 (4): 294–303. DOI : 10.1137 / 0202024 .
  4. ^ a b c Тарьян, Роберт Э .; ван Леувен, Ян (1984). «Анализ наихудшего случая алгоритмов объединения множеств». Журнал ACM . 31 (2): 245–281. DOI : 10.1145 / 62.2160 . S2CID 5363073 . 
  5. ^ а б Тарьян, Роберт Эндре (1979). «Класс алгоритмов, которые требуют нелинейного времени для поддержания непересекающихся множеств». Журнал компьютерных и системных наук . 18 (2): 110–127. DOI : 10.1016 / 0022-0000 (79) 90042-4 .
  6. ^ a b Фредман, М .; Сакс, М. (май 1989 г.). «Ячейка зондирования сложности динамических структур данных». Материалы двадцать первого ежегодного симпозиума ACM по теории вычислений : 345–354. DOI : 10.1145 / 73007.73040 . ISBN 0897913078. S2CID  13470414 . Теорема 5: Любая реализация CPROBE (log n ) задачи объединения множеств требует времени Ω ( m α ( m , n )) для выполнения m Find и n −1 Union, начиная с n одноэлементных наборов.
  7. ^ Галил, З .; Итальяно, Г. (1991). «Структуры данных и алгоритмы для задач объединения непересекающихся множеств». ACM Computing Surveys . 23 (3): 319–344. DOI : 10.1145 / 116873.116878 . S2CID 207160759 . 
  8. ^ Андерсон, Ричард Дж .; Уолл, Хизер (1994). Параллельные алгоритмы без ожидания для задачи поиска объединения . 23-й симпозиум ACM по теории вычислений. С. 370–380.
  9. ^ Кончон, Сильвен; Филлиатр, Жан-Кристоф (октябрь 2007 г.). «Постоянная структура данных поиска союза». ACM SIGPLAN Мастер-класс по ML . Фрайбург, Германия.
  10. ^ a b c Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009). «Глава 21: Структуры данных для непересекающихся множеств». Введение в алгоритмы (третье изд.). MIT Press. С. 571–572. ISBN 978-0-262-03384-8.
  11. ^ Раймунд Зайдель , Миха Шарир. «Нисходящий анализ сжатия пути», SIAM J. Comput. 34 (3): 515–525, 2005.
  12. ^ Тарьян, Роберт Эндре (1975). «Эффективность хорошего, но не линейного алгоритма объединения множеств» . Журнал ACM . 22 (2): 215–225. DOI : 10.1145 / 321879.321884 . hdl : 1813/5942 . S2CID 11105749 . 
  13. ^ Хопкрофт, JE; Ульман, JD (1973). «Установить алгоритмы слияния». SIAM Journal on Computing . 2 (4): 294–303. DOI : 10.1137 / 0202024 .
  14. ^ Роберт Э. Тарджан и Ян ван Леувен . Анализ наихудшего случая алгоритмов объединения множеств. Журнал ACM, 31 (2): 245–281, 1984.
  15. ^ Рыцарь, Кевин (1989). «Унификация: междисциплинарный обзор» (PDF) . ACM Computing Surveys . 21 : 93–124. DOI : 10.1145 / 62029.62030 . S2CID 14619034 .  
  16. ^ Шарир, М .; Агарвал П. (1995). Последовательности Давенпорта-Шинцеля и их геометрические приложения . Издательство Кембриджского университета.

Внешние ссылки [ править ]

  • Реализация C ++ , часть библиотек Boost C ++
  • Реализация Java с приложением для сегментации цветных изображений, Статистическое объединение областей (SRM), IEEE Trans. Pattern Anal. Мах. Intell. 26 (11): 1452–1458 (2004).
  • Java-апплет: графическое объединение - реализация поиска , Рори Л.П. Макгуайр
  • Реализация Matlab, которая является частью библиотеки компонентов трекера
  • Реализация Python
  • Визуальное объяснение и код C #