Задача о точном покрытии, но с ограничением на точное количество подмножеств в решении

Question

Я относительно новичок в точном покрытии и подобных проблемах, поэтому, пожалуйста, потерпите меня. Предположим, у меня есть типичная проблема с точным покрытием, ie. учитывая набор X и набор подмножеств X S , я хочу найти S * (подмножество S ), который точно охватывает X . Однако я хочу, чтобы решение S * содержало ровно k элементов. Более того, достаточно одного решения.

Я знаю, что алгоритм Кнута X разработан так, чтобы возвращать все возможные решения. Должен ли я просто запустить алгоритм Кнута и перебирать решения, пока не найду решение с k элементами, или есть (как я подозреваю) гораздо лучший способ? Я использую Python btw.

Для контекста размер X <100, но размер <em>S может быть 10 ^ 6. k относительно мало при <10. </p>

Answer 1

Если k мало, вы можете просто попробовать добавить k дополнительных элементов и продублировать каждое подмножество k раз, причем каждый дубликат будет включать ровно один из k дополнительных элементов.

Другой Подход состоял бы в том, чтобы решить проблему точного покрытия как целочисленной линейной программы и решить ее с помощью решателя ILP. Тогда у вас будет 0–1 переменные x_i, которые говорят, включено ли i -е подмножество в решение, с ограничениями, которые предотвращают включение перекрывающихся наборов в решение. В этой формулировке, чтобы обеспечить прикрытие ровно k подмножествами, у вас просто будет дополнительное ограничение, которое sum(x_i) = k.

Также можно изменить алгоритм X, чтобы он работал напрямую с ограничением. Просто посчитайте, сколько строк вы уже выбрали, и, если вы уже выбрали k, просто не выполняйте поиск без дальнейшего поиска. Точно так же игнорируйте решения, которые имеют менее k строк.