Нояб. 14

Union-find: алгоритм, применение и анализ сложности

Всем привет! Меня зовут Данил, и я Java-разработчик в компании TeamDev, занимаюсь написанием ПО для сетевых устройств.

Думаю, многие из вас читали Роберта Мартина, а может, и являются ценителями его идей. Мне же запомнилась одна его фраза из книги «Идеальный программист»: «Недостаточно выполнять свою повседневную работу и называть ее тренировкой». Тренировкой Мартин называет «применение своих навыков... с единственной целью совершенствования этих навыков».

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

Введение

Как узнать, связаны ли два человека цепочкой общих друзей? Где нужно построить новые дороги, чтобы город B был достижим  из города A? Какая часть людей должна быть восприимчива к болезни, чтобы стала возможна эпидемия?

Для решения подобных задач используют особую структуру данных (union-find), где элементы, будь то города или пользователи социальной сети, распределены на непересекающиеся множества.

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

Немного из теории множеств

Элементы, имеющие общие характеристики, объединяются в множества, как, например, пользователи социальной сети, подписанные на определенное сообщество, или города, которые связаны общими дорогами. Даже не имея связей, элемент образует множество, состоящее из самого себя, — синглтон.

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

Рассмотрим следующую задачу: имеется набор из N объектов, которые связаны между собой каким-то образом. Необходимо определить, существует ли путь, соединяющий выбранные объекты A и B через другие объекты. В теории графов данная задача определена как «задача о динамической связности» (dynamic connectivity).

Задача о динамической связности

Теперь предположим, что связанные между собой объекты — это элементы одного множества. Тогда, чтобы узнать, связаны ли выбранные объекты A и B, достаточно определить, принадлежат ли они одному множеству.

Такую структуру данных, где элементы распределены на непересекающиеся множества, называют системой непересекающихся множеств (union-find data structure).

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

Правила и ограничения

Введем некоторые правила и ограничения, которые помогут смоделировать задачу о динамической связности и реализовать эффективный алгоритм для ее решения:

Не имеет значения, что из себя представляют объекты. Для простоты можно сопоставить N объектам числа от 0 до N  −  1.
Не нужно определять, каким образом объекты связаны между собой, достаточно будет определить, принадлежат ли сопоставляемые им элементы одному множеству.
Когда элементы непересекающихся множеств образуют связь, их множества объединяются.

Интерфейс

Итак, согласно первому правилу элементами множества будут числа от 0 до N − 1. Для решения любых задач, использующих структуру данных union-ﬁnd, будет достаточно определить следующие операции (здесь и далее примеры кода приводятся на языке Java):

    public interface UnionFind {
 
        void union(int p, int q);
 
        boolean connected(int p, int q);
    }

Немного подробнее о каждой из них:

void union(int p, int q) — объединяет элементы p и q, а также множества, которым они принадлежат (правило 3).
boolean connected(int p, int q) — проверяет, принадлежат ли элементы p и q одному множеству.

Жадный алгоритм

Рассмотрим первую реализацию алгоритма для решения задачи о динамической связности под названием Quick-find, которая относится к категории жадных алгоритмов.

Структура данных, используемая в алгоритме, — простой массив целых чисел (nodes[]) размера N, где индексы от 0 до N  −  1 сопоставляются элементам множеств, которые могут впоследствии объединяться. Два элемента с индексами p и q будут принадлежать одному множеству, если их значения по индексу совпадают (nodes[p] == nodes[q]). Значением может быть любой элемент множества, поэтому его еще называют представителем множества.

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

Конструктор выглядит следующим образом:

    public class QuickFind implements UnionFind {
        private int[] nodes;
 
        public QuickFind(int N) {
            nodes = new int[N];
            for (int i = 0; i < N; i++) {
                nodes[i] = i;
            }
        }
 
        public void union(int p, int q) { ... }
 
        public boolean connected(int p, int q) { ... }
     }

Возьмем для примера N = 10:

Вначале каждый элемент представляет собой синглтон

