Алгоритм поиска максимального покрытия непересекающихся последовательностей.(То есть, проблема взвешенного интервального планирования.)

Question

У меня вопрос, очень похожий на алгоритм поиска самых длинных непересекающихся последовательностей.

Единственное отличие от связанного вопроса состоит в том, что вместо поиска набора непересекающихся кортежей, представляющих самая длинная последовательность, мне нужно найти набор непересекающихся кортежей, представляющих максимальный охват, под этим я имею в виду сумма длин кортежей является максимальным (а длина кортежа существование last - first + 1 учитывая определение кортеж в следующем предложении).

Я представляю свои кортежи иначе, чем связанную проблему.Вместо (starting index, length), я представляю свои кортежи как (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)).

Answer 1

Вот O(nlog n)-время, O(n)-пространство алгоритм.Сначала отсортируйте массив кортежей по их начальной позиции, если они еще не расположены в этом порядке.Я предполагаю, что индексы массива начинаются с нуля.

Назовем начальную позицию кортежа i b(i) и конечную позицию e(i), чтобы его общая длина была e(i) - b(i) + 1.Также давайте определим функцию next(i), которая возвращает позицию в списке кортежей первого кортежа, который может появиться в правой части кортежа i.Обратите внимание, что next(i) можно вычислить за время O(log n) с помощью двоичного поиска:просто сохраните все начальные позиции кортежа b(i) в массиве b[] и найдите первый j в подмассиве b[i+1 ..n-1], имеющий b[j] > e(i).

Определим f(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).Это легко вычислить.В псевдо-С++:

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 раз, и каждая итерация выполняет один вызов O(log n) функции двоичного поиска. upper_bound().

Мы можем реконструировать реальный набор такого размера, вычислив оба входных сигнала для max() для f(0), проверив, какой из них на самом деле дал максимум, зафиксировав, подразумевает ли это наличие или отсутствие кортежа 0, а затем рекурсивно обработать остаток (соответствующий f(next(0)) или f(1)).(Если оба входных параметра равны, то существует несколько оптимальных решений, и мы можем следовать любому из них.)

Answer 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>";