これで問題が解決するわけではありませんが (十分に速くはありません)、多くのアイデアが得られず、他の誰かがここで構築するのに役立つ何かを見つけるかもしれません。
これは短い純粋な 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 要素未満になることはありません!)。それもまったく素朴に行われた場合、残りの 254 個の 8 要素サブセットすべてを (「すべて 0」および「すべて 1」の文字列に) 追加する必要があり、254-choose-8 は約 3.8e14 です。1.2e77 よりもはるかに小さいですが、それでも大きすぎて実用的ではありません。コードがそれよりもはるかにうまく機能する方法を理解することは、興味深い演習です。ヒント: これは、この問題のデータに大きく関係しています。
工業用強度のソルバーは、比類のないほど高度で複雑です。この単純な小さなプログラムが、小さな問題のインスタンスに対してどれほどうまく機能するかに、私は嬉しい驚きを感じました! ラッキーになりました。
しかし、N=15 の場合、この単純なアプローチは絶望的です。18 要素のカバーをすばやく見つけますが、少なくとも数時間は目に見える進歩がありません。内部的には、まだneeded数百 (場合によっては数千) の要素を含むセットで動作しているため、本体がsolve()非常に高価になります。まだ 2**10 - 2 = 1022 個の短い文字列を考慮する必要があり、1022-choose-16 は約 6e34 です。このコードが 100 万倍高速化されたとしても、目に見えて役立つとは思いません。
でも、やってみるのは楽しかったです:-)
そしてちょっと書き直し
このバージョンは、完全な N=12 実行で少なくとも 6 倍高速に実行されます。無駄な検索を 1 レベル早くカットするだけです。また、初期化を高速化し、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)