Чтобы выполнить операцию union, необходимо пройтись по всему массиву и заменить представителя одного множества представителем другого, объединив таким образом элементы двух множеств.

Алгоритм Quick-find

Теперь для того, чтобы определить, принадлежат ли два выбранных элемента одному множеству, достаточно сравнить значения по индексу: nodes[p] == nodes[q].

Ниже приведена реализация union и connected:

    public void union(int p, int q) {
        int pNode = nodes[p];
        int qNode = nodes[q];
        for (int i = 0; i < nodes.length; i++) {
            if (nodes[i] == qNode) {
                nodes[i] = pNode;
            }
        }
    }
 
    public boolean connected(int p, int q) {
        return nodes[p] == nodes[q];
    }

Оценка сложности Quick-ﬁnd

Очевидно, что поиск связи между элементами (операция connected) осуществляется за константное время: O(1).

Однако при объединении множеств нам придется пройти весь массив. В таком случае для N элементов операция union имеет линейную сложность: O(N).

Предположим, что для решения определенной задачи нам нужно построить систему непересекающихся множеств для N элементов и вызвать операцию union для каждого отдельного элемента. В этом случае сложность инициализации будет квадратичной: O(N²).

Алгоритмы с квадратичной сложностью редко находят применение на практике. Уже при N = 10⁹ поиск решения занимает часы, а при N = 10¹² — годы.

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

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

В предыдущей реализации мы представляли каждый элемент в качестве индекса i в массиве, а его принадлежность конкретному множеству — в качестве значения по индексу nodes[i]. У такого подхода есть недостаток: необходимо проходить массив каждый раз при объединении множеств.

Теперь мы будем хранить представителя множества в качестве корня дерева, а остальные элементы множества — в качестве узлов под ним.

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

Каждый элемент представляется в виде индекса массива nodes[] длины N.
Родитель элемента i — это nodes[i].
Корень i находится последовательной индексацией элемента: nodes[nodes[...nodes[i]...]] (пока nodes[i] ≠ i).

Операция union выполняется следующим образом: nodes[root(q)] = root(p). Визуально это можно представить, как будто корень элемента q подвязывается к корню элемента p.

Представление связей в виде дерева

Код алгоритма прост и лаконичен. Ниже приведена реализация root, union и connected.

    public void union(int p, int q) {
        int pRoot = root(p);
        int qRoot = root(q);
        nodes[qRoot] = pRoot;
    }
 
    public boolean connected(int p, int q) {
        return root(p) == root(q);
    }
 
    private int root(int p) {
        while (p != nodes[p]) {
            p = nodes[p];
        }
        return p;
    }

Оценка реализации Quick-union

Не стоит забывать, что обозначение O(f(N)) показывает верхнюю оценку сложности, то есть мы всегда рассматриваем худший по времени вариант выполнения алгоритма.

В указанной выше реализации мы не учитываем высоту дерева при подвязывании очередного элемента, а это значит, что теоретически дерево может иметь высоту N, то есть элементы могут образовать длинную цепочку, и поиск корня дерева будет занимать много времени. Поэтому верхняя оценка сложности операций union и connected — O(N).

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

Взвешенные деревья

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

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

Объединение деревьев с учетом их размера

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

Возможна ли ситуация, когда дерево с меньшим размером (количеством элементов) будет выше дерева с большим размером?

Оказывается, что при таком подходе высота самого высокого дерева будет не более log(N), или, другими словами, ранг любого узла дерева не превышает log(N). Рангом узла будем называть расстояние (число ребер) от данного узла до корня дерева.

Итак, введем новую эвристику:

Структура данных такая же, как и в алгоритме Quick-union.
Вводится дополнительный массив sz[] для подсчета количества элементов дерева с корнем i.

