Система непересекающихся множеств: различия между версиями

Материал из Поле цифровой дидактики
 
Строка 20: Строка 20:
* <math>\mathrm{Find}(x)</math>: проходит путь от <math>x</math> до корня дерева и возвращает его (корень в данном случае является представителем).
* <math>\mathrm{Find}(x)</math>: проходит путь от <math>x</math> до корня дерева и возвращает его (корень в данном случае является представителем).


== Эвристики ==
Для ускорения операций {{math|Union}} и {{math|Find}} могут быть использованы эвристики {{math|Union-By-Size}}, {{math|Union-By-Height}}, {{math|Random-Union}} и сжатие путей.
В эвристике {{math|Union-By-Size}} во время операции <math>\mathrm{Union}(r, s)</math> корень меньшего дерева вешается под корень большего дерева. Благодаря этому подходу сохраняется балансировка дерева. Глубина каждого поддерева <math>T</math> не может превысить величину <math>\log \left|T\right|</math>. При использовании этой эвристики время операции {{math|Find}} в худшем случае увеличивается с <math>O(\log n)</math> до <math>O(n)</math>. Для эффективной реализации предлагается сохранять в корне количество узлов в дереве.
Эвристика {{math|Union-By-Height}} аналогична {{math|Union-By-Size}}, но использует высоту дерева вместо размера.
В эвристике {{math|Random-Union}} используется тот факт, что можно не тратить дополнительные <math>O(n)</math> памяти на сохранение количества узлов в дереве: достаточно выбирать корень случайным образом — такое решение даёт на случайных запросах скорость, вполне сравнимую с другими реализациями. Тем не менее, если имеется много запросов вида «объединить большое множество с маленьким», данная эвристика улучшает [[матожидание]] (то есть среднее время работы) всего в два раза, поэтому использовать её без эвристики сжатия путей не рекомендуется.
Эвристика сжатия путей используется, чтобы ускорить операцию <math>\mathrm{Find}(x)</math>. При каждом новом поиске все элементы, находящиеся на пути от корня до искомого элемента, вешаются под корень дерева. В этом случае операция {{math|Find}} будет работать в среднем <math>\alpha(n)</math>, где <math>\alpha</math> — функция, обратная [[Функция Аккермана|функции Аккермана]]. Это позволяет значительно ускорить работу, так как <math>\alpha</math> для всех применяемых на практике значений принимает значение, меньшее 5.




[[Категория:Структуры данных]]
[[Категория:Структуры данных]]

Текущая версия на 13:38, 16 февраля 2024

Система непересекающихся множеств — структура данных, которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. Абстрактная структура данных определяется множеством трёх операций: [math]\displaystyle{ \{\mathrm{Union}, \mathrm{Find}, \mathrm{MakeSet}\} }[/math].

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

Определение

Пусть [math]\displaystyle{ S }[/math] конечное множество, разбитое на непересекающиеся подмножества (классы) [math]\displaystyle{ X_i }[/math]:

[math]\displaystyle{ S = X_0 \cup X_1 \cup X_2 \cup \ldots \cup X_k: X_i \cap X_j = \varnothing \quad\forall i, j \in \lbrace 0, 1, \ldots, k \rbrace, i \neq j }[/math].

Каждому подмножеству [math]\displaystyle{ X_i }[/math] назначается представитель [math]\displaystyle{ r_i \in X_i }[/math]. Соответствующая система непересекающихся множеств поддерживает следующие операции:

  • [math]\displaystyle{ \mathrm{MakeSet}(x) }[/math]: создаёт для элемента [math]\displaystyle{ x }[/math] новое подмножество. Назначает этот же элемент представителем созданного подмножества.
  • [math]\displaystyle{ \mathrm{Union}(r, s) }[/math]: объединяет оба подмножества, принадлежащие представителям [math]\displaystyle{ r }[/math] и [math]\displaystyle{ s }[/math], и назначает [math]\displaystyle{ r }[/math] представителем нового подмножества.
  • [math]\displaystyle{ \mathrm{Find}(x) }[/math]: определяет для [math]\displaystyle{ x \in S }[/math] подмножество, к которому принадлежит элемент, и возвращает его представителя.

Алгоритмическая реализация

Тривиальная реализация сохраняет принадлежность элементов из [math]\displaystyle{ S }[/math] и представителей [math]\displaystyle{ r_i }[/math] в индексном массиве. На практике же чаще используются множества деревьев. Это позволяет существенно сократить время, необходимое для операции Шаблон:Math. При этом представитель записывается в корень дерева, а остальные элементы класса в узлы под ним.

  • [math]\displaystyle{ \mathrm{Union}(r, s) }[/math]: вешает корень более низкого дерева под корень более высокого дерева. Если при этом [math]\displaystyle{ r }[/math] становится потомком [math]\displaystyle{ s }[/math], оба узла меняются местами.
  • [math]\displaystyle{ \mathrm{Find}(x) }[/math]: проходит путь от [math]\displaystyle{ x }[/math] до корня дерева и возвращает его (корень в данном случае является представителем).
Источник — http://digida.mgpu.ru/index.php?title=Система_непересекающихся_множеств&oldid=15686