Задача о множествах

Stas33

Имеется множество 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)17,23,155
Нужен метод решения, который будет отрабатывать быстрее чем полный перебор.
Подскажите какие алгоритмы можно посмотреть, реализация от вас не требуется :)
Читал о жадных алгоритмах, в принципе можно попробовать подтянуть его.

Suebaby

Имеется множество X (допустим (1,5,23,7,15 прозвольной длины и состоящий из произвольных натуральных чисел, которые не повторяются внутри множества.
ощути разницу между множеством и последовательностью

Damrad

это - "задача о покрытии множествами". NP-трудная. так что быстрого алгоритма для нее нету.
либо полный перебор, либо приближенный жадный алгоритм, либо еще какие-нибудь эвристики по месту
жадный алгоритм прост: в каждый момент мы выбираем множество, покрывающее максимальное число еще не покрытых элементов. утверждается, что его можно реализовать за линейное время.
решение, найденное жадным алгоритмом, будет не более чем в H(k) раз хуже оптимального
где H(k)=1+1/2+...+1/k
а k = максимальный размер множества из тех ,которыми пытаешься покрыть

Stas33

Угу, не успел отписаться, тоже нашел эту инфу.
И т.к. требуется еще и поиск строгого минимума, то только полный перебор.
Спасибо.

romanenkoroman1

NP-трудная. так что быстрого алгоритма для нее нету.

Поправочка: не нету, а никто его не знает, но и не доказано, что его нет

Boris

не нету, а никто его не знает, но и не доказано, что его нет
Для того, кто собрался его прямо сейчас писать, это означает, что его нету :D

stm7543347

NP-трудная. так что быстрого алгоритма для нее нету.
... пока не установлено, что P=NP.

Damrad

но-большинство то понимает, что скорее всего такой халявы не будет и там будет "не равно"

Vlad128

там вполне может оказаться N^9000, что тоже не сильно всех обрадует :)
Оставить комментарий
Имя или ник:
Комментарий: