查找范围的最大相交子集

  • Z时代
  • 2024-01-10
  • 分类：问答

如果您有一组范围，例如下面的简单示例…

[
    [12, 25], #1
    [14, 27], #2
    [15, 22], #3
    [17, 21], #4
    [20, 65], #5
    [62, 70], #6
    [64, 80]  #7
]

…如何计算 最大相交的子集 （不确定如何表达，但我的意思是“相交并具有最高基数的范围的子集”）并确定相交程度（该子集中范围的基数） ）？

从逻辑上讲，我可以解决这个问题，并且可以将其转换为简单的算法。在列表下方，我们看到1-5相交，而5-7相交，＃5相交。

我想要的结果只是子集，因为这给了我关于基数的信息，而且只要它们全部相交，我就可以轻松地计算出集合的交集。在上面的示例中，它将为[[14, 27],[15,

22],[12, 25],[17, 21],[20, 65]]。

我可能会尝试将每个范围转换为一个图形节点，将相交的部分连接起来，然后找到最大的全连接图。

我还反复考虑要从头开始，继续建立相交范围的列表，并在每个相交范围上运行一个相交的区域以进​​行检查-

直到您找到一个不相交的元素，然后开始一个新列表。继续对照现有交叉口检查每个项目。但是我不确定这是否完成。

我可以尝试实现某些东西（语言是ruby FWIW），但是我很想听听其他人如何解决这个问题，以及最有效，最优雅的方法是什么。

我认为这是最大派系问题的一个具体案例，这是NP难题，因此实际上很困难。对于近似值/实际使用的建议将不胜感激！

另请参阅：http :

//en.wikipedia.org/wiki/Maximum_clique

/ 查找图中的所有完整子图

在此找到了有关此问题的NP硬度和NP完整性的很好证明： http :

//www.cs.bris.ac.uk/~popa/ipl.pdf

看起来这是行的结尾。抱歉！我将使用足够好的贪婪近似进行工作。谢谢。

如答案中所述，我认为该论文没有描述这个问题……我们可能会根据范围在此处提供更多信息。

回答：

如果我对问题的理解正确，那么这并不是您所链接论文中描述的NP问题的一个实例。这是我对问题的理解以及多项式时间解。

  1. 我们给定了一组实数范围，例如n：[A1，B1]，[A2，B2]，…，[An，Bn]，其中Ai <= Bi。

  2. 创建起点和终点的排序列表，并按数字顺序排列，以指示该点是起点还是终点。

在您的示例中，该值为：12 +，14 +，15 +，17 +，20 +，21-，22-，25-，27-，62 +，64 +，65-，70-，80-

  1. 将curOverlap和maxOverlap初始化为零。

  2. 遍历列表，为每个+增加curOverlap，为每个-减少。在每个增量上设置maxOverlap = max（curOverlap，maxOverlap）。

要继续例如：

缬氨酸，CUR，最大

12，1，1

14，2，2

15，3，3

17，4，4

20，5，5

21，4，5

22，3，5

25，2,5

27，1，5

62，2，5

64，3，5

65，2，5

70，1，5

80，0，5

最大重叠值为5。如果您想知道最大重叠发生在何处，也可以存储与最大关联的val。在此示例中，这将为您提供20。然后遍历初始范围并找到包含20个范围的5个范围很简单。

-edit-如果您有重复的值，请在每个值的负号之前对正号进行计数，以便包括在单个点处重叠的范围。

以上是 查找范围的最大相交子集 的全部内容， 来源链接： utcz.com/qa/419281.html

回到顶部