Разбирая старые бумаги, я наткнулся на изрядно потрепанный блокнот, в котором нашел наброски алгоритма поиска покрытия.
Автор алгоритма Щербанов Виктор Анатольевич — мой учитель, под руководством которого я работал в девяностые годы прошлого века.
Моё скромное участие главным образом заключалось в том, что я предлагал в большинстве случаев неверные (а иногда и просто бредовые) варианты.
Что, в общем-то, не помешало Шефу (как мы его между собой называли) довести работу над алгоритмом до логического завершения.
Где-то в 2000-х алгоритм был опубликован в одном из институтских изданий в Томске.
Но думаю, не помешало бы вспомнить об этом еще раз.
Собственно, в память о Шефе я и решил написать этот пост. Возможно, кому-то алгоритм покажется интересным или подскажет новые идеи реализации алгоритма.
Сам алгоритм основан на двух утверждениях и двух теоремах, доказательства которых здесь не приводятся из-за их достаточно большого объема.
Для начала давайте определимся, что мы на самом деле ищем.
Пусть дано конечное множество 
и семья 
его подмножества 
.
Найти подсемейство 
(если он существует) такой, что 
и мощность подсемейства S* (охватывающего множество V) наименьшая из всех возможных.
Следующие утверждения определяют концепции минимального и наименьшего покрытия.
Утверждение 1.
Для того, чтобы подсемейство 
, было обложкой сета
, необходимо и достаточно, чтобы условие выполнялось 
Покрытие S' называется минимальным, если не существует покрытия S'' такого, что 
.
Покрытие S* называется минимальным, если для любого минимального покрытия S' выполнено следующее условие: 
Утверждение 2.
Покрытие
минимальным тогда и только тогда, когда для любого 
, условие выполнено 
И самое важное.
Пусть дано конечное множество
и семья
его подмножества
.
Построим полный загруженный граф 
, в котором много 
семейство вершин графа отображается взаимно однозначно 
подмножества 
,
и к каждому ребру 
- подмножество 
.
Обозначим 
множество всех ребер, инцидентных вершине 
, А 
— множество всех вершин, инцидентных ребрам из множества
.
Теорема 1.
Подмножество минимальной мощности 
ребра, инцидентные произвольной вершине
в столбце G при соблюдении условий 
определяет минимальное покрытие
, однозначно соответствующий множеству 
вершины, если 
или многие 
вершины, если 
.
Теорема 2.
Подмножество минимальной мощности
ребра, инцидентные произвольной вершине
ребра
в столбце G при соблюдении условий 
для всех 
определяет наименьшее покрытие
, однозначно соответствующий множеству
вершины, если
или многие
вершины, если
.
На основе теорем предлагается следующий алгоритм поиска наименьшего покрытия.
1. Для многих
и семья
его подмножества
, сравните семью 
подмножества 
.
Если для некоторых 
оказывается 
, то существует тривиальное накрытие 
.
Конец алгоритма.
В противном случае перейдите к шагу 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. Если в столбце
условие выполнено 
, затем поставь 
, иначе - Д:=Д.
Перейдите к шагу 8.
11. Семья 
подмножества 
определяет наименьшую обложку набора
.
Конец алгоритма.
Попробуем оценить сложность алгоритма.
Вся, так сказать, суть алгоритма (с точки зрения оценки сложности) заключена во фразе «построить полный нагруженный граф».
Нам нужно выполнить n действий для расчета нагрузки на n вершин графа и (n-1)n/2 вычислений (в зависимости от количества ребер полного графа) для загрузки ребер графа.
И все это, если рассматривать худший случай, когда подмножества не пересекаются друг с другом, выполняется n-2 раза.
Таким образом, грубая оценка равна O(n) = n 3 + н 2 .
В заключение.
Не уверен, что пост заслуживает инвайта, поскольку моя причастность к алгоритму более чем сомнительна.
Но мне кажется, что стоит опубликовать.
Надеюсь модераторы разберутся.
Что там говорили греки? - Fais se que dois adviegne que peut (делай то, что должен, и будь что будет).
(или это были римляне?) Теги: #множества #покрытие #граф #Алгоритмы
-
Взломать Самолет - 3
19 Oct, 24 -
Можно Ли Доверять Вебвизору От Яндекса?
19 Oct, 24 -
Bmw Выжигает Рекламу В Глазах Кинозрителей
19 Oct, 24
