在Javascript中使用最多的点找到最少的节点的最佳方法

Optimum way to find fewest nodes with most points in Javascript

本文关键字：节点 方法 最佳 Javascript      更新时间：2023-09-26

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

例如:

  • 节点
    • 点(1
    • 2
    • 3
  • 节点B
  • 节点C
    • 点(1
    • 点4
    • D
  • 节点
    • 2

等。

是否存在一种算法或方法来找到包含最多点的最少节点数量，达到特定限制?

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

目前，我通过按点的数量(即节点A，节点C，节点D)降序排序节点列表并丢弃没有点的节点(节点B)来解决这个问题。然后我迭代该节点列表，计算唯一点(并记录所查看的节点)，直到我达到定义的唯一点阈值。因此，在上面的例子中，我的结果将是节点A和节点c。

为了它的价值，我在Javascript中这样做，但我认为我的问题更多的是"如何解决问题"，而不是与特定的语言相关。

在我看来，没有限制，减少Set Cover对你的问题应该是微不足道的。你的极限没有指定，所以它也可以张成所有可能的点。因此，暴力是唯一可行的选择。请注意，即使进一步指定极限，我仍然猜测它是np完全的。

排序不应该这样做:排序后的前n个节点可能有许多重复的点，使得包含每个点较少的节点"更好"。

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

以上面的项为结果。

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

相关文章：