3

C# でデジタル ファウンテンシステムを作成しています。このシステムの一部は、整数のセットを作成します。作成するセットの組み合わせを見つけて、1 つのアイテムだけのセットを残すことができるようにする必要があります。これを行う最速の方法は何ですか?

Set A: 1,2,3,4,5,6
Set B: 1,2,3,4,6
Set C: 1,2,3
Set D: 5,6

Solutions:
A - B => 5
A - (C + D) => 4

すべての組み合わせを見つける必要はありません。できるだけ多くの一意の数字を見つけることができれば十分です。これを利用して、より効率的なアルゴリズムを作成できる可能性があります。

忘れていた重要なポイント: 事前にセット数がわからないため、1 つずつ追加し、必要な数がすべて見つかったかどうかを毎回判断する必要があります。したがって、アルゴリズムは、新しいセットが追加されたときに段階的に実行できるものでなければなりません。

注意 C# のソリューションはボーナス マークを取得します ;)

4

1 に答える 1

1

貪欲なセット カバー ( http://en.wikipedia.org/wiki/Set_cover_problem ) アルゴリズムを使用する何らかの変更によって、いくつかの優れたソリューションが得られると思います。

[疑似コード]そう：

1. sort sets by size descending
2.
foreach set in sets do:
  uncovered = set.size
  while uncovered > 1
    current_set = the biggest set that covers no more than (uncovered - 1) and was not used before to cover set
    uncovered = uncovered - covered_by_set(set)
    collect current_set to some array
  end
end

編集：

  • 最後のセットの foreach ループを省略できます
  • これにより、セットごとに複数の解が得られることはありません (これを修正するには、問題を直接セット カバーの問題に変更し、貪欲なセット カバーを使用します)。たとえば、[1,3,4] を配列する場合は、サイズが 2 のすべてのサブセットに対する SCV 問題の解: [1,3]、[1,4]、[3,4]。それは問題をより複雑にするでしょう
  • あなたが考えるかもしれない別の方法は進化アルゴリズムです（ここでの表現は非常に単純になり、指定された数をビットとして扱い、フィットネス関数は1に近づくはずです）、それでも計算後に新しいセットを追加する問題は解決しません（おそらく最後の問題からの最良の集団を持っている場合、新しいセットを追加した後、染色体に新しい場所を追加するだけです)
于 2010-10-04T13:35:58.203 に答える