Ответ 1
Это не решает вашу проблему (ну, не так быстро), но вы не получаете много идей, а кто-то еще может найти что-то полезное для создания здесь.
Это короткая чистая программа Python 3, использующая поиск обратного следа с некоторыми жадными эвристиками порядка. Он очень быстро решает N = 3, 6 и 9 экземпляров. Он также быстро находит покрытие размером 10 для N = 12, но, по-видимому, потребуется намного больше времени для исчерпания пространства поиска (у меня нет времени для этого, и он все еще работает). При 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
Followup
При N = 12 это окончательно закончилось, подтвердив, что минимальное покрытие содержит 10 элементов (которые он нашел очень скоро в начале). Я не успел, но потребовалось не менее 5 часов.
Почему? Потому что это близко к мозгу - мертво;-) Полностью наивный поиск будет проверять все подмножества 256 8-битных коротких строк. Есть 2 ** 256 таких подмножеств, около 1,2e77 - это не закончилось бы в ожидаемом времени жизни Вселенной; -)
Упорядочивающие трюки здесь сначала обнаруживают, что "все 0" и "все 1" короткие строки должны быть в любом наборе покрытий, поэтому выбирайте их. Это оставляет нам смотреть на "только" 254 оставшихся коротких строк. Тогда жадный "выбрать элемент, который покрывает самую" стратегию, очень быстро находит набор покрытий с 11 полными элементами, а вскоре после этого - покрытие с 10 элементами. Это бывает оптимальным, но для исчерпания всех других возможностей требуется много времени.
В этот момент любая попытка набора покрытий, которая достигает 10 элементов, прерывается (тогда она не может быть меньше 10 элементов!). Если бы это было сделано полностью наивно, нужно было бы попробовать добавить (к строкам "все 0" и "все 1" ) все 8-элементные подмножества оставшихся 254, а 254-select-8 - около 3.8e14. Очень меньше 1,2e77 - но все же слишком большой, чтобы быть практичным. Это интересное упражнение, чтобы понять, как код справляется намного лучше, чем это. Подсказка: он имеет много общего с данными в этой проблеме.
Промышленно-силовые решатели несравнимо более сложны и сложны. Я был приятно удивлен, насколько хорошо эта простая маленькая программа сделала на небольших проблемах! Ему повезло.
Но для N = 15 этот простой подход безнадежен. Он быстро находит обложку с 18 элементами, но не делает видимого прогресса в течение как минимум часов. Внутренне он все еще работает с наборами needed, содержащими сотни (даже тысячи) элементов, что делает тело solve() довольно дорогостоящим. Он все еще имеет 2 ** 10 - 2 = 1022 коротких строк, и 1022-select-16 составляет около 6e34. Я не ожидаю, что это явно поможет, даже если этот код будет ускорен на миллион.
Было интересно попробовать: -)
И небольшая перезапись
Эта версия работает как минимум в 6 раз быстрее при полном запуске N = 12, просто отсекая бесполезные поиски на один уровень раньше. Также ускоряет инициализацию и сокращает использование памяти путем изменения наборов 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)