Нахождение наибольшего объединения непересекающихся множеств из заданных множеств

Question

У меня есть несколько наборов (около 100 или около того) чисел в диапазоне от 1 до 32, каждый из которых имеет не более 32 элементов.

Например:

[1,2]
[3,4]
[1,2,3]

Что я я пытаюсь сделать, это сделать алгоритм для вывода наибольшего объединения множеств, которые не имеют пересечений друг с другом.

Выход из примера [[1,2], [3,4]], где они не имеют любые пересечения друг с другом, и их объединение больше, чем множество [[1,2,3]].

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

Кажется, что написание алгоритма полиномиальной сложности времени трудно, любые идеи не более 2 ^ n сложности времени будут быть оцененным.

Answer 1

В общем случае из 100 случайных подмножеств {1..32} базовый c исчерпывающий поиск работает довольно хорошо. Размер подмножества будет около 16, и если вы выберете 100 из них, довольно часто ни одна пара не будет непересекающейся. Это примерно n ^ 2/2 сравнений (если подмножества выбраны случайным образом).

В особом случае, когда длина подмножеств мала (например, 5), сложность возрастает гораздо быстрее. Базовый c исчерпывающий поиск должен работать как минимум до 500.

Я хочу сказать, что это зависит от ваших данных.

Answer 2

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