Лекция 7_2 непересекающиеся подмножества.ppt

и анализ алгоритмов

- множество множеств Wi узлов (множество деревьев остовного леса)
**********************************************************************************************
if (u

и v принадлежат разным подмнож.W1 и W2 из Vs )
{ Заменить W1 и W2 на W1 ∪ W2 в Vs;
T := T ∪ {e};
}
**********************************************************************************************
Сначала Vs = { {v1}, {v2}, …, {vn} }. В конце Vs = { {v1,v2, …,vn}}.
Используются только операции:
Найти подмножество W1, такое, что u ∈ W1,
Найти подмножество W2, такое, что v ∈ W2,
Объединить W1 и W2 (получить W1 ∪ W2 )

массив элементов, тогда:
Поиск W1 и W2, таких, что для ребра

{u, v} имеем u ∈ W1 и v ∈ W2 → O(n)
Объединение массивов – O(n1+n2).

Т.о. вся обработка ребер из очереди с приоритетами
даст O(m*n), что хуже, чем O( m * log m )
и при m =O(n), и при m =O(n2),
т.к. O( m * log m ) = O( m * log n2 ) = O( m * log n )

Операции с непересекающимися подмножествами

объединение»
Пример из лекции 5. Задача о связности графа (об остовном

дереве)

for (i = 1; i <= n; i++) w[i] = i; // w[i] – метка дерева
while (cin >> p>> q)
{
i = w[p]; j = w[q];
if (i != j)
{ cout << p <<‘ ‘<< q<< endl;
w[p] = j;
for (k = 1; k <= n; k++)
if (w[k] == i) w[k] = j;
}
}

Поиск: O(1)
Объединение: O(n)

– быстрое объединение
17.03.2014
Алгоритмы на графах Начало
int i,

j, p, q, w[N];
for (i = 0; i < N; i++) w[i] = i;
while (fin >> p >> q){
for (i = p; i != w[i]; i = w[i]) ; // i == w[i]
for (j = q; j != w[j]; j = w[j]) ; // j == w[j]
if (i == j) continue;
w[i] = j;
cout << "+ребро: " << p << " " << q << endl;
}

int i, j, p, q, w[N];
for (i = 0; i < N; i++) w[i] = i;
while (fin >> p >> q){
for (i = p; i != w[i]; i = w[i]) ; // i == w[i]
for (j = q; j != w[j]; j = w[j]) ; // j == w[j]
if (i == j) continue;
w[i] = j;
cout << "+ребро: " << p << " " << q << endl;
}

Обобщение этой идеи см. далее

g, h, i, j, k }
Подмножества:
{ a, b, c },

{ d, e }, { f, g, h, i, j }, { k }
Имя (по «представителю») подмножества:
{ a , b, c }, { d, e }, { f, g, h, i, j }, { k }
Пусть x - элемент, тогда
Make ( x ) → { val ( x ) } и x - представитель
Find ( x ) → имя (представитель)
Например, при x = ‘k’: Make ( x ) = { k },
при x = ‘g’: Find ( x ) = h

Операции с непересекающимися подмножествами

Union (x, y) - порождает новое подмножество (объединение) с именем

x или y.
Например, при x = a, y = d
Union (x, y) дает { a , b, c } U { d, e } в виде
{ a , b, c, d, e } или { a , b, c, d, e } .
Например, объединить множество, содержащее u, с множеством, содержащим v:
x = Find(u);
y = Find(v);
if x ≠ y then Union (x, y)
Какая СД для представления подмножеств эффективна?

Операции с непересекающимися подмножествами

k – суммарное число операций Make, Find и Union.
k ≥

n,
число операций Union ≤ n – 1 (попарно ⎡log2 n⎤)

Операции с непересекающимися подмножествами

Реализация 1
Линейные списки

Абстрактная реализация (ссылки на представителя). Пример Union

что в худшем случае O(n2).
Пример. Пусть Union (x, y) -

порождает новое подмножество с именем y.
for (i =1; i≤n; i++) Make ( x(i) );
for (i =1; i < n; i++) Union ( x(i), x(i+1) );

Реализация 1. Линейные списки

i

i -1

2

1

i + 1

Суммарная стоимость n + Σi=1..n-1 i = Θ(n2)

короткий список добавляется к более длинному (ссылки на представителя изменяются

в коротком списке).
Утверждение.
Пусть система непересекающихся подмножеств сначала пуста. Далее k – суммарное число операций Make, Find и Union, а n – число операций Make.
Тогда суммарная сложность есть O(k + n log2 n)

Реализация 1. Линейные списки
Весовая эвристика

обновления размера – O(1)
2) Какова стоимость обновления указателей на представителя?

Зафиксируем какой-либо элемент x. Указатель от x к представителю изменяется, если только x входит в меньшее из объединяющихся подмножеств (в силу эвристики). При этом размер объединения не менее, чем вдвое превышает размер множества, включавшего x.
Т.о. x участвует не более чем в ⎡log2 n⎤ «результативных» объединениях.
Суммарно по всем элементам – не более O(n log2 n) изменений указателей.
В итоге общая стоимость есть O(k + n log2 n) . В жадном алгоритме O(2m + (n-1) + n log2 n) = O(m + n log2 n)

Реализация 1. Линейные списки. Весовая эвристика

с внутрисписковыми указателями не нужна. Важна лишь работа с указателями

на представителя!

Реализация 1. Линейные списки

Ср. не оч. быстрый поиск – быстрое объединение
(лекция 5)

} U { f, e, g } = { f,

e, g, c, a, b, d }
Union → O(1). Find(x) → O(n) (!!!).

Union

узла х – высота поддерева с корнем x (точнее –

верхняя оценка высоты…)
Make (x) → r(x) = 0
Find (x) не меняет рангов (!)
При Union (x, y) – дерево с меньшим рангом «подвешивается» к корню дерева с не меньшим рангом, при этом ранг нового корня изменяется (увеличивается на 1) только при равенстве рангов объединяемых подмножеств (деревьев леса)

Реализация 2. Лес непересекающихся подмножеств

( x(i) );
for (i =1; i < n; i++) Union

( x(i), x(i+1) );

Всего O(n). Здесь: Find ~ O(1)

!!! Ср. с предыдущим слайдом (отличие при Union с равными рангами). Здесь корнем будет первый аргумент.

2
n/23 восьмерок. r = 3

2k элементов,
а ранг r = k.
Пусть n =

2q. Тогда на q-ом шаге получим одно дерево из n элементов.
Вопросы:
Сколько тратится на операцию Find (в худшем случае)?
Сколько всего действий (в худшем случае)?

Сценарий 2 (продолжение)

от x к корню устанавливаются на корень.
Реализация 2. Лес непересекающихся

подмножеств

Find ( a )

отца, r(x) – ранг узла
Реализация 2. Лес непересекающихся подмножеств
(псевдокод)
Proc

Make (x);
{создан узел со ссылкой x}
begin
p(x) := x;
r(x) := 0
end {Make}

Proc Union (x, y);
begin
Link ( Find (x), Find (y) )
end {Union}
{Link – объединение по
рангам, см. далее}

по рангам}
begin
if r(x) < r(y) then p(x) := y
else

begin
p(y) := x;
if r(x) = r(y) then r(x) := r(x) +1
end
end {Link}

путей}
begin
if p(x) ≠ x then p(x) := Find (p(x));
Return (p(x))
end

{Find}

Без доказательства:
Только объединение по рангу → O ( k log n)
+ сжатие путей → O ( k α(k, n) ), где α(k, n) ≤ 4 (практически)

ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