Код операций root и connected остается прежним, меняется только union:

    public void union(int p, int q) {
        int pRoot = root(p);
        int qRoot = root(q);
 
        if (pRoot == qRoot)
            return;
 
        if (sz[pRoot] < sz[qRoot]) {
            nodes[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        } else {
            nodes[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }

Изменений в коде немного, однако скорость работы алгоритма существенно возросла. Этот факт будет несложно доказать.

Доказательство сложности log(N)

Утверждение. Ранг любого узла x не превышает log(N), где N — количество узлов.

Доказательство. Рассмотрим, при каких условиях ранг x возрастает.

Ранг x после слияния увеличивается на 1

Слияние двух деревьев всегда происходит за счет подвязывания корня меньшего дерева к корню большего. Это означает, что ранг любого элемента x, принадлежащего дереву T1, после слияния с деревом T2 всегда увеличивается на 1, при этом |T2| ≥ |T1|. В результате слияния получим дерево с мощностью |T2| + |T1|.

В крайнем случае, когда |T2| = |T1|, мощность результирующего дерева после слияния увеличится вдвое. Другими словами, ранг x увеличивается на 1, когда количество элементов дерева растет не более чем вдвое. А это значит, что ранг x не превышает log(N).

Сжатие путей

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

Оптимизация может быть применена во время вычисления root. После того как мы нашли корень элемента p, мы можем сразу же подвязать узел к своему корню.

Сжатие путей

Код connected и union остается прежним. В реализации root мы добавляем всего одну строчку.

    private int root(int p) {
        while (p != nodes[p]) {
            nodes[p] = nodes[nodes[p]];
            p = nodes[p];
        }
        return p;
    }

Обратите внимание на строчку 3: мы поднимаем узел на уровень выше на каждой итерации цикла.

Финальная оценка сложности

Сложность операции union после применения сжатия путей ограничивается функцией итерированного логарифма — O(log*(N)).

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

Функция итерированного логарифма возрастает неограниченно, но чрезвычайно медленно. Для всех мыслимых на практике аргументов ее можно было бы заменить константой, но для формул, определенных на всей числовой оси, такая запись будет ошибочной. Значения двоичного итерированного логарифма для всех практически интересных аргументов не превосходят 5 и приведены ниже:

n	*log^(n)**
(—∞, 1]	0
(1, 2]	1
(2, 4]	2
(4, 16]	3
(16, 65536]	4
(65536, 2⁶⁵⁵³⁶]	5

Это означает, что для объема данных, встречающегося на практике, операция union выполняется за константное время, и это было достигнуто всего одной строчкой кода!

Подытожим сложности всех операций для каждого алгоритма:

	initialization	union	connected
Quick-ﬁnd	N	N	1
Quick-union	N	N	N
Weighted QU	N	log(N)	log(N)
Weighted QU + path compression	N	log*(N)	log*(N)

Применение

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

Примером использования в физике является исследование теории перколяции. Звучит угрожающе, однако, по моему мнению, это очень наглядное и изящное применение данного алгоритма.

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

Сколько надо добавить медных опилок в ящик с песком, чтобы смесь начала проводить ток?

Смоделируем задачу в 2D для простоты вычислений и реализации:

Представим материал в виде решетки N на N.
Каждая ячейка может быть открыта с вероятностью p или закрыта с вероятностью 1 − p. Ток, соответственно, может проходить только через открытые ячейки.
Протекание возникает тогда и только тогда, когда верх и низ решетки соединены открытыми ячейками.

Закрытые ячейки помечены черным цветом, открытые — белым, ток — синим

Обозначим открытую ячейку s₀, а закрытую — s₃. Тогда соотношение открытых ячеек к закрытым и есть вероятность p = s₀ / s₃.

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

Очевидно, что при p = 1 ток будет протекать с вероятностью 100%, а при p = 0 — не будет. Однако нам необходимо определить более точное значение p, при котором решетка начинает проводить ток.

Самое интересное, что данная задача не решается математически. Определить приблизительное значение p, при котором ток будет просачиваться с вероятностью p* > 1/2, можно лишь эмпирическим путем.

Число p также называют порогом протекания, минимальной концентрацией элементов перколяционного кластера (в нашем случае — s₀), при которой возникает протекание.

При каком p решетка начнет проводить ток

На рисунке показано, что вероятности p = 0,4 недостаточно для возникновения перколяции, а при p = 0,7 можно уверенно сказать, что ток будет протекать через решетку. Сомнения возникают при p = 0,6, когда не всегда можно дать положительный ответ.

Реализация Percolation

Рассмотрим, как можно представить нашу задачу в виде системы непересекающихся множеств:

Решетку N на N можно представить в виде массива размерности N².
Обозначим закрытую ячейку как 0, а открытую — 1. Изначально все ячейки закрыты.
Последовательно открываем случайные ячейки.
Если соседняя ячейка (сверху, снизу, справа или слева) также открыта, выполняем операцию union с каждой из них.
Повторяем шаги 3–4, пока любая верхняя ячейка не будет связана с любой нижней. Проверка осуществляется с помощью знакомой нам операции connected.

Представление решетки N на N в виде массива элементов N²

Как видите, алгоритм предельно прост, однако шаг 5-й достаточно ресурсоемкий. Нам придется выполнять connected последовательно для каждой верхней ячейки с каждой нижней, то есть сложность этих вычислений составит O(N²).

Чтобы упростить последний шаг, можно пойти на небольшую хитрость. Мы введем 2 виртуальных элемента, pTop и pBottom, и свяжем их с верхней и нижней строкой соответственно. Тогда на 5-м шаге мы будем просто проверять connected(pTop, pBottom).

Виртуальные элементы pTop и pBottom

Вычисление порога протекания

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

Традиционно для изучения случайных процессов воспользуемся методом Монте-Карло:

Инициализируем решетку N на N закрытыми ячейками.
Выбираем случайную ячейку и открываем ее.
Повторяем шаг 2-й, пока решетка не будет в состоянии перколяции.
Вычисляем порог протекания как отношение открытых ячеек к закрытым: p = s₃ / s₀.
Повторяем шаги 1–4-й T раз.

Точность результата зависит от размера решетки N и количества экспериментов T. В конце значения порогов усредняются и вычисляется среднеквадратичное отклонение. Пусть, xt — значение порога протекания в эксперименте t, тогда среднее значение x и среднеквадратичное отклонение s² определяются так:

В результате получаем заветное число — 0,593. Это означает, что концентрация медных опилок в ящике с песком должна превышать 50%, чтобы смесь была токопроводящей.

График вероятности перколяции

Выводы

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

Верхняя граница сложности O(f(N)) отвечает на вопрос, с какой скоростью растет число операций алгоритма при увеличении N. То есть, к примеру, если мы удвоим количество элементов в алгоритме Quick-ﬁnd, то объем работы для операции union также удвоится.

Позднее мы доказали, что сложность union можно свести к O(log*(N)), а это означает, что при любых объемах данных, применяемых на практике, операция union будет выполняться одинаковое время.

Безусловно, для важных научных исследований можно воспользоваться мощностью суперкомпьютера, производительность которого измеряется экзафлопсами (10¹⁸). Однако, если посчитать, это всего на 6 порядков выше производительности домашнего ПК (10¹²). Когда мы имеем дело с алгоритмом квадратичной сложности, суперкомпьютер обеспечит прирост объема входных данных всего в 1000 раз, чего может быть недостаточно для решения поставленной задачи за допустимое время.

Поэтому так важно правильно оценить сложность алгоритма и на основании полученной оценки выбрать самую оптимальную реализацию.

Благодарность

Выражаю благодарность профессору Принстонского университета Роберту Седжвику и доктору технических наук Кевину Уэйну за составление исчерпывающего курса по алгоритмам «Algorithms, Part I, II» на сайте coursera.org. Также в свободном доступе можно найти их книгу Algorithms, 4th Edition.

Источники

Sedgewick, Robert; Wayne, Kevin (2011). Algorithms. 4th ed. Addison-Wesley Professional. ISBN 978-0-321-57351-3.
Sedgewick, Robert (2012). Union Find. Coursera.
Disjoint-set data structure (2019) in Wikipedia: The Free Encyclopedia, Wikimedia Foundation Inc.