Алгоритм поиска Union решает огромную вычислительную проблему. Как мы можем эффективно определить, связаны ли два элемента в системе с множеством элементов, где элементы соединены путем прохождения через другие элементы?
Это обычно называется проблемой динамического подключения. Алгоритм грубой силы работает для системы с небольшим количеством элементов.
//brute force quick find
class QuickFindUF {
// construct an array with N integer elements
constructor (N) {
this.id = []
for (var i = 0; i < N; i++) {
this.id[i] = i;
}
}
// Connections between elements are tracked in the ID array.
// To check if two elements are connected, we check for an ID match
connected = (p, q) => {
return this.id[p] === this.id[q];
}
// To create a new connection between two elements P and Q, we change the id of element P to the id of element Q.
// We also change all the elements that were previously connected to P to the new id.
union = (p, q) => {
var pid = this.id[p]
var qid = this.id[q]
for (var i = 0; i < id.length; i++) {
if (this.id[i] === pid) { this.id[i] = qid }
}
}
}
Алгоритм грубой силы работает, присваивая двум связанным элементам один и тот же идентификатор. Вы можете проверить, связаны ли два элемента, проверив, что у них есть совпадающий идентификатор.
Проблема с этой реализацией заключается в том, что всякий раз, когда вы создаете новое соединение между двумя элементами, вы должны перебирать весь массив id в поисках элементов, которые ранее были связаны с элементом, идентификатор которого вы меняете.
Например, если мы соединяем 2 и 3, мы также должны подключить 3 к каждому элементу, ранее связанному с 2. Единственный способ добиться этого - перебрать весь массив.
Итерация по всему массиву будет иметь временную сложность 0 (n), что неэффективно для больших систем.
К счастью, есть элегантное решение для повышения эффективности алгоритма. Вместо того, чтобы перебирать весь массив для создания нового соединения, мы будем поддерживать дерево соединений с одним корневым элементом:
Вместо того, чтобы назначать соединенным элементам один и тот же идентификатор, мы назначим им родительский элемент. Чтобы найти корень элемента, мы можем проследить за родителями вверх по дереву, пока не дойдем до элемента, родителем которого является он сам. Это корень. Вот как выглядит алгоритм findRoot:
findRoot = (currentEl) => {
while (currentEl != id[currentEl]) {
currentEl = id[currentEl]
}
return currentEl;
}
Этот алгоритм создает цикл while. На каждой итерации цикла текущий элемент переназначается его родительскому элементу. Когда текущий элемент равен своему родительскому, это означает, что мы попадаем в корневой элемент, поэтому мы возвращаем этот элемент.
Прекрасная особенность этой реализации заключается в том, что она значительно повышает эффективность создания нового соединения между двумя элементами. Вместо того, чтобы переназначать идентификатор каждого элемента, который мы ранее подключили, нам нужно изменить только один элемент - корень подключаемого меньшего дерева. Поскольку все элементы уже подключены к своему корню, изменение корня подключит все эти элементы к целевому дереву.
Вот как выглядит новый алгоритм объединения:
union = (elementA, elementB) => {
var rootA = this.findRoot(elementA)
var rootB = this.findRoot(elementB)
if (rootA === rootB) {return}
// connect root of smaller tree to root of larger tree
if (size[rootA] < size[rootB]) {
id[rootA] = rootB
size[rootB] += size[rootA]
} else {
id[rootB] = rootA
size[rootA] += size[rootB]
}
this.treeCount--
}
Теперь мы увеличили эффективность алгоритма объединения с 0 (n) до 0 (log2 (n)), потому что глубина дерева никогда не будет превышать log из n элементов. Это означает, что по мере увеличения размера набора данных время, необходимое для завершения алгоритма объединения, не увеличивается намного. Мы можем соединить деревья, содержащие миллиарды элементов, за считанные секунды.
Мы можем улучшить алгоритм еще больше, сжимая деревья всякий раз, когда мы создаем новое объединение. Поскольку алгоритм следует по пути к корневому элементу, мы будем переназначать родителей элементов их бабушкам и дедушкам по мере прохождения, тем самым уменьшая глубину дерева. Для этого требуется всего одна дополнительная строка кода:
findRoot = (currentEl) => {
while (currentEl != id[currentEl]) {
// as we follow a tree to its root, reassign elements parents to their grandparents
id[currentEl] = id[id[currentEl]];
currentEl = id[currentEl];
}
return currentEl
}
Вот полная реализация js, частично взятая из JS-визуализации перколяции Майкла Тота с помощью union find. Я добавил сжатие, которое Майкл не реализовал. Я также изменил название, чтобы его было легче читать.
//N is the initial number of elements in the system, before any connections are made.
function WeightedUnionFind(N) {
// Constructor
var id = [];
var size = [];
for (var i = 0; i < N; i++) {
id[i] = i; // id[i] = parent of i
size[i] = 1; // size[i] = number of objects in subtree with root i
}
// Returns the number of components, which initializes at N
this.treeCount = N;
// Returns the component id for the containing site
this.findRoot = function(currentEl) {
while (currentEl != id[currentEl]) {
// compression
id[currentEl] = id[id[currentEl]]
currentEl = id[currentEl];
}
return currentEl;
}
// Returns true if two elements are part of the same component
this.connected = function(elementA, elementB) {
return this.find(elementA) === this.find(elementB);
}
// Connects the components of two elements
this.union = function(elementA, elementB) {
var rootA = this.find(elementA);
var rootB = this.find(elementB);
if (rootA === rootB) { return; }
// make smaller tree point to larger one
if (size[rootA] < size[rootB]) {
id[rootA] = rootB; size[rootB] += size[rootA];
} else {
id[rootB] = rootA; size[rootA] += size[rootB];
}
this.treeCount--;
}
}
Наслаждайтесь и ознакомьтесь с курсом бесплатных алгоритмов Coursera, который подробно описывает алгоритм поиска объединения в первом разделе!
