Наименьшее количество контейнеров, которые содержат все заданные элементы

Question

Предполагать C относится к набору контейнеров {c1,c2,c3....cn}где каждый из этих контейнеров содержит конечный набор целых чисел {i1,i2,i3...im}, Кроме того, предположим, что целое число может существовать в нескольких контейнерах. Учитывая конечный набор целых чисел S{s1,s2,s3...sz}найти размер наименьшего подмножества C который содержит все целые числа в S,

Обратите внимание, что могут быть тысячи контейнеров с сотнями целых чисел. Таким образом, грубая сила медленно решает эту проблему.

Я попытался решить проблему, используя алгоритм Жадный. То есть каждый раз, когда я выбираю контейнер с наибольшим числом целых в наборе S, но я не смог!

Кто-нибудь может предложить быстрый алгоритм для этой проблемы?

Answer 1

Это хорошо известная проблема с множеством покрытий. Это NP-сложный процесс - фактически, его вариант решения был одной из канонических NP-полных задач и входил в число 21 проблем, включенных в статью Карпа 1972 года, и поэтому эффективный алгоритм не известен. Если вы не можете определить какую-то особую дополнительную структуру проблемы, вам придется довольствоваться приблизительным результатом: то есть подмножеством C, объединение которого содержит S, которое не обязательно является наименьшим таким подмножеством C.

Жадный алгоритм - это, вероятно, ваша лучшая ставка: он находит коллекцию наборов, которая не более чем в O(log |C|) умножается на размер наименьшей такой коллекции.

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

каждый раз, когда я выбираю контейнер с наибольшим числом целых чисел в наборе S

но в обычном жадном алгоритме правило состоит в том, чтобы на каждом этапе выбирать контейнер с наибольшим числом целых чисел в наборе S , которых пока нет ни в одном из выбранных контейнеров.