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

[andy_p]

Можно привести какой-нибудь пример?

[bigfatbrowncat]

… или хотя бы пару картинок… для троечников ;)

[SeptiM]

Есть два замечания. Во-первых, задача о покрытии множествами является NP-полной. Ни одной такой задачи за последние лет 50 не решили, и сомнительно, что решат.

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

[alex103]

Во-вторых, я дошел до теоремы 2 и нашел там ошибку. Если в последнем условии пересечение V-шек по E^* не пусто, то соответствующее S^* никак не будет покрытием.

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

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

Вот! Вы тоже это заметили.
Поскольку я не автор алгоритма, то имею право сомневаться в его правильности.
У меня стали возникать сомнения, когда я попытался при подготовке статьи реализовать алгоритм в коде.
В настоящее время пытаюсь материализовать эти сомнения в конкретные доказательства.
Пока не очень успешно, так как за давностью лет я разучился мыслить в терминах множеств и графов.
И процесс восстановления протекает не очень быстро.

[andy_p]

Мне тоже всегда казалось, что это NP-полная задача.

[alex103]

Да… Эта задача отностится к классу NP-полных… И здесь, наряду с аналогичными алгоритмами (например «жадным» или генетическим), предлагается её решение за полиномиальное время… Цель таких алгоритмов уйти от полного перебора, насколько это возможно.

[stanishevsky]

В качестве примера я тут попробую привести задачу, которую мне однажды пришлось решать — решил методом ненаучного тыка, и подмножество точно не было минимальным.

Кому интересно — тыц

Было это в 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 категории вне зависимости от того, какие буквы выберет компьютер. При таком количестве СМС игра принесла вполне реальный доход, с лихвой окупивший затраты на отправку этих сообщений. :)

По моему, это именно для этого алгоритма задача, нет?

[Regis]

Но опубликования, как мне кажется, стоит.

Если возможно раздобыть статью в электронном виде, то стоило бы закинуть её куда-нибудь вроде arxiv.org (туда можно поместить статью и на русском, но нужно перевести заголовок и аннотацию на англйский).

[degs]

Fais se que dois adviegne que peut

никогда бы не подумал что древние греки говорили на современном французском

[Koncopd]

Это с мерой связано?

[qmax]

Я нифига не понял, но торт!