我有一组变量S和一个布尔函数f在S上定义如下:
f (x 1 , x 2 , ... x n ) = True 当且仅当f (x i , x j ) = True ∀ 1 ≤ i ≤ n ∀ 1 ≤ j ≤ n , n > 1,否则为 False。
f (a, b) 是已知的并且f (a, a) 是 True ∀ a, b in S。
我希望能在设计一个快速算法方面提供一些帮助,该算法可以返回S的所有子集,其中f返回 True。
例如,令S = [a, b, c] 和f (a, b) = f (b, c) = f (a, c) = True。然后算法应该返回 [[a, b], [a, c], [b, c], [a, b, c]]。
我想到了四种改进蛮力搜索的策略:
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 +Δ ) 也可以,可能会减少解空间。
4) 只要f (x i , x j ) 对于某些 i, j 为假,就立即返回 False。
如果您想编写一些代码,如果您能在 python 中给出它,我将不胜感激。
非常感谢。