Javascriptでほとんどのポイントを持つノードを最も少なく見つける最適な方法

Question

私はそれぞれが0以上のポイントを含むノードのセットを持っています。ノード間に重複したポイントがありますが、各ノードにはそのノードに固有のポイントが含まれている場合があります。例えば

：

• ノードA
  • ポイント1
  • ポイント2
  • ポイント3
• ノードB
• ノードC
  • ポイント1
  • ポイント4
• ノードD
  • ポイント2

等

見つけるアルゴリズム又は方法があります。共同するノードの数が最も少ない最も多くのポイントを特定の限度まで獲得していますか？上記の例では

は、私は4つのユニークなポイントを必要に応じて、私は現在、ノードAとノードC、またはノードAとノードD

になるだろう、私は内のノードのリストをソートすることにより、この問題を解決しています（ノードA、ノードC、ノードD）とポイントを持たないノード（ノードB）を廃棄することによって、降順に並べ替えることができます。私は、ユニークなポイントの定義されたしきい値を打つまで、ユニークなポイントを数える（そして、ノードが見ているものを記録する）ノードのリストを繰り返しています。上記の例では、ノードAとノードCの結果が返されます。

私はJavascriptでこれをやっていますが、私の質問は「問題を解決する方法」です。特定の言語には関係しません。これが間違った投稿場所である場合はお詫び申し上げます。

Answer 1

私が見ることのできるところでは、制限なしで、Set Coverの削減は簡単です。あなたの制限は指定されていないので、すべての可能な点に及ぶ可能性があります。そのため、ブルートフォースだけが実行可能な選択肢です。制限をさらに指定する必要がある場合でも、私はまだそれがNP完全であると推測します。

ソート後に最初のn個のノードには重複したポイントがたくさんあり、ポイントが少ないノードを含めると「良い」ことができます。

Answer 2

すべての可能な組み合わせを構築し、値を合計し、ターゲット値をフィルタリングし、結果セットを必要な制約に並べ替えることができます。

結果として上位項目を取ります。

var array = [3, 0, 2, 1], 
 
    i, 
 
    result = [], 
 
    values, 
 
    sum; 
 

 
// filter zero values 
 
array = array.filter(function (a) { 
 
    return a; 
 
}); 
 

 
// generate all possible combination and build sum 
 
for (i = 0; i < 1 << array.length; i++) { 
 
    sum = 0; 
 
    values = array.filter(function (a, j) { 
 
     if (i & (1 << j)) { 
 
      sum += a; 
 
      return true; 
 
     } 
 
    }); 
 
    // add only relevant items to the result set 
 
    sum >= 4 && result.push({ values: values, sum: sum }); 
 
} 
 

 
// sort by priority 
 
result.sort(function (a, b) { 
 
    return a.values.length - b.values.length || a.sum - b.sum; 
 
}); 
 

 
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }