Минимальная комплектация обложки

Question

Я хотел бы решить проблему минимального набора покрытия следующего вида. Все списки содержат только 1 и 0.

Я говорю, что список A охватывает список B если вы можете сделать B от A вставив точно x символы.

Рассмотрим все 2^n списков длины 1 и 0 n и установить x = n/3, Я бы вычислил минимальный набор списков длины 2n/3 это охватывает их всех.

Вот наивный подход, который я начал. Для каждого возможного списка длины 2n/3 Я создаю набор всех списков, которые я могу создать из него с помощью этой функции (написанной DSM).

from itertools import product, combinations

def all_fill(source, num):
    output_len = len(source) + num
    for where in combinations(range(output_len), len(source)):
        # start with every possibility
        poss = [[0,1]] * output_len
        # impose the source list
        for w, s in zip(where, source):
            poss[w] = [s]
        # yield every remaining possibility
        for tup in product(*poss):
            yield tup

Затем я создаю набор наборов следующим образом, используя n = 6 В качестве примера.

n = 6
shortn = 2*n/3
x = n/3
coversets=set()
for seq in product([0,1], repeat = shortn):
    coversets.add(frozenset(all_fill(seq,x)))

Я хотел бы найти минимальный набор наборов из наборов обложек, объединение которых allset = set(product([0,1], repeat=n)),

В этом случае, set(all_fill([1,1,1,1],2)), set(all_fill([0,0,0,0],2)), set(all_fill([1,1,0,0],2)), set(all_fill([0,0,1,1],2)) Сделаю.

Моя цель - решить проблему для n = 12, Я рад использовать внешние библиотеки, если это поможет, и я ожидаю, что время будет экспоненциальным в n в худшем случае.

Answer 1

Я написал небольшую программу для написания целочисленной программы, которую нужно решить с помощью CPLEX или другого MIP-решателя. Ниже это решение для n=12.

---

from collections import defaultdict
from itertools import product, combinations

def all_fill(source, num):
    output_len = (len(source) + num)
    for where in combinations(range(output_len), len(source)):
        poss = ([[0, 1]] * output_len)
        for (w, s) in zip(where, source):
            poss[w] = [s]
        for tup in product(*poss):
            (yield tup)

def variable_name(seq):
    return ('x' + ''.join((str(s) for s in seq)))
n = 12
shortn = ((2 * n) // 3)
x = (n // 3)
all_seqs = list(product([0, 1], repeat=shortn))
hit_sets = defaultdict(set)
for seq in all_seqs:
    for fill in all_fill(seq, x):
        hit_sets[fill].add(seq)
print('Minimize')
print(' + '.join((variable_name(seq) for seq in all_seqs)))
print('Subject To')
for (fill, seqs) in hit_sets.items():
    print(' + '.join((variable_name(seq) for seq in seqs)), '>=', 1)
print('Binary')
for seq in all_seqs:
    print(variable_name(seq))
print('End')

---

MIP - Integer optimal solution:  Objective =  1.0000000000e+01
Solution time =    7.66 sec.  Iterations = 47411  Nodes = 337

CPLEX> Incumbent solution
Variable Name           Solution Value
x00000000                     1.000000
x00000111                     1.000000
x00011110                     1.000000
x00111011                     1.000000
x10110001                     1.000000
x11000100                     1.000000
x11001110                     1.000000
x11100001                     1.000000
x11111000                     1.000000
x11111111                     1.000000
All other variables matching '*' are 0.
CPLEX>