1

我有一组变量S和一个布尔函数fS上定义如下:

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 中给出它,我将不胜感激。

非常感谢。

4

1 回答 1

5

二元函数f(a, b)可以看作是 S 上的一个对称的自反关系,可以看作是一个无向图。

这样看来,当仅当且仅当形成一个完整的子图时f(x1, ..., xn)为真。{x1, ..., xn}

从那里,你最终遇到了集团问题,不幸的是,结果证明是 NP 完全的。换句话说,不太可能存在快速算法。

于 2012-07-04T17:49:11.060 回答