4

特定の問題に遭遇し、そのためのアルゴリズムを探していました。解決すべき問題は以下のとおりです。

以下のような組み合わせがあるとしましょう

1 - 3 - 5

1 - 4 - 5

1 - 8 - 5

2 - 4 - 5

3 - 4 - 5

2 - 4 - 7

これらの組み合わせは、特定のセットから生成されました。この特定のケースでは、

{1},{3,4,8},{5}

{2,3}、{4}、{5}

{2}、{4}、{7}

私がやりたいのは、これらの組み合わせからセットを再作成することです。これらの組み合わせには、複数のソリューションがあることを知っています。

最初の解決策

{1}、{3、4、8}、{5}

{2, 3}, {4}, {5}

{2}、{4}、{7}

2番目のソリューション

{1}、{3、8}、{5}

{1, 2, 3}, {4}, {5}

{2}、{4}、{7}

3番目のソリューション

{1}、{3、4、8}、{5}

{3}、{4}、{5}

{2}、{4}、{5、7}

しかし、最終的な (最適な) 解決策は、可能な限りセット数の少ないものか、セット数に関してすべてが同等である場合のランダムなものです。

そのような問題のアルゴリズムは存在しますか? この種の問題を扱ってきた人が私にヒントを与えることができれば幸いです。

編集:私が探しているのは、n-ary積(Nのデカルト積)の分解であるように見えます

編集: このトピックについてさらに調査した結果、この問題は「グラフ理論」で「最小クリークカバー」問題として知られていることがわかりました

よろしく、バズ

4

1 に答える 1

1

これは実際には答えではなく、より拡張されたコメントです。あなたの「圧縮された表現」は、実際にはスペースをまったく節約しません。

保存する非圧縮表現では、次のようになります。

  • 各グループは 3 つのシンボルで構成されているというルール。と
  • 18個の（あなたの例では）シンボル。

これは 1R+18S に格納できます (R はルールを格納するために必要なスペース、S はシンボルを格納するために必要なスペースです)。

圧縮されたはずの表現では、次のものを保存する必要があります。

  • 各グループは 3 セットのシンボルで構成されているというルール。
  • 各セットのシンボル; と
  • 各セットを次のセットから区切る別の記号。

最初の「圧縮された」表現では、1R + 12S + 8Dを数えます（Dは1つの区切り文字を格納するために必要なスペースです）。S==D の場合、これは 1R+20S であり、圧縮されていない表現よりも多くなります。

他の 2 つの「圧縮された」表現では、1R+12S+8D と 1R+12S+8D を同じように数えます。

この非圧縮があなたの提案の本質的な特徴なのか、それともあなたが選んだ例の偶発的な特徴なのか、私にはわかりません。

つまり、あなたがそれを書くとき

組み合わせた要素の数は実際には N です

いくつかの組み合わせには 3 つの要素があり、他の組み合わせには 4 つ、他の組み合わせには 2 つまたは 5 つなどがありますか?

質問を明確にすることをお勧めします。

編集: @bazeusz: セットのデカルト積を探しているようです。

于 2010-09-24T16:54:44.853 に答える