Алгоритм пошуку найменшого за потужністю покриття кінцевого безлічі його підмножинами

Розбираючи старі папери наткнувся на неабияк пошарпану зошит, в якій виявив начерки алгоритму пошуку покриття. Автор алгоритму Віктор Анатолійович Щербанів — мій учитель, під керівництвом якого я працював в дев'яності роки минулого сторіччя. Моє скромне участь в основному полягало в тому, що я пропонував у більшості випадків невірні (а часом і просто маячні) варіанти. Що загалом-то не завадило Шефу (так ми його називали між собою) таки довести роботу над алгоритмом до логічного завершення. Десь у двохтисячних роках алгоритм був опублікований в одному з інститутських видань Томська. Але думаю, що не зайвим буде згадати його ще раз. Власне в пам'ять про шефа я і вирішив написати цей пост. Може бути алгоритм здасться комусь цікавим чи підштовхне на якісь нові ідеї з реалізації алгоритму.
 
 
Сам алгоритм грунтується на двох твердженнях і двох теоремах, докази яких тут не наводяться, через їх досить великого обсягу.
 
 Для початку визначимося з тим, що ми, власне, шукаємо.
 
Нехай задано кінцеве безліч imageі сімейство його підмножин .
Знайти підродина (якщо воно існує) таке, що і потужність підродини S * (покриття множини V) найменша з усіх можливих.
 
 Наступні твердження визначають поняття мінімального і найменшого покриття.
 
 Затвердження 1.
Для того щоб підродина , було покриттям безлічі image, необхідно і достатньо, щоб виконувалася умова
 
 
Покриття S 'називається мінімальним, якщо не існує покриття S'' такого, що .
Покриття S * називається найменшим, якщо для будь-якого мінімального покриття S 'виконується умова
 
 
 Твердження 2.
Покриття мінімально тоді і тільки тоді, коли для будь-якого , виконується умова
 
 
 

 
 І, саме основне.
 
Нехай задано кінцеве безліч imageі сімейство його підмножин .
Побудуємо повний навантажений граф , в якому безлічі вершин графа взаємно однозначно співставлено сімейство підмножин ,
а кожному ребру — підмножина .
 
Позначимо безліч всіх ребер інцидентних вершині , а — безліч всіх вершин, інцидентних ребрах з безлічі .
 
 Теорема 1.
Мінімальна за потужністю підмножина ребер, інцидентних довільній вершині в графі G, при виконанні умов
 
визначає мінімальне покриття , однозначно відповідне безлічі вершин, якщо , або безлічі вершин, якщо .
 
 Теорема 2.
Мінімальна за потужністю підмножина ребер, інцидентних довільній вершині ребра в графі G, при виконанні умов
 
 для всіх
визначає найменшу покриття , однозначно відповідне безлічі вершин, якщо , або безлічі вершин, якщо .
 
 

 На підставі теорем пропонується наступний алгоритм пошуку найменшого покриття.
 
1. Безлічі imageі сімейства його підмножин , зіставити сімейство підмножин . Якщо для деякого виявиться , то існує тривіальне покриття . Кінець алгоритму.
Інакше перейти на п.2.
 
2. Побудувати повний навантажений граф , де .
Вершину навантажити безліччю
Ребро навантажити безліччю .
 
3. Перевірити існування покриття: для довільної вершини визначити підмножина
  ,
де — безліч ребер, інцидентних вершині в графі .
Якщо , то покриття не існує. Кінець алгоритму.
Якщо , то покриття існує. Перейти до процедури пошуку найменшого покриття (п. 4).
 
4. Покласти t: = 0.
5. У повному навантаженому графі знайти ребро для якого виконується умова .
Якщо , то перейти на п. 6,
інакше — на процедуру побудови безлічі D вершин, що визначають найменшу покриття (п. 7).
 
6. Побудувати повний навантажений граф , вважаючи , — безліч ребер, інцидентних вершині в графі .
Покласти для всіх .
Покласти t: = t +1 і перейти на п. 5.
 
7. Початок побудови безлічі D вершин, що визначають найменшу покриття .
Покласти .
 
8. Якщо t = 0, то перейти на п. 11, інакше — покласти t: = t-1.
 
9. У графі визначити підмножина
 
10. Якщо в графі виконується умова , то покласти , інакше — D: = D. Перейти на п. 8.
 
11. Сімейство підмножин визначає найменшу покриття множин .
Кінець алгоритму.
 

 
Спробуємо оцінити складність алгоритму.
Вся, так сказати, суть алгоритму (з точки зору оцінки складності) укладена в фразі «побудуємо повний навантажений граф».
Нам потрібно виконати n дій для обчислення навантаження в n вершинах графа і (n-1) n / 2 обчислень (за кількістю ребер повного графа) для навантаження ребер графа. І все це, якщо розглядати найгірший випадок, коли підмножини взаємно не перетинаються, виконується n-2 рази. Таким чином груба оцінка O (n) = n 3 + n 2 .
 
І на закінчення. Не впевнений, що пост заслуговує инвайта, тому як моя причетність до алгоритму більш ніж сумнівна. Але опублікування, як мені здається, варто. Сподіваюся модератори розберуться.
Як там греки говорили? — Fais se que dois adviegne que peut (роби, що повинно, і будь, що буде).
(Або це були римляни?)

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.