这并不能解决您的问题(嗯,不够快),但是您没有得到很多想法,其他人可能会在这里找到有用的东西。
这是一个简短的纯 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)