Алгоритми для роботи з множинами
Побудова алгоритмів
Алгоритми для роботи з множинами
У цілого ряду додатків використовується наступна структура даних: елементів розбиті на непусті множини, що не пересікаються.
Система множин, що не пересікаються це набір непустих множин, що не пересікаються, і у кожному із яких зафіксований один із елементів – представник. Точніше, елементи множини є об’єктами і робота з ними здійснюється за допомогою покажчика. При цьому повинні підтримуватись наступні процедури.
«Створити множину» (MakeSet) Процедура створює нову множину, у якій елемент задається за допомогою вказівника . Оскільки множини не повинні пересікатися, вимагається, щоб вказував на новий елемент, що не лежить ні в одному із уже створених множин.
«Знайти множину» (FindSet). Повертає вказівник на представника множини, що вміщує елемент, на який вказує .
«Об’єднання» (Union). Процедура тоді може бути застосована, якщо елементи і належать до двох різних множин і , і замінюють ці дві множини на одну ; при цьому вибирається деякий представник для елементу множини . Самі множини і вилучаються.
У певних випадках вибір представника повинен підкорятись деяким правилам, наприклад, елементи можуть бути упорядковані і представником є найменший елемент множини. У будь-якому випадку суттєвим є те, що вказівник залишається незмінним до тих пір поки сама множина не змінюється.
Приклад 3.1.Алгоритм ConnectedComponents (зв’язані компоненти), що наведений нижче, розбиває множину вершин графа на множини, що не пересікаються, і які відповідають зв’язаним компонентам; після цього за допомогою процедури SameComponent можна вияснити чи знаходяться дві дані вершини в одній компоненті.
Позначимо через і множину вершин і ребер графа .
ConnectedComponents
1 for (для) кожної вершини
2 MakeSet(w)
3 end for
4 for (для) кожного ребра
5 if
6 then Union(v,w)
7 end if
8 end for
SameComponent
1 if
2 then return true
3 else return false
4 end if
Алгоритм ConnectedComponents працює наступним чином (рис. 3.1) Спочатку кожна вершина розглядається як одноелементна підмножина. Потім для кожного ребра графа об’єднуємо підмножини, у які попали кінці цього ребра. Коли всі ребра опрацьовані, множина вершин розбита на зв’язані компоненти.
На рис 3.1,а показаний граф, що складається із чотирьох зв’язаних компонент: , , та . У процесі роботи алгоритму стан системи множин, що не пересікаються послідовно змінюється і на останньому кроці алгоритм формує чотири зв’язані компоненти (рис. 3.1,б).
Найпростіший варіант реалізації системи множин , що не пересікаються, зберігати кожну множину у вигляді окремого списку. Для ідентифікації кожного списку із множини можна використати функцію належності, , , яка відображає елементи множини ідентифікаторів у множину цілих чисел від до (для деяких алгоритмічних мов такі числа приймають значення від 1 до ). Компонентами масиву розміром є вказівники на списки елементів множини . Список, на який вказує , складається із всіх тих елементів , для яких (рис. 3.2).
a)
| Ребро, що опрацьовується | Множини, що не пересікаються | |||||||||
| початок | ||||||||||
б)
Рисунок 3.1 – Процес опрацювання множин вершин графа
Виконуючи операцію об’єднання (Union(x,y)) добавляємо список, що вміщує до кінця списку, що вміщує . Тепер представником нового списку буде його початок, тобто представник списку, що вміщує . При цьому виникає необхідність у правильній установці вказівників на початок списку для всіх колишніх елементів множини, що вміщувала . Час на виконання цієї операції лінійно залежить від розміру вказаної множини.
Рисунок 3.2 – Схема ідентифікації списків за допомогою функції розстановки
Допустимо, що список складається із елементів , , …, . Виконаємо операції MakeSet(xi)для всіх , а потім операцій Union(x1,x2), Union(x2,x3), …,
Union(xn-1,xn). марна вартість операції Union(xі,xі+1) пропорційна , то сумарна вартість виконання операцій буде
.
Використовуючи формулу суми членів арифметичної прогресії , де - перший член прогресії; - різниця прогресії, і враховуючи те, що , і , знайдемо
,
тобто
.
Описаний вище спосіб реалізації процедури Union вимагає порядку операцій. Алгоритм Union можна покращити, якщо до довшого списку долучати коротший. Такий прийом називається ваговою евристикою. Якщо списки, що об’єднуються вміщують приблизно рівну кількість елементів, то великого виграшу не буде, але у протилежному випадку економія може бути відчутною.
Якщо довжина більшого списку , а довжина меншого , то загальне число операцій по об’єднанню двох списків буде .
Приклад 3.2. Нехай задано два списки і , які вміщують певні числові величини. Необхідно їх об’єднати в один, використавши прийом вагової евристики. Алгоритм Union у псевдокоді буде мати такий вигляд:
Union(А,В)
1 n1=length(A) Кількість елементів у списку А
2 n2=length(B) Кількість елементів у списку В
Першим у загальному списку буде довший список
3 n=max(n1,n2)
4 if n1>n2
5 then C=A
6 D=B
7 else C=B
8 D=A
9 end if
10 k=1
11 for i=n+1 to n1+n2
12 C(i)=D(k)
13 k=k+1
14 end for