寻找非重叠序列的最大覆盖算法（即加权区间调度问题）。

Question

寻找非重叠序列的最大覆盖算法（即加权区间调度问题）。

algorithmcomplexity-theorydynamic-programmingintervalsresource-scheduling

3

我有一个问题，它与算法查找最长不重叠序列非常相似。唯一的区别在于，我需要找到表示最大覆盖的非重叠元组集合，其中元组长度之和是最大的（元组长度是指根据下一句中元组的定义给出的last-first+1）。与链接问题不同的是，我以不同的方式表示我的元组。我把我的元组表示成(first, last)，例如，元组(3,7)表示数字集合[3,4,5,6,7]。（即使端点匹配，元组也可以重叠;例如，元组(2,6)和(6,8) 重叠，因此不能同时出现在解决方案中。）例如，考虑以下按first排序的元组集合： [(0,100), (2,50), (30,150), (60,95), (110,190), (120,150), (191,200)] 这里的最大集合将是 [(0,100), (110,190), (191,200)] ，其覆盖范围为101 + 81 + 10 = 192。（注意，此解决方案中的元组是非重叠的。）最简单的算法示例是什么？该算法的复杂度是多少？（如果可以在O（N）内解决这个问题，那将非常好，但我现在不知道是否可以。）补充：回顾一下，事实证明，我在这里提出的问题等价于加权区间调度问题。这是区间调度问题的一个特例。@j_random_hacker的答案实际上是已知的加权区间调度问题的解决方案，其时间复杂度为O（N log（N））。

- Dan Nissenbaum

3

关于将这个问题标记为“过于广泛” - 我注意到链接的问题和其他带有相同标签的问题同样“广泛”，但它们并没有被关闭。请问您需要翻译成哪种语言呢？ - Dan Nissenbaum

2个回答

2

下面的算法通过递归地检索最大的非重叠集合，使得每个元素都是最左边的成员，然后返回覆盖范围最大的集合。请参见代码中的注释。

使用 PHP 实现。您可以在此处进行测试 http://viper-7.com/xowTRF 我认为这个算法的复杂度是 O(2^N) 或 O(N^2)（如果使用缓存），如果您不同意，请随意发表评论。

$set = [[0,100], [2,50], [30,150], [60,95], [110,190], [120,150], [191,200]];
$GLOBALS['cache'] = array(); //cache for overlapping sub problems

function maximumSet($set) {

    if(count($set) === 1) {
        return $set;
    }

    $cache_key = [];

    foreach($set as $k) {
        $cache_key[] = implode($k,'.');
    }

    $cache_key = implode('_',$cache_key);

    if(isset($GLOBALS['cache'][$cache_key])) {
        return $GLOBALS['cache'][$cache_key];
    }

    $maximumResult = null;

    //for each element in the set,
    //get the largest non-overlapping set that the element is a member of
    //once all N sets have been computed, return the largest one
    foreach($set as $k => $element) {

        unset($set[$k]);

        //create a new set $copy, which contains the remaining elements that
        //do not overlap with $element            
        $copy = $set;

        foreach($set as $k2 => $element2) {
            if($element2[0] <= $element[1]) { 
                //element is considered non overlapping if its start 
                //is less than or equal to current element's end
                unset($copy[$k2]);
            }
            else break; //because the list is sorted we can break the 1st time
            //see a non-overlapping element
        }

        if(!empty($copy)) {
            //if there is at least one non-overlapping element
            //recursively get the maximum set
            $maximumSubset = maximumSet($copy);
            //prepend the current element to it
            array_unshift($maximumSubset,$element);
        }
        else {
            //otherwise the maximum non-overlapping set which contains this element
            //is the element itself                
            $maximumSubset = [$element];
        }

        //store the set in the results by coverage
        $coverage = getCoverage($maximumSubset);
        if(is_null($maximumResult) || $maximumResult['coverage'] < $coverage) {
            $maximumResult = [
                'coverage' => $coverage,
                'set' => $maximumSubset
            ];
        }
    }

    $GLOBALS['cache'][$cache_key] = $maximumResult['set'];
    return $maximumResult['set'];
}

function getCoverage($set) {
    $range = 0;
    foreach($set as $v) {
        $range += ($v[1] - $v[0]);
    }
    return $range;
}

$x = maximumSet($set);
print "<pre>";
print_r($x);
print "</pre>";

- FuzzyTree

几点建议：（1）你正在测试的条件（即$element2是否在$element结束之前开始）需要翻转以检查$element2是否在$element开始之前结束；（2）您从未添加位于$element右侧的元素；（3）如果您解决了这些问题，您的算法将是指数时间，例如，如果问题实例具有n个不重叠的区间，则maximumSet()最终将使用所有2^n-1个可能的非空子集调用。 - j_random_hacker

“$element2 排在 $element 后面”这个说法并不总是正确的——例如，假设 $k == 2 并且 $k2 == 1。（我不了解 PHP，但我猜 $k 和 $k2 是数组索引。） - j_random_hacker

请注意代码中的这两行：unset($set[$k]); $copy = $set;（unset 会从集合中移除元素）。由于 $set 是按照元素的起始时间排序的，$element2 总是在 $element 的后面。 - FuzzyTree

1

我还要补充一点，你添加的记忆化以及这个改动意味着该算法现在是多项式时间（至少是O(n^3)，但由于大小为n的集合复制可能会更多）。如果maximumSet()接受一个整数参数start，表示全局$set中开始查找的数组位置，而不是一个集合本身，则这个时间复杂度将更清晰（代码也更快！: )）。然后很明显它只能使用n个不同的参数值进行调用，并且每次调用只需要O(n^2)的非递归工作，总共为O(n^3)。 - j_random_hacker

还有一个想法 :) 预处理步骤实际上可以通过进行n个二分搜索而不是n个线性搜索在O(nlog n)时间内完成。这给了我一个总体O(nlog n)算法的想法 :) - j_random_hacker

显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- j_random_hacker · Accepted Answer

这里有一个时间复杂度为O(nlog n)，空间复杂度为O(n)的算法。首先，如果元组数组未按其起始位置排序，则按其起始位置进行排序。我们假设数组索引从零开始。

我们称元组i的起始位置为b(i)，结束位置为e(i)，因此其总长度为e(i)-b(i)+1。还让我们定义一个函数next(i)，它返回可以出现在元组i右侧的第一个元组在元组列表中的位置。请注意，可以使用二进制搜索在O(log n)时间内计算next(i)：只需将所有元组起始位置b(i)存储在数组b[]中，并在子数组b[i+1..n-1]中搜索第一个满足b[j]>e(i)的j。

让我们将f(i)定义为从元组i开始或之后开始的任何非重叠元组集的最大覆盖范围。由于元组i本身要么在这个最优集合中，要么不在，因此我们有：

f(i) = max(e(i) - b(i) + 1 + f(next(i)), f(i+1)) for 0 <= i < n

我们还有一个边界条件f(n) = 0。

显然，最大的覆盖范围由f(0)给出。这很容易计算。在伪C++中：

```c++ int maxCoverage = f(0); ```

int b[] = /* Tuple beginning positions, in nondecreasing order */;
int e[] = /* Tuple end positions */;
int n = /* Number of tuples */;

// Find the array position of the leftmost tuple that begins to the right of
// where tuple i ends.
int next(int i) {
    return upper_bound(b + i + 1, b + n, e[i]);
}

int maxCov[n + 1];    // In practice you should dynamically allocate this

// After running this, maxCov[i] will contain the maximum coverage of any
// nonoverlapping subset of the set of n - i tuples whose beginning positions
// are given by b[i .. n-1] and whose ending points are given by e[i .. n-1].
// In particular, maxCov[0] will be the maximum coverage of the entire set.
void calc() {
    maxCov[n] = 0;
    for (int i = n - 1; i >= 0; --i) {
        maxCov[i] = max(e[i] - b[i] + 1 + maxCov[next(i)], maxCov[i + 1]);
    }
}

calc()中的循环运行n次，每次迭代都会对二分搜索函数upper_bound()进行一次O(log n)调用。

我们可以通过计算f(0)的max()输入来重新构建这个大小的实际集合，看哪个产生了最大值，记录它是否意味着元组0的存在或不存在，然后递归处理剩余部分（对应于f(next(0))或f(1)）。（如果两个输入相等，则有多个最优解，我们可以随意选择一个。）