algorithm - 找到最小基组的算法？

Question

假设我们有N个集合 {  x ₁ , x ₂ , x ₃ , ..., x _N  }。

这N个集合的“基础”是M个集合 {  y ₁ , y ₂ , y ₃ , ..., y _M  } 的集合，使得 {  x ₁ , x ₂ , x ₃ , ..., x _N  } 中的每一个是{ y ₁ , y ₂ , y ₃ , ..., y _M  }的某种组合的并集 。

我怎样才能找到一个“最小”的基础，即M最小的基础？

Answer 1

想到的一个类似问题是分别找到向量空间的基础或找到最小生成集。

由于集合的数量以及所有可能元素的宇宙是有限的数字，我们可以将每个集合重写为这样的向量（假设整数作为集合内的元素）：

{ 1, 2, 5 } => ( 1, 1, 0, 0, 1, 0 , ... )
{ 4 }       => ( 0, 0, 0, 1, 0, ... )

所有向量x_is 的集合现在形成了G所有集合的全域的（平凡的）生成集x_i。

您搜索最小的生成器。为此，我们必须从向量集中消除所有线性依赖关系G。一种天真的方法是检查所有带有元素的三元组G是否满足以下条件（x,y,z向量G和k,l,m数字）：

  k * x + l * y  + m * z == 0

如果满足条件，我们消除这三个向量中的一个。（哪一个并不重要）。

这种简化的向量集（及其各自的集合）构成了您的集合的基础。

^{上述参数的一个要求是，您允许将集合差异作为生成集合的操作。}

Answer 2

这个问题是NP完全问题。