Алгоритм поиска наименьшего по мощности покрытия конечного множества его подмножествами

в 9:13, , рубрики: Алгоритмы, граф, покрытие, метки: ,

Разбирая старые бумаги наткнулся на изрядно потрёпанную тетрадь, в которой обнаружил наброски алгоритма поиска покрытия. Автор алгоритма Виктор Анатольевич Щербанов — мой учитель, под руководством которого я работал в девяностые годы прошлого столетия. Моё скромное участие в основном заключалось в том, что я предлагал в большинстве случаев неверные (а порой и просто бредовые) варианты. Что в общем-то не помешало Шефу (так мы его называли между собой) таки довести работу над алгоритмом до логического завершения. Где-то в двухтысячных годах алгоритм был опубликован в одном из институтских изданий Томска. Но думаю, что не лишним будет вспомнить его ещё раз. Собственно в память о Шефе я и решил написать этот пост. Может быть алгоритм покажется кому-то интересным или подтолкнёт на какие-то новые идеи по реализации алгоритма.

Сам алгоритм зиждется на двух утверждениях и двух теоремах, доказательства которых здесь не приводятся, из-за их довольно большого объёма.

Для начала определимся с тем, что мы, собственно, ищем.

Пусть задано конечное множество 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) = n3 + n2.

И в заключение. Не уверен, что пост заслуживает инвайта, потому как моя причастность к алгоритму более чем сомнительная. Но опубликования, как мне кажется, стоит. Надеюсь модераторы разберутся.
Как там греки говорили? — Fais se que dois adviegne que peut (делай, что должно, и будь, что будет).
(или это были римляне?)

Автор: alex103

Источник

Поделиться

  1. Алексей:

    Хотелось бы посмотреть доказательства теорем..

* - обязательные к заполнению поля