Алгоритм - найти наименьшее подмножество ячеек, представляющих все строки

Question

У меня есть несколько списков, которые можно рассматривать как строки целых чисел. Например:

[1 3 5] 
[3 7] 
[3 5 7] 
[1 5 9] 
[3 9] 
[1 7] 
[5 9 11] 

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

• каждая строка имеет по крайней мере один из выбранных чисел,
• в случай связей мощности, выберите набор, имеющий самую высокую сумму.

В моем примере я считаю, что результат должен быть [5 7 9] (предпочтительнее [3 5 7] или [1 3 11] или ... много возможностей).

Вторая часть тривиальна (выбор высшей суммы), но поколение всех минимальных подмножеств в мощности кажется трудным.

Знаете ли вы, хороший способ достичь этого?

Редактировать

Размер данных медленно растет с итераций, но мне нужно точное совпадение.

Answer 1

Версия с минимальной мощностью NP-Complete. Set Cover можно свести к этому. Требование максимального числа из них только усложняет задачу.

Btw, другой ответ, говорящий о логической выполнимости: Неверный! Вам нужно уменьшить логическую выполнимость этой проблемы, чтобы показать NP-полноту, а не наоборот.

Установить крышки в основном:

Дайте набор множеств S1, S2, ... Sn подмножеств множества X, найти наименьшее суб-коллекции (в терминах числа множеств), объединение охватывает все элементы в S1 U S2 U ... U Sn.

Чтобы уменьшить это к нашей проблеме,

Пусть S = S1 U S2 ... Sn U. = {X1, x2, ..., хт}

Пусть C_i = {j такие, что хи в Sj}

Поток c_i к нашей проблеме.

Теперь, если наша задача была разрешима в полиномиальное время, и мы могли бы найти минимальное множество элементов элементов C_i, то мы можем найти множество покрытий для Si и наоборот.

Обычно это можно решить как проблему с целым программированием (также NP-Hard).

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

Также, к сожалению, было показано, что это NP-сложно приблизить даже к постоянному коэффициенту (на самом деле, я считаю, что это O (logn)).