-3

以下に実際の例を示します。

としましょうm = 4：

// the sets for reuniting
Set1 = { 5 , 1 , 2 }
Set2 = { 2 , 6 , 3 }
Set3 = { 7 , 8 , 4 }
Set4 = { 4 , 9 , 10}

// the set I need to form
Set m+1: Set5 = { 1 , 2 , 3 , 4 }

インデックスのセットを見つける必要A = { 1, 2, 3 }がU (Seti)あります。基数は最小でなければなりません。Set5iAA

4

2 に答える 2

2

あなたの質問を正しく理解していれば、

これは NP 困難なセット カバー問題です。

結果として、最適かつ貪欲なアルゴリズムは存在しません。貪欲な次善のアプローチを示す記事を確認してください。

于 2011-12-19T10:21:04.160 に答える
0

問題を正しく理解した場合は、set5をカバーするセットのインデックスを返す擬似コードを次に示します。

setTmp = set5
A = {}
foreach i:
  if (seti intersect setTmp) is not empty then
    setTmp = setTmp  \ setI
    A.add(i)
return A

これは貪欲なアプローチであり、Aが最小であることを保証するものではないことに注意してください

于 2011-12-19T10:13:54.027 に答える