Комментарии 11
Можно привести какой-нибудь пример?
… или хотя бы пару картинок… для троечников ;)
Есть два замечания. Во-первых, задача о покрытии множествами является NP-полной. Ни одной такой задачи за последние лет 50 не решили, и сомнительно, что решат.
Во-вторых, я дошел до теоремы 2 и нашел там ошибку. Если в последнем условии пересечение V-шек по E^* не пусто, то соответствующее S^* никак не будет покрытием. Дальше я решил пока не вникать. Мне кажется, что вы ищете решение не среди всего множества решений, а только среди части. Думаю, что в этом основная ошибка.
Во-вторых, я дошел до теоремы 2 и нашел там ошибку. Если в последнем условии пересечение V-шек по E^* не пусто, то соответствующее S^* никак не будет покрытием. Дальше я решил пока не вникать. Мне кажется, что вы ищете решение не среди всего множества решений, а только среди части. Думаю, что в этом основная ошибка.
Во-вторых, я дошел до теоремы 2 и нашел там ошибку. Если в последнем условии пересечение V-шек по E^* не пусто, то соответствующее S^* никак не будет покрытием.
Раз вы не нашли ошибки в Теореме 1, то в соответствии с ней соответствующее S* теоремы 2 обязательно будет покрытием. Более того, оно будет минимальным покрытием. Но не факт, что наименьшим. Этим и занимается теорема 2.
Мне кажется, что вы ищете решение не среди всего множества решений, а только среди части.
Вот! Вы тоже это заметили.
Поскольку я не автор алгоритма, то имею право сомневаться в его правильности.
У меня стали возникать сомнения, когда я попытался при подготовке статьи реализовать алгоритм в коде.
В настоящее время пытаюсь материализовать эти сомнения в конкретные доказательства.
Пока не очень успешно, так как за давностью лет я разучился мыслить в терминах множеств и графов.
И процесс восстановления протекает не очень быстро.
Мне тоже всегда казалось, что это NP-полная задача.
В качестве примера я тут попробую привести задачу, которую мне однажды пришлось решать — решил методом ненаучного тыка, и подмножество точно не было минимальным.
По моему, это именно для этого алгоритма задача, нет?
Кому интересно — тыц
Было это в 2008 году. Одна жуликоватая компания решила провести СМС-лотерею (ссылка на правила на archive.org). Суть лотереи:
Понятно, что шанс угадать все 4 буквы довольно мал — всего существует 32x31x30x29 = 863040 комбинаций (буква Ё не участвует), и пытаться перебрать их все имеет смысл только в случае, если в игре участвует более миллиона игроков. Кроме того, технически невозможно отправить в сутки с одного номера такое количество сообщений.
А вот с угадыванием 3 букв получилось интереснее. Организаторы лотереи опрометчиво присудили слишком большую часть призового фонда за СМС, в которой 3 буквы совпадет с 4 буквами, загаданными компьютером. Я нашел (неоптимальное) множество из 784 СМС вида АБВГ, АБДЕ… и так далее, которое гарантированно получает как минимум один выигрыш 2 категории вне зависимости от того, какие буквы выберет компьютер. При таком количестве СМС игра принесла вполне реальный доход, с лихвой окупивший затраты на отправку этих сообщений. :)
- В течение суток участники присылают на короткий номер СМС с 4 буквами русского алфавита, напр. ВОТФ. Количество СМС от одного участника неограниченно.
- В определенное время раз в сутки компьютер организаторов лотереи сам выбирает 4 буквы. Буквы не повторяются (
АЛВА). - Победители определяются по количеству угаданных букв: Если участник угадал все 4 буквы (позиция не важна), то он является победителем 1 категории. Если угадал 3 буквы — 2-я категория и 2 буквы `— 3-я категория.
- Все отправленные в течение суток СМС формируют призовой фонд. Этот призовой фонд делится так: 50% делят между собой поровну все победители 1 категории; 30% фонда делят между собой победители 2-й категории и победители 3-й категории получают обратно стоимость отправленных СМС.
Понятно, что шанс угадать все 4 буквы довольно мал — всего существует 32x31x30x29 = 863040 комбинаций (буква Ё не участвует), и пытаться перебрать их все имеет смысл только в случае, если в игре участвует более миллиона игроков. Кроме того, технически невозможно отправить в сутки с одного номера такое количество сообщений.
А вот с угадыванием 3 букв получилось интереснее. Организаторы лотереи опрометчиво присудили слишком большую часть призового фонда за СМС, в которой 3 буквы совпадет с 4 буквами, загаданными компьютером. Я нашел (неоптимальное) множество из 784 СМС вида АБВГ, АБДЕ… и так далее, которое гарантированно получает как минимум один выигрыш 2 категории вне зависимости от того, какие буквы выберет компьютер. При таком количестве СМС игра принесла вполне реальный доход, с лихвой окупивший затраты на отправку этих сообщений. :)
По моему, это именно для этого алгоритма задача, нет?
Но опубликования, как мне кажется, стоит.Если возможно раздобыть статью в электронном виде, то стоило бы закинуть её куда-нибудь вроде arxiv.org (туда можно поместить статью и на русском, но нужно перевести заголовок и аннотацию на англйский).
Fais se que dois adviegne que peut
никогда бы не подумал что древние греки говорили на современном французском
Это с мерой связано?
Я нифига не понял, но торт!
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм поиска наименьшего по мощности покрытия конечного множества его подмножествами