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

Question

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

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

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

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

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

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

Знаете ли вы, как можно добиться этого?

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

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

Answer 1

Минимальная кардинальная версия - NP-Complete. Установить обложку можно уменьшить до этого.Требование максимума среди тех только усложняет задачу.

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

Обложка набора в основном:

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

Чтобы уменьшить это до нашегозадача,

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

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

Подайте C_i в нашу проблему.

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

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

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

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