一連の変数Sと、次のようにSで定義されたブール関数fがあります。
f (x 1 , x 2 , ... x n ) = True if f (x i , x j ) = True ∀ 1 ≤ i ≤ n ∀ 1 ≤ j ≤ n , n > 1, そうでなければ False.
f (a, b) は既知であり、f (a, a) はSの True ∀ a, bです。
fが Trueを返すSのすべてのサブセットを返すことができる高速なアルゴリズムを設計する際に、助けていただければ幸いです。
例として、S = [a, b, c] およびf (a, b) = f (b, c) = f (a, c) = True とします。次に、アルゴリズムは [[a, b], [a, c], [b, c], [a, b, c]] を返す必要があります。
ブルートフォース検索を改善するための 4 つの戦略を考えました。
1) fのパラメータの順序は関係ありません。
2) f (a, a) が True であり、f (x i , x j ) = f (x j , x i ) であることを利用して、i < j のみをチェックする必要があります。
2) f (x 1 , x 2 , ... x n +1 ) = f (x 1 , x 2 , ... x n ) ∧ ( f (x i , x n +1 ) ∀ 1 ≤ i ≤ n ) ここで、∀ は反復結合を表します。
3) 2) は、 f (x 1 , x 2 , ... x n ) が False を返す場合、f (x 1 , x 2 , ... x n +Δ ) も False を返し、解を減らす可能性があることを意味することに注意してください。スペース。
4) f (x i , x j ) が一部の i、j に対して false になるとすぐに False を返す。
何かコードを書きたい場合は、pythonで教えていただけるとありがたいです。
どうもありがとう。