python - 最小セットカバー

Question

次のような最小集合被覆問題を解きたいと思います。すべてのリストには 1 と 0 のみが含まれます。

正確に記号 を挿入して作成できる場合、リストはリストAをカバーすると言います。BBAx

lengthnと setの 1 と 0 のすべての 2^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。最悪の場合、時間が指数関数的になると予想しています。