Задача нахождения ближайшей сходной цепочки (?)

← →
teleroot (2014-01-15 13:36) [0]

Всем привет!
Есть одна задача. Может, она и не слишком сложная, и, в принципе, решается, так сказать, в лоб и с наскоку.
Но вдруг кто знает, может, для данной задачи есть "классическое решение", и (чем черт не шутит) вдруг у этой задачи есть общеупотребительное имя.
Задача:
Дано множество N, состоящее из множеств целых чисел (на самом деле тип вх. элементов не важен)
На вход подается множество K целых чисел.
Необходимо: найти из множества N одно или несколько множеств, объединение которых будет включать в себя все элементы множества К. Количество множеств из N нужно минимизировать.

Вот как-то так

← →
Ega23 © (2014-01-15 13:46) [1]

Одно, несколько, или все?

← →
teleroot (2014-01-15 15:52) [2]

одно или несколько.

вот представим: у нас есть множества:

1. [1, 4, 7, 33]
2. [5, 10]
3. [2, 7, 13]

и есть входящее множество K: [4, 10]

Результатом будет:
множество 1
и множество 2

← →
Ega23 © (2014-01-15 16:38) [3]

> вот представим: у нас есть множества:
>
> 1. [1, 4, 7, 33]
> 2. [5, 10]
> 3. [2, 7, 13]
>
> и есть входящее множество K: [4, 10]

Расширим задачу.
Исходные множества:

1. [4]
2. [10]
3. [4, 10]
4. [5, 10]
5. [3, 4]

Входящее - [4, 10]

Какой здесь должен быть результат?
Если все варианты, то
(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (2, 5), (3), (3, 4), (3, 5), (4, 5)

Какой именно ответ в твоей постановке вопроса должен быть?

← →
teleroot (2014-01-15 17:04) [4]

Конечно, решений может быть несколько.
Что касается твоего примера, то ответом будет: множество 3,
т.к. в первом посте было дополнительное условие о том, что "Количество множеств из N нужно минимизировать."

← →
Ega23 © (2014-01-15 17:09) [5]

> Конечно, решений может быть несколько.

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

Ну ежели мой вариант расширить на
1. [4]
2. [10]
3. [4, 10]
4. [5, 10]
5. [3, 4]
6. [1, 2, 3, 4, 10]

то правильный ответ будет (3), (6), так?

← →
teleroot (2014-01-15 17:17) [6]

верно.
Олег, я рад любым вариантам решения - ведь коллективный разум всегда сильнее.
Но как я уже писал выше, основной вопрос: не занимаюсь ли я изобретением велосипеда и нет ли классического решения для этой или сходной задачи. К сожалению, поисковики не всегда могут найти название задачи по его описанию )

← →
Ega23 © (2014-01-15 17:37) [7]

Я всего лишь уточнял условие задачи, а то в [0] как-то мутно результат описывался.
Теперь по решениям: лично я какого-то общего не знаю. Сама задача несколько похожа на механизм индексирования слов в полнотекстовом поиске водном из наших проектов.
Я сейчас чутка подумаю, в башке малость покручу и вечером отпишусь.
А ты пока подумай над инверсией. Если вкратце, то раскладываешь все встречающиеся элементы в исходных множествах на цепочки, в которых эти элементы встречаются. Т.е.

1. [a, b, c, d, e]
2. [a, e, s, x]
3. [d, u, x, y]
4. [x, y, z]

инвертируем в

a - [1, 2]
b - [1]
c - [1]
d - [1, 3]
e - [1, 2]
s - [2]
u - [3]
x - [2, 3, 4]
y - [3, 4]
z - [4]

и теперь входящее множество по каждому из элементов перебираем, находим номера множеств и уже начинаем играть с ними.
Инверсия занимает определённое время, выигрыш будет если на неизменный набор исходных множеств приходит много входящих. Для разовой операции, вроде как, бессмысленно. Хотя тоже стоит покрутить, мало ли что.

← →
teleroot (2014-01-15 18:04) [8]

Ок. Спасибо.
Идея с инверсией - замечательная.
Тут вот еще что. В настоящий момент нет никаких ограничений на структуры хранения данных и на первичные оптимизации. Можно делать совершенно разные допущения.

Это задача о покрытии, она относитя к NP-полным проблемам, точное решение которых получается полным перебором
http://ru.wikipedia.org/wiki/Задача_о_покрытии_множества

← →
teleroot (2014-01-15 18:47) [10]

Задача нахождения ближайшей сходной цепочки (?) Найти похожие ветки