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-find, буде достатньо визначити наступні операції (тут і далі наводяться приклади коду на мові 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-find

Очевидно, що пошук зв'язку між елементами (операція connected) здійснюється за константна час: O(1).

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

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

Алгоритми квадратичних складністю рідко знаходять застосування на практиці. Вже при N = 109 пошук рішення займає години, а при N = 1012 — роки.

Подання у вигляді дерев

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

У попередньої реалізації ми представляли кожен елемент в якості індексу 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 (s[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, 265536]	5

Це означає, що для обсягу даних, що зустрічаються на практиці, операція union виконується за константна час, і це було досягнуто всього одним рядком коду!

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

	initialization	union	connected
Quick-find	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. Струм, відповідно, може проходити тільки через відкриті осередки.
Перебіг виникає тоді й тільки тоді, коли верх і низ решітки з'єднані відкритими осередками.

Закриті осередки позначені чорним кольором, відкриті — білим, ток — синім

Позначимо відкриту клітинку s0, а закрите — s3. Тоді співвідношення відкритих осередків до закритим і є ймовірність p = s0/s3.

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

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

Найцікавіше, що дана задача не вирішується математично. Визначити приблизне значення p, при якому струм буде просочуватися з імовірністю p* > 1/2, можна лише емпіричним шляхом.

Число p також називають порогом протікання, мінімальною концентрацією елементів перколяційного кластера (в нашому випадку — s0), при якій виникає протікання.

При якому p решітка почне проводити струм

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

Реалізація Percolation

Розглянемо, як можна представити нашу задачу у вигляді системи непересічних множин:

Грати N на N можна представити у вигляді масиву розмірності N2.
Позначимо закриту клітинку як 0, а відкриту — 1. Спочатку всі комірки закриті.
Послідовно відкриваємо випадкові осередку.
Якщо сусідня комірка (зверху, знизу, праворуч або ліворуч) також відкрита, виконуємо операцію union з кожною з них.
Повторюємо кроки 3-4, поки будь-верхня клітинка не буде пов'язана з будь-нижній. Перевірка здійснюється з допомогою знайомої нам операції connected.

Подання решітки N на N у вигляді масиву елементів N2

Як бачите, алгоритм дуже простий, проте крок 5-й досить ресурсомісткий. Нам доведеться виконувати connected послідовно для кожної верхньої комірки з кожної нижньої, тобто складність цих обчислень складе O(N2).

Щоб спростити останній крок, можна піти на невелику хитрість. Ми введемо 2 віртуальних елемента, pTop і pBottom, і зв'яжемо їх з верхньої і нижньої рядком відповідно. Тоді на 5-му кроці ми просто будемо перевіряти connected(pTop, pBottom).

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

Обчислення порогу протікання

Тепер у нас все готово для проведення експериментів. Як говорилося раніше, нам необхідно визначити мінімальну кількість відкритих осередків, при якому відбувається перколяция, так званий поріг протікання. Обчислити його можливо лише емпірично і на великій вибірці.

Традиційно для вивчення випадкових процесів скористаємося методом Монте-Карло :

Ініціалізуємо ґрати N на N закритими комірками.
Вибираємо випадкову клітинку і відкриваємо її.
Повторюємо крок 2-й, поки грати не буде в змозі перколяції.
Обчислюємо поріг протікання як відношення відкритих осередків до закритим: p = s3/s0.
Повторюємо кроки 1-4-ї T разів.

Точність результату залежить від розміру решітки N і кількості експериментів T. наприкінці значення порогів усереднюються і обчислюється середньоквадратичне відхилення. Нехай, xt — значення порогу протікання в експерименті t, тоді середнє значення x і середньоквадратичне відхилення s2 визначаються так:

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

Графік ймовірності перколяції

Висновки

Отже, ми побачили, як додавання простих евристик і пари рядків коду докорінно змінюють швидкість обчислень. Цей факт ми довели за допомогою функції обчислювальної складності, яка встановлює залежність обсягу обчислень від розміру вхідних даних.

Верхня межа складності O(f(N)) відповідає на питання, з якою швидкістю зростає кількість операцій алгоритму при збільшенні N. тобто, наприклад, якщо ми подвоїмо кількість елементів в алгоритмі Quick-find, то обсяг роботи для операції union також подвоїться.

Пізніше ми довели, що складність union можна звести до O(log*(N)), а це означає, що при будь-яких обсягах даних, що застосовуються на практиці, операція union буде виконуватися однаковий час.

Безумовно, для важливих наукових досліджень можна скористатися потужністю суперкомп'ютера, продуктивність якого вимірюється экзафлопсами (1018). Проте, якщо порахувати, це всього на 6 порядків вище продуктивності домашнього ПК (1012). Коли ми маємо справу з алгоритмом квадратичних складності, суперкомп'ютер забезпечить приріст обсягу вхідних даних всього в 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.

Опубліковано: 13/11/19 @ 11:00
Розділ Різне

SEO Блог