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

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


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

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

Пусть задано конечное множество 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 (делай, что должно, и будь, что будет).
(или это были римляне?)
Поделиться публикацией

Комментарии 11

    +3
    Можно привести какой-нибудь пример?
      +6
      … или хотя бы пару картинок… для троечников ;)
        +8
        Есть два замечания. Во-первых, задача о покрытии множествами является NP-полной. Ни одной такой задачи за последние лет 50 не решили, и сомнительно, что решат.

        Во-вторых, я дошел до теоремы 2 и нашел там ошибку. Если в последнем условии пересечение V-шек по E^* не пусто, то соответствующее S^* никак не будет покрытием. Дальше я решил пока не вникать. Мне кажется, что вы ищете решение не среди всего множества решений, а только среди части. Думаю, что в этом основная ошибка.
          +1
          Во-вторых, я дошел до теоремы 2 и нашел там ошибку. Если в последнем условии пересечение V-шек по E^* не пусто, то соответствующее S^* никак не будет покрытием.

          Раз вы не нашли ошибки в Теореме 1, то в соответствии с ней соответствующее S* теоремы 2 обязательно будет покрытием. Более того, оно будет минимальным покрытием. Но не факт, что наименьшим. Этим и занимается теорема 2.

          Мне кажется, что вы ищете решение не среди всего множества решений, а только среди части.

          Вот! Вы тоже это заметили.
          Поскольку я не автор алгоритма, то имею право сомневаться в его правильности.
          У меня стали возникать сомнения, когда я попытался при подготовке статьи реализовать алгоритм в коде.
          В настоящее время пытаюсь материализовать эти сомнения в конкретные доказательства.
          Пока не очень успешно, так как за давностью лет я разучился мыслить в терминах множеств и графов.
          И процесс восстановления протекает не очень быстро.
          0
          Мне тоже всегда казалось, что это NP-полная задача.
            0
            Да… Эта задача отностится к классу NP-полных… И здесь, наряду с аналогичными алгоритмами (например «жадным» или генетическим), предлагается её решение за полиномиальное время… Цель таких алгоритмов уйти от полного перебора, насколько это возможно.
            +1
            В качестве примера я тут попробую привести задачу, которую мне однажды пришлось решать — решил методом ненаучного тыка, и подмножество точно не было минимальным.
            Кому интересно — тыц
            Было это в 2008 году. Одна жуликоватая компания решила провести СМС-лотерею (ссылка на правила на archive.org). Суть лотереи:
            1. В течение суток участники присылают на короткий номер СМС с 4 буквами русского алфавита, напр. ВОТФ. Количество СМС от одного участника неограниченно.
            2. В определенное время раз в сутки компьютер организаторов лотереи сам выбирает 4 буквы. Буквы не повторяются (АЛВА).
            3. Победители определяются по количеству угаданных букв: Если участник угадал все 4 буквы (позиция не важна), то он является победителем 1 категории. Если угадал 3 буквы — 2-я категория и 2 буквы `— 3-я категория.
            4. Все отправленные в течение суток СМС формируют призовой фонд. Этот призовой фонд делится так: 50% делят между собой поровну все победители 1 категории; 30% фонда делят между собой победители 2-й категории и победители 3-й категории получают обратно стоимость отправленных СМС.

            Понятно, что шанс угадать все 4 буквы довольно мал — всего существует 32x31x30x29 = 863040 комбинаций (буква Ё не участвует), и пытаться перебрать их все имеет смысл только в случае, если в игре участвует более миллиона игроков. Кроме того, технически невозможно отправить в сутки с одного номера такое количество сообщений.

            А вот с угадыванием 3 букв получилось интереснее. Организаторы лотереи опрометчиво присудили слишком большую часть призового фонда за СМС, в которой 3 буквы совпадет с 4 буквами, загаданными компьютером. Я нашел (неоптимальное) множество из 784 СМС вида АБВГ, АБДЕ… и так далее, которое гарантированно получает как минимум один выигрыш 2 категории вне зависимости от того, какие буквы выберет компьютер. При таком количестве СМС игра принесла вполне реальный доход, с лихвой окупивший затраты на отправку этих сообщений. :)

            По моему, это именно для этого алгоритма задача, нет?
              0
              Но опубликования, как мне кажется, стоит.
              Если возможно раздобыть статью в электронном виде, то стоило бы закинуть её куда-нибудь вроде arxiv.org (туда можно поместить статью и на русском, но нужно перевести заголовок и аннотацию на англйский).
                +2
                Fais se que dois adviegne que peut

                никогда бы не подумал что древние греки говорили на современном французском
                  0
                  Это с мерой связано?
                    +3
                    Я нифига не понял, но торт!

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое