Алгоритм поиска наименьшего по мощности покрытия конечного множества его подмножествами
Разбирая старые бумаги наткнулся на изрядно потрёпанную тетрадь, в которой обнаружил наброски алгоритма поиска покрытия. Автор алгоритма Виктор Анатольевич Щербанов — мой учитель, под руководством которого я работал в девяностые годы прошлого столетия. Моё скромное участие в основном заключалось в том, что я предлагал в большинстве случаев неверные (а порой и просто бредовые) варианты. Что в общем-то не помешало Шефу (так мы его называли между собой) таки довести работу над алгоритмом до логического завершения. Где-то в двухтысячных годах алгоритм был опубликован в одном из институтских изданий Томска. Но думаю, что не лишним будет вспомнить его ещё раз. Собственно в память о Шефе я и решил написать этот пост. Может быть алгоритм покажется кому-то интересным или подтолкнёт на какие-то новые идеи по реализации алгоритма.
Сам алгоритм зиждется на двух утверждениях и двух теоремах, доказательства которых здесь не приводятся, из-за их довольно большого объёма.
Для начала определимся с тем, что мы, собственно, ищем.
Пусть задано конечное множество
Найти подсемейство
Следующие утверждения определяют понятия минимального и наименьшего покрытия.
Утверждение 1.
Для того чтобы подсемейство
Покрытие S' называется минимальным, если не существует покрытия S'' такого, что
Покрытие S* называется наименьшим, если для любого минимального покрытия S' выполняется условие
Утверждение 2.
Покрытие
И, самое основное.
Пусть задано конечное множество
Построим полный нагруженный граф
а каждому ребру
Обозначим
Теорема 1.
Минимальное по мощности подмножество
определяет минимальное покрытие
Теорема 2.
Минимальное по мощности подмножество
определяет наименьшее покрытие
На основании теорем предлагается следующий алгоритм поиска наименьшего покрытия.
1. Множеству
Иначе перейти на п.2.
2. Построить полный нагруженный граф
Вершину
Ребро
3. Проверить существование покрытия: для произвольной вершины
где
Если
Если
4. Положить t:=0.
5. В полном нагруженном графе
Если
иначе — на процедуру построения множества D вершин, определяющих наименьшее покрытие
6. Построить полный нагруженный граф
Положить
Положить t:=t+1 и перейти на п. 5.
7. Начало построения множества D вершин, определяющих наименьшее покрытие
Положить
8. Если t=0, то перейти на п. 11, иначе — положить t:=t-1.
9. В графе
10. Если в графе
11. Семейство
Конец алгоритма.
Попробуем оценить сложность алгоритма.
Вся, так сказать, суть алгоритма (с точки зрения оценки сложности) заключена в фразе «построим полный нагруженный граф».
Нам требуется выполнить n действий для вычисления нагрузки в n вершинах графа и (n-1)n/2 вычислений (по количеству рёбер полного графа) для нагрузки рёбер графа. И всё это, если рассматривать наихудший случай, когда подмножества взаимно не пересекаются, выполняется n-2 раза. Таким образом грубая оценка O(n) = n3 + n2.
И в заключение. Не уверен, что пост заслуживает инвайта, потому как моя причастность к алгоритму более чем сомнительная. Но опубликования, как мне кажется, стоит. Надеюсь модераторы разберутся.
Как там греки говорили? — Fais se que dois adviegne que peut (делай, что должно, и будь, что будет).
(или это были римляне?)