16

[这与最小设置覆盖有关]

我想通过计算机解决以下小尺寸 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涵盖了列表。BBAx

考虑所有 2^n 个长度为 1 和 0 的列表n和 set 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?

4

2 回答 2

4

这并不能解决您的问题(嗯,不够快),但是您没有得到很多想法,其他人可能会在这里找到有用的东西。

这是一个简短的纯 Python 3 程序,使用带有一些贪婪排序启发式的回溯搜索。它非常快速地解决了 N = 3、6 和 9 个实例。它也很快找到 N=12 的大小为 10 的封面,但显然需要更长的时间来耗尽搜索空间(我没时间了,它仍在运行)。对于 N=15,初始化时间已经很慢了。

位串在这里用普通的 N 位整数表示,因此消耗的存储空间很小。这是为了简化以更快的语言重新编码。它确实大量使用整数集,但没有其他“高级”数据结构。

希望这对某人有帮助!但很明显,随着 N 的增加,可能性的组合爆炸确保了在不深入研究问题的数学的情况下,没有任何事情会“足够快”。

def dump(cover):
    for s in sorted(cover):
        print("    {:0{width}b}".format(s, width=I))

def new_best(cover):
    global best_cover, best_size
    assert len(cover) < best_size
    best_size = len(cover)
    best_cover = cover.copy()
    print("N =", N, "new best cover, size", best_size)
    dump(best_cover)

def initialize(N, X, I):
    from itertools import combinations
    # Map a "wide" (length N) bitstring to the set of all
    # "narrow" (length I) bitstrings that generate it.
    w2n = [set() for _ in range(2**N)]
    # Map a narrow bitstring to all the wide bitstrings
    # it generates.
    n2w = [set() for _ in range(2**I)]
    for wide, wset in enumerate(w2n):
        for t in combinations(range(N), X):
            narrow = wide
            for i in reversed(t):  # largest i to smallest
                hi, lo = divmod(narrow, 1 << i)
                narrow = ((hi >> 1) << i) | lo
            wset.add(narrow)
            n2w[narrow].add(wide)
    return w2n, n2w

def solve(needed, cover):
    if len(cover) >= best_size:
        return
    if not needed:
        new_best(cover)
        return
    # Find something needed with minimal generating set.
    _, winner = min((len(w2n[g]), g) for g in needed)
    # And order its generators by how much reduction they make
    # to `needed`.
    for g in sorted(w2n[winner],
                    key=lambda g: len(needed & n2w[g]),
                    reverse=True):
        cover.add(g)
        solve(needed - n2w[g], cover)
        cover.remove(g)

N = 9  # CHANGE THIS TO WHAT YOU WANT

assert N % 3 == 0
X = N // 3 # number of bits to exclude
I = N - X  # number of bits to include

print("initializing")
w2n, n2w = initialize(N, X, I)
best_cover = None
best_size = 2**I + 1  # "infinity"
print("solving")
solve(set(range(2**N)), set())

N=9 的示例输出:

initializing
solving
N = 9 new best cover, size 6
    000000
    000111
    001100
    110011
    111000
    111111

跟进

对于 N=12,这最终完成,确认最小覆盖集包含 10 个元素(它在开始时很快就找到了)。我没有计时,但至少花了5个小时。

为什么?因为它接近于脑死亡;-) 一个完全幼稚的搜索将尝试 256 个 8 位短字符串的所有子集。有 2**256 个这样的子集,大约 1.2e77 - 它不会在宇宙的预期生命周期内完成;-)

这里的排序噱头首先检测到“全0”和“全1”的短字符串必须在任何覆盖集中,所以选择它们。这让我们只看剩下的 254 个短字符串。然后贪婪的“选择一个覆盖最多的元素”策略很快找到一个包含 11 个元素的覆盖集,然后很快找到一个包含 10 个元素的覆盖集。这恰好是最佳的,但需要很长时间才能耗尽所有其他可能性。

此时,任何达到 10 个元素的覆盖集的尝试都将被中止(那么它不可能小于10 个元素!)。如果这也完全天真地完成,则需要尝试添加(到“全 0”和“全 1”字符串)剩余 254 个的所有 8 元素子集,并且 254-choose-8 约为 3.8e14。比 1.2e77 小得多 - 但仍然太大而无法实用。这是一个有趣的练习,可以理解代码如何做得比这更好。提示:这与这个问题中的数据有很大关系。

工业级求解器更加复杂和复杂。我对这个简单的小程序在较小的问题实例上的表现感到惊喜!它走运了。

但是对于 N=15,这种简单的方法是没有希望的。它很快就找到了一个包含 18 个元素的封面,但至少在几个小时内都没有明显的进展。在内部,它仍在处理needed包含数百(甚至数千)个元素的集合,这使得主体的solve()成本相当高。它仍然有 2**10 - 2 = 1022 个短字符串需要考虑,1022-choose-16 大约是 6e34。即使这段代码被加速了一百万倍,我也不认为它会有明显的帮助。

不过,尝试很有趣:-)

和一个小的重写

这个版本在完整的 N=12 运行中运行速度至少快 6 倍,只需提前一级切断无用的搜索。还可以加快初始化速度,并通过将 2**N 个集合更改为列表来减少内存使用w2n(这些集合上不使用集合操作)。尽管如此,N = 15仍然没有希望:-(

def dump(cover):
    for s in sorted(cover):
        print("    {:0{width}b}".format(s, width=I))

def new_best(cover):
    global best_cover, best_size
    assert len(cover) < best_size
    best_size = len(cover)
    best_cover = cover.copy()
    print("N =", N, "new best cover, size", best_size)
    dump(best_cover)

def initialize(N, X, I):
    from itertools import combinations
    # Map a "wide" (length N) bitstring to the set of all
    # "narrow" (length I) bitstrings that generate it.
    w2n = [set() for _ in range(2**N)]
    # Map a narrow bitstring to all the wide bitstrings
    # it generates.
    n2w = [set() for _ in range(2**I)]
    # mask[i] is a string of i 1-bits
    mask = [2**i - 1 for i in range(N)]
    for t in combinations(range(N), X):
        t = t[::-1]  # largest i to smallest
        for wide, wset in enumerate(w2n):
            narrow = wide
            for i in t:  # delete bit 2**i
                narrow = ((narrow >> (i+1)) << i) | (narrow & mask[i])
            wset.add(narrow)
            n2w[narrow].add(wide)
    # release some space
    for i, s in enumerate(w2n):
        w2n[i] = list(s)
    return w2n, n2w

def solve(needed, cover):
    if not needed:
        if len(cover) < best_size:
            new_best(cover)
        return
    if len(cover) >= best_size - 1:
        # can't possibly be extended to a cover < best_size
        return
    # Find something needed with minimal generating set.
    _, winner = min((len(w2n[g]), g) for g in needed)
    # And order its generators by how much reduction they make
    # to `needed`.
    for g in sorted(w2n[winner],
                    key=lambda g: len(needed & n2w[g]),
                    reverse=True):
        cover.add(g)
        solve(needed - n2w[g], cover)
        cover.remove(g)

N = 9  # CHANGE THIS TO WHAT YOU WANT

assert N % 3 == 0
X = N // 3 # number of bits to exclude
I = N - X  # number of bits to include

print("initializing")
w2n, n2w = initialize(N, X, I)

best_cover = None
best_size = 2**I + 1  # "infinity"
print("solving")
solve(set(range(2**N)), set())

print("best for N =", N, "has size", best_size)
dump(best_cover)
于 2013-10-18T18:08:52.487 回答
-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 种可能的模式。

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

于 2013-10-11T20:28:02.673 回答