0

我有一组节点，每个节点包含 0 个或多个点。节点之间存在重复点，但每个节点可能包含该节点唯一的点。

例如：

  • 节点 A
    • 第 1 点
    • 第 2 点
    • 第 3 点
  • 节点 B
  • 节点 C
    • 第 1 点
    • 第 4 点
  • 节点 D
    • 第 2 点

等等

是否有一种算法或方法可以找到包含最多点数的最少节点数，直至特定限制？

在上面的例子中，如果我需要 4 个唯一点，我会得到节点 A 和节点 C，或节点 A 和节点 D。

目前，我正在通过按点数（即节点 A、节点 C、节点 D）对节点列表进行降序排序并丢弃没有点的节点（节点 B）来解决此问题。然后，我将遍历该节点列表，计算唯一点（并记录查看的节点），直到达到定义的唯一点阈值。因此，在上面的示例中，我的结果将是节点 A 和节点 C。

对于它的价值，我在 Javascript 中执行此操作，但我认为我的问题更多是“如何解决问题”而不是与特定语言相关。道歉，如果这是不正确的地方张贴。

4

2 回答 2

1

据我所知，没有限制，减少Set Cover到您的问题应该是微不足道的。您的限制未指定，因此它也可以跨越所有可能的点。因此，蛮力是唯一可行的选择。请注意，即使进一步指定限制，我仍然猜测它是 NP 完全的。

排序不应该解决问题：排序后的前 n 个节点可能有许多重复点，这使得包含每个点较少的节点“更好”。

于 2016-10-12T16:48:06.220 回答
0

您可以构建所有可能的组合并对值求和，过滤目标值并将结果集排序为所需的约束。

以上面的项目作为结果。

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; }

于 2016-10-12T17:09:18.440 回答