当给定一些数字组时,我该如何找到覆盖所有数字的最小组合?限制是所选组不应重叠。
例如,给定三组数字(1,2),(2,3)和(3,4),我们可以选择(1,2)和(3,4),因为(2,3)是多余的。
对于(1,2),(2,3),(3,4),(1,4),我们有两个解决方案:(1,2),(3,4)或(1,4),(2,3)。
对于(1,2,3),(1,2,4)和(3,4),存在冗余,但没有解决方案。
我想到的算法(以G = (1,2),(2,3),(3,4),(1,4)为例)是:
例如,给定三组数字(1,2),(2,3)和(3,4),我们可以选择(1,2)和(3,4),因为(2,3)是多余的。
对于(1,2),(2,3),(3,4),(1,4),我们有两个解决方案:(1,2),(3,4)或(1,4),(2,3)。
对于(1,2,3),(1,2,4)和(3,4),存在冗余,但没有解决方案。
我想到的算法(以G = (1,2),(2,3),(3,4),(1,4)为例)是:
collect all the numbers from the groups x = (1,2,3,4)
for g in G:
x = remove g in x # x = (3,4)
find G' = (a set of (g' in (G - g))) that makes (G' + g = x) # G' = ((3,4))
if find (G' + g) return (G',g) # return ((1,2)(3,4))
我知道我的算法在性能方面存在很多漏洞,我猜想这可能是一个众所周知的问题。有什么提示可以解决这个问题吗?