python - 查找满足特定约束的子集

Question

我有一组变量S，以及一个在S 上定义的 boolean 函数f，如下所示:

f(x₁, x₂, ... x_n) = True iff f(x_i, x_j) = True ∀ 1 ≤ i ≤ n ∀ 1 ≤ j ≤ n，n> 1，否则为 False。

f(a, b) 是已知的，f(a, a) 在 S 中为真 ∀ a, b。

如果有人能帮助我设计一个快速算法，该算法可以返回 S 的所有子集，f 返回 True，我将不胜感激。

例如，令S = [a, b, c] 和f(a, b) = f(b, c) = f(a, c) = 真。然后算法应该返回 [[a, b], [a, c], [b, c], [a, b, c]]。

我想到了四种改进暴力搜索的策略:

1) f 的参数顺序无关紧要。

2) 使用 f(a, a) 为真且 f(x_i, x_j) = f(x_j, x_i) 所以只有 i < j 需要检查。

2) 使用 f(x₁, x₂, ... x_n+1) = f(x₁, x₂, ... x _n) ∧ (f(x_i, x_n+1) ∀ 1 ≤ i ≤ n) 其中∀表示迭代连词。

3) 注意 2) 意味着如果 f(x₁, x₂, ... x_n) 返回 False，然后 f(x₁, x₂, ... x_n+Δ) 也一样，可能会减少解决方案空间。

4) 一旦 f(x_i, x_j) 对于某些 i, j 为假，就立即返回 False。

如果你想写一些代码，如果你能用python给出，我将不胜感激。

非常感谢。

Answer 1

双参数函数f(a, b)可以看作是S上的对称自反关系，可以看作是无向图。

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

从那里，您最终会到达 clique problem不幸的是，结果证明它是 NP 完全的。换句话说，不太可能存在快速算法。