javascript - 在 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 个节点可能有很多重复点，这使得包含每个点数较少的节点“更好”。