我有一组节点,每个节点包含0个或更多点节点之间存在重复点,但每个节点可能包含该节点唯一的点。
例如:
节点A
第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个节点可能有许多重复的点,因此“更好”地包括每个点较少的节点。

08-25 10:35
查看更多