コンテナーCのセットを参照するとします。{c1,c2,c3....cn}これらのコンテナーのそれぞれには、整数の有限セットが含まれています{i1,i2,i3...im}。さらに、整数が複数のコンテナーに存在する可能性があるとします。整数の有限集合 が与えられたとき、 のすべての整数を含むS {s1,s2,s3...sz}の最小サブセットのサイズを見つけます。CS
それぞれ数百の整数を持つ数千のコンテナーが存在する可能性があることに注意してください。したがって、ブルートフォースはこの問題を解決するのに時間がかかります。
Greedyアルゴリズムを使用して問題を解決しようとしました。つまり、セット内の整数の最大数を持つコンテナーを選択するたびに、S失敗しました!
この問題の高速なアルゴリズムを提案できる人はいますか?
これはよく知られているセット カバーの問題です。これはNP 困難であり、実際、その決定バージョンは正規の NP 完全問題の 1 つであり、 Karp の 1972 年の論文に含まれる 21 の問題の 1 つであったため、効率的なアルゴリズムは知られていません。問題に対する特別な余分な構造を特定できない限り、おおよその結果に満足する必要があります。つまり、C の部分集合で S を含む和集合であり、これは必ずしも C のそのような部分集合の最小値であるとは限りません。
貪欲なアルゴリズムはおそらくあなたの最善の策です。それは、そのような最小のコレクションのサイズの O(log |C|) 倍以下のセットのコレクションを見つけます。
あなたは貪欲なアルゴリズムを機能させることができなかったと言っています。これはおそらく、正しく実装できなかったことが原因だと思います。アルゴリズムを次のように記述します。
セットS内の整数の最大数を持つコンテナを選択するたびに
しかし、通常の貪欲なアルゴリズムのルールは、各段階で、これまでに選択されたどのコンテナにも含まれていない集合 S 内の整数の最大数を持つコンテナを選択することです。