如何加快代码解决位删除难题

Question

[这与最小集合覆盖有关 ]

我想通过计算机解决以下小巧的n难题.考虑长度为n的所有2 ^ n个二进制向量.对于每一个,您只删除n/3个位,留下二进制向量长度2n/3(假设n是3的整数倍).目标是选择您删除的位,以便最小化保留在末尾的长度为2n/3的不同二进制向量的数量.

例如,对于n = 3,最佳答案是2个不同的向量11和00.对于n = 6,它是4,对于n = 9,它是6,对于n = 12,它是10.

我之前尝试将此问题解决为以下类型的最小集合覆盖问题.所有列表仅包含1和0.

我说,名单A涵盖了列表B,如果你可以B从A正好插入x符号.

考虑所有2 ^ n个1和0的长度n和集合列表x = n/3.我想计算一组2n/3涵盖所有长度的最小长度列表.David Eisenstat提供了将这个最小集合覆盖问题转换为混合整数编程问题的代码,该问题可以输入CPLEX(或http://scip.zib.de/,它是开源的).

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')

问题是,如果你设置n = 15,那么它输出的实例对于我能找到的任何求解器来说都太大了.有没有更有效的方法来解决这个问题所以我可以解决n = 15甚至n = 18？

Answer 1

首先考虑是否有 6 位。您可以扔掉 2 位。因此，任何 6-0、5-1 或 4-2 的模式平衡都可以转换为 0000 或 1111。在 3-3 零一平衡的情况下，任何模式都可以转换为以下四种情况之一：1000、0001 、0111 或 1110。因此，6 位的一个可能的最小集合是：

0000
0001
0111
1110
1000
1111

现在考虑 9 位，其中 3 位被丢弃。您有以下 14 个主模式集：

000000
100000
000001
010000
000010
110000
000011
001111
111100
101111
111101
011111
111110
111111

换句话说，每个模式集的中心都有 1/0，每端都有 n/3-1 位的每个排列。例如，如果有 24 位，那么中间将有 17 位，末端有 7 位。由于 2^7 = 128，您将有 4 x 128 - 2 = 510 种可能的模式。

为了找到正确的删除，有多种算法。一种方法是找到当前位组与每个主模式之间的编辑距离。具有最小编辑距离的图案是要转换的图案。该方法使用动态规划。另一种方法是使用一组规则对模式进行树搜索以查找匹配模式。