8

材料のセットとしてのレシピを考えて、私は一週間分の食事を作る最小限の材料を見つけようとしています。これは、レシピの数がNで、M = 7の場合、上記の問題に変換されます。

eg. if the initial sets are [{1,2}, {2,3}, {1,2,3}, {1}, {2}], and M=3
The minimal union is {1,2}.

私はこれを解決するための高レベルのアプローチを探しています。これはBFSに減らすことができると思いますが、他のアプローチでも最適化できるかどうかを確認したいと思います。

注：カーディナリティが同じであるようなセットが複数存在する場合があります。

4

1 に答える 1

8

この問題はMINIMUMk-UNIONとして知られており、次のようにNP困難です。

したがって、入力のサイズが多項式である時間内に実行される、それを解決するためのアルゴリズムを誰も知りません。

あなたの場合、おおよその解決策を喜んで受け入れるでしょう。つまり、材料の小さな結合を含むレシピのコレクションですが、必ずしもそのような最小のコレクションである必要はありません。したがって、欲張りアルゴリズムを試してみることをお勧めします。各段階で、ユニオンのサイズを最小化するレシピを追加することにより、レシピのコレクションを繰り返し構築します。Pythonでのナイーブな実装は次のとおりです。

def small_union(sets, k):
    """
    Choose `k` elements from `sets` and return their union.  Attempt
    to return a fairly small union using a greedy approach.

    >>> small_union([{1,2}, {2,3}, {1,2,3}, {1}, {2}], 3)
    set([1, 2])
    >>> small_union([{1,2}, {2,3}, {3,4}, {1,4}], 3)
    set([1, 2, 3, 4])
    """
    union = set()
    for _ in xrange(k):
        s = min(sets, key = lambda s: len(s | union))
        sets.remove(s)
        union |= s
    return union
于 2012-09-14T12:49:33.147 に答える