6

如果您有一组范围，例如以下简单示例...

[
    [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]].

在我的脑海中，我可能会尝试将每个范围转换为一个图节点，连接相交的节点，并找到最大的全连接图。

我也在反复思考从一开始就开始，继续建立一个相交范围的列表，每个范围都有一个运行的交点来检查——直到你碰到一个不相交的元素，然后开始一个新的列表。继续根据现有交叉点检查每个项目。但是我不确定这是否完整。

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

更新：

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

另请参阅：http ://en.wikipedia.org/wiki/Maximum_clique /在图中查找所有完整的子图

更新 2

在这里找到了这个问题的 NP-hardness 和 NP-completeness 的一个很好的证明：http ://www.cs.bris.ac.uk/~popa/ipl.pdf

看起来这是该行的结尾。对不起各位！我将使用足够好的贪婪近似值。谢谢。

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

4

2 回答 2

16

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

  1. 我们有一组有限的实数范围，比如n：[A 1 , B 1 ], [A 2 , B 2 ], ..., [A n , B n ]，其中 A i ≤ B i。

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

在您的示例中，这将是：12+、14+、15+、17+、20+、21-、22-、25-、27-、62+、64+、65-、70-、80-

  1. 初始化curOverlap和maxOverlap归零。

  2. 遍历列表，curOverlap每个 + 递增，每个 - 递减。maxOverlap = max(curOverlap, maxOverlap)在每个增量上设置。

继续您的示例：
val, cur, max
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- 如果您有重复的值，请在每个值的减号之前计算加号，以便您包含在单个点重叠的范围。

于 2013-02-25T02:32:12.950 回答
3

这是 Dave 提出的解决方案的 Java 实现：

public static List<Range> getMaxIntersectingSubset(List<Range> ranges) {
    // First, we collect "a sorted list of the starting and ending points".
    // We're sorting such that all lower bounds come first
    List<Bound> intersections = Arrays.stream(ranges)
        .flatMap(arr -> Stream.of(Bound.ofLowerBound(arr[0]), Bound.ofUpperBound(arr[1])))
        .sorted(Comparator
            .comparing(Bound::value)
            .thenComparing((a, b) -> Boolean.compare(!a.isLowerBound(), b.isLowerBound())))
        )
        .collect(Collectors.toList());

    long curOverlap = 0;
    long maxOverlap = 0;
    List<Integer> indexes = new ArrayList<>();

    // Then we iterate the list, searching for the highest overlap
    for (int i = 0; i < intersections.size(); i++) {
        Bound intersection = intersections.get(i);
        curOverlap += (intersection.isLowerBound() ? 1 : -1);
        if (curOverlap > maxOverlap) {
            maxOverlap = curOverlap;
            indexes.clear();
            indexes.add(i);
        }
        else if (curOverlap == maxOverlap) {
            indexes.add(i);
        }
    }

    return indexes.stream()
        .map(index -> Range.of(intersections.get(index).value(), intersections.get(index + 1).value()))
        .collect(Collectors.toList());
}

public class Bound {

    private final int value;
    private final boolean lower;

    private Bound(int value, boolean lowerbound) {
        this.value = value;
        this.lower = lowerbound;
    }

    public static Bound ofLowerBound(int value) {
        return new Bound(value, true);
    }

    public static Bound ofUpperBound(int value) {
        return new Bound(value, false);
    }

    public int value() {
        return this.value;
    }

    public boolean isLowerBound() {
        return this.lower;
    }
}

public class Range {

    private final int start;
    private final int end;

    private Range(int start, int end) {
        if (start > end) {
            throw new IllegalArgumentException("start > end");
        }
        this.start = start;
        this.end = end;
    }

    public static Range of(int start, int end) {
        return new Range(start, end);
    }

    public int start() {
        return this.start;
    }

    public int end() {
        return this.end;
    }
}

这些是一些测试集：

  1. 从这个 Stackoverflow 问题

    int[][] ints = {
    { 1, 100 },
    { 30, 95 },
    { 10, 60 },
    { 15, 25 },
    { 33, 66 },
    { 20, 50 },
    { 51, 100 },
    { 25, 70 }
};

    根据上述问题的OP，结果应该是[ 30, 55 ]。提供的代码输出此结果。然而，还有另一个重叠，虽然不那么广泛。请参阅下面的图片。

    测试用例 #1a

    测试用例 #1b

  2. 这个问题的 OP 提到了这个列表：

    int[][] ints = {
    { 12, 25 },
    { 14, 27 },
    { 15, 22 },
    { 17, 21 },
    { 20, 65 },
    { 62, 70 },
    { 64, 80 }
};

    在这里，输出是[ 20, 21 ]。这与下图相符：

    测试用例#2示意图

于 2020-09-15T12:50:56.527 回答