最小設置覆蓋率

我想解決以下排序的最小設置覆蓋率問題。所有列表只包含1和0。最小設置覆蓋率

我說一個列表A覆蓋列表B如果你能正好插入x符號使從AB。

考慮所有2^n個1和0的長度爲n的列表並設置x = n/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的時間是指數級的。

來源

2013-09-24 felix

我實際上並不知道你是問什麼。你能解釋一下嗎？ – Veedrac

@Veedrac小例子如何。設置n = 3和x = 1，因此有8個可能的1和0列表。我想找到涵蓋全部8個的最小長度爲2的列表。所以採取[0,0]，[1,1]。我們可以通過向這兩個列表中的任意一個添加1或0來創建長度爲3的任何列表。這是否更清楚？我的方法是將其轉換爲最小集覆蓋問題。 – felix

是的，都清楚。 – Veedrac

我寫了一個小程序來編寫一個整數程序，由 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>

來源

2013-09-25 21:15:52

謝謝。太棒了。 – felix

最小設置覆蓋率

回答

相關問題