Как хранить элементы данных в группах / кластерах по union-find - PullRequest
Новая
       42

Как хранить элементы данных в группах / кластерах по union-find

0 голосов
/ 13 февраля 2019

Я реализовал алгоритм поиска объединения, основанный на этом коде с этим API : 

void unify(int p, int q)
int find(int p)
boolean connected(int p, int q)
int clusterSize(int p)

Затем я обнаруживаю кластеры с помощью вложенного цикла:

for i = (0) to (data size)
    for j = (i+1) to (data size)
        if ( "i" and "j" meet this condition )
            unify(i,j)
    end for
end for

Чтобы фактически сохранить каждый кластер / группу в отдельном array, в настоящее время я перебираю все свои элементы данных и вызываю find следующим образом: 

for i = 0 to data-size
    k = find(i);
    // ... Store data element "i" in cluster "k" (array "k")
end-for

У меня такое ощущение, что последний for loop для хранения элементов данных в разных группах / кластерах может не понадобиться.Интересно, я на правильном пути?

1 Ответ

0 голосов
/ 13 февраля 2019

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

int clusters[data_size];
for(int i = 0; i < data_size; i++)
{
  clusters[i] = i; // each element refers to itself initially, indicating that it's a separate cluster
}

Теперь после проверки во вложенном цикле, какие элементы необходимо кластеризовать, а затем объедините их -

for i = (0) to (data size)
    for j = (i+1) to (data size)
        if ( "i" and "j" meet this condition )
            unify(i,j)
    end for
end for

В методе unify(p, q) то, что вы можете сделать, - 

clusters[find(p)] = find(q); // indicates p belongs to cluster number q

Или наоборот также верно - 

clusters[find(q)] = find(p); // indicates q belongs to cluster number p

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

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

...