|
FOX
|
|
Клерчила
|
|
|
|
|
|
|
Рег.: 23.09.2002
|
|
Сообщений: 4723
|
|
Из: Б-1230
|
|
Рейтинг: 2117
|
|
Задача о множествах
04.03.2010 10:47
|
|
|
Имеется множество X (допустим (1,5,23,7,15)) прозвольной длины и состоящий из произвольных натуральных чисел, которые не повторяются внутри множества.
Также имеется множество множеств Y(допустим(1), (5,24), (5,23), (7,23,15), (7), (15)) элементы которого имеют меньшую длину, чем Х, так же состоящих из произвольных рандомных натуральных чисел, так же в Y не может быть 2 одинаковых множеств.
Задача: Найти минимальное количество объединений множеств в Y, так чтобы они образовывали Х, т.е. в моем примере это будет (1,5,23,7,15)=((1),(7,23,15),(5))
Нужен метод решения, который будет отрабатывать быстрее чем полный перебор.
Подскажите какие алгоритмы можно посмотреть, реализация от вас не требуется 
Читал о жадных алгоритмах, в принципе можно попробовать подтянуть его.
|
----
Когда мы плачем о ком-то, то на самом деле мы все равно плачем не о ком-то, а жалеем самих себя. |
|
|
bashtanov
|
|
спец по говядине
|
|
|
|
|
|
|
Рег.: 11.05.2007
|
|
Сообщений: 9569
|
|
Из: например
|
|
Рейтинг: 7070
|
|
Re: Задача о множествах
[re: FOX]
04.03.2010 11:41
|
|
|
В ответ на:
Имеется множество X (допустим (1,5,23,7,15)) прозвольной длины и состоящий из произвольных натуральных чисел, которые не повторяются внутри множества.
ощути разницу между множеством и последовательностью
|
|
|
abv
|
|
|
|
|
|
|
|
|
Рег.: 21.09.2007
|
|
Сообщений: 6924
|
|
|
|
Рейтинг: 6747
|
|
Re: Задача о множествах
[re: FOX]
04.03.2010 13:31
|
|
|
это - "задача о покрытии множествами". NP-трудная. так что быстрого алгоритма для нее нету.
либо полный перебор, либо приближенный жадный алгоритм, либо еще какие-нибудь эвристики по месту
жадный алгоритм прост: в каждый момент мы выбираем множество, покрывающее максимальное число еще не покрытых элементов. утверждается, что его можно реализовать за линейное время.
решение, найденное жадным алгоритмом, будет не более чем в H(k) раз хуже оптимального
где H(k)=1+1/2+...+1/k
а k = максимальный размер множества из тех ,которыми пытаешься покрыть
|
|
|
|
FOX
|
|
Клерчила
|
|
|
|
|
|
|
Рег.: 23.09.2002
|
|
Сообщений: 4723
|
|
Из: Б-1230
|
|
Рейтинг: 2117
|
|
Re: Задача о множествах
[re: abv]
04.03.2010 14:19
|
|
|
Угу, не успел отписаться, тоже нашел эту инфу.
И т.к. требуется еще и поиск строгого минимума, то только полный перебор.
Спасибо.
|
----
Когда мы плачем о ком-то, то на самом деле мы все равно плачем не о ком-то, а жалеем самих себя. |
|
|
Non_trivial
|
|
enthusiast
|
|
|
|
|
|
|
Рег.: 06.12.2006
|
|
Сообщений: 335
|
|
Из: ГЗ
|
|
Рейтинг: 101
|
|
Re: Задача о множествах
[re: abv]
04.03.2010 17:57
|
|
|
В ответ на:
NP-трудная. так что быстрого алгоритма для нее нету.
Поправочка: не нету, а никто его не знает, но и не доказано, что его нет
|
|
|
Lehtym
|
|
демоверсия
|
|
|
|
|
|
|
Рег.: 06.12.2004
|
|
Сообщений: 332
|
|
Из: Shit Building
|
|
Рейтинг: 350
|
|
|
Quote:
не нету, а никто его не знает, но и не доказано, что его нет
Для того, кто собрался его прямо сейчас писать, это означает, что его нету 
|
|
|
DizzyDen
|
|
достаточно добр
|
|
|
|
|
|
|
Рег.: 04.03.2003
|
|
Сообщений: 51430
|
|
Из: http://лакалхвост
|
|
Рейтинг: 13545
|
|
Re: Задача о множествах
[re: abv]
05.03.2010 18:19
|
|
|
Quote:
NP-трудная. так что быстрого алгоритма для нее нету.
... пока не установлено, что P=NP.
|
If stateless paradigm is good for your code, why shouldn't it be for your country? |
|
|
abv
|
|
|
|
|
|
|
|
|
Рег.: 21.09.2007
|
|
Сообщений: 6924
|
|
|
|
Рейтинг: 6747
|
|
|
но-большинство то понимает, что скорее всего такой халявы не будет и там будет "не равно"
|
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
Re: Задача о множествах
[re: abv]
06.03.2010 09:39
|
|
|
там вполне может оказаться N^9000, что тоже не сильно всех обрадует
|
|
Список
Плоский
Дерево
