algorithm - セットの最小基底セットを見つけるアルゴリズム?

Question

Nセット {  x ₁ , x ₂ , x ₃ , …, x N  }があるとし_ます。

これら のNセット_の「_基礎」_は 、  {  x ₁ , x ₂ , x ₃ , … , x _N }_のそれぞれが_ { y ₁ , y ₂ , y ₃ , …, y _M  }の組み合わせの和集合 。

Mが最小の基底を意味する「最小」基底を見つけるにはどうすればよいですか?

Answer 1

頭に浮かぶ同様の問題の 1 つは、ベクトル空間の基底を見つけること、または最小生成集合を見つけることです。

セットの数、つまり可能なすべての要素の宇宙は有限数であるため、各セットを次のようなベクトルとして書き換えることができます (セット内の要素として整数を仮定します)。

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

すべてのベクトル s のセットは、すべてのセットの宇宙のx_i(自明な) 生成セットを形成します。Gx_i

最小のジェネレーターを検索します。そのためには、ベクトル セットからすべての線形依存関係を排除する必要がありますG。単純なアプローチはG、次の条件 (x,y,zベクトルGおよびk,l,m数値) の要素を持つすべてのトリプルをチェックすることです。

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

条件が満たされた場合、これら 3 つのベクトルのうちの 1 つを削除します。（実際にはどちらでもかまいません）。

このような削減されたベクトルのセット (およびそれぞれのセット) は、セットのセットの基礎を形成します。

^{上記の引数の 1 つの要件は、セットを生成する操作としてセットの差を許可することです。}