Algorithmus zur Ermittlung der maximalen Abdeckung nicht überlappender Sequenzen.(Das heißt, das Weighted Interval Scheduling Prob.)

Question

Ich habe eine Frage, die sehr ähnlich ist Algorithmus zum Finden der längsten nicht überlappenden Sequenzen.

Der einzige Unterschied zur verknüpften Frage besteht darin, dass nicht die Menge nicht überlappender Tupel gefunden wird, die die darstellen längste Sequenz, muss ich den Satz nicht überlappender Tupel finden, die das darstellen maximale Abdeckung, womit ich das meine Summe der Tupellängen ist maximal (a Tupellänge Sein last - first + 1 angesichts der Definition von Tupel im nächsten Satz).

Ich stelle meine Tupel anders dar als das verknüpfte Problem.Anstatt (starting index, length), ich stelle meine Tupel dar als (first, last);zum Beispiel das Tupel (3,7) stellt die Menge der Zahlen dar [3, 4, 5, 6, 7].(Ein Tupel Überschneidungen ein anderes Tupel, auch wenn die Endpunkte übereinstimmen;d.h., (2,6) Und (6,8) Überlappung und daher können nicht beide in der Lösung vorkommen.)

Betrachten Sie als Beispiel den folgenden Satz von Tupeln, sortiert nach first:

[(0,100), (2,50), (30,150), (60,95), (110,190), (120,150), (191,200)]

Der maximale Satz wäre hier [(0,100), (110,190), (191,200)] mit einer Abdeckung von 101 + 81 + 10 = 192.(Beachten Sie, dass die Tupel in dieser Lösung sind nicht überlappend.)

Was ist ein Beispiel für den am wenigsten komplexen Algorithmus zur Lösung dieses Problems und wie komplex ist dieser Algorithmus?(Es wäre einfach toll, wenn das gelöst werden könnte O(N), aber ich weiß im Moment nicht, ob es sein kann.)

NACHTRAG: Im Nachhinein stellt sich heraus, dass die Frage, die ich hier stelle, dem entspricht Problem der gewichteten Intervallplanung.Dies ist ein Sonderfall des Problem bei der Intervallplanung.

Die Antwort von @j_random_hacker unten ist tatsächlich die bekannte Lösung für das Problem der gewichteten Intervallplanung mit einer zeitlichen Komplexität von O(N log(N)).

Answer 1

Hier ist ein O(nlog n)-Zeit, O(n)-Raum Algorithmus.Sortieren Sie zunächst das Tupel-Array nach ihrer Startposition, sofern sie nicht bereits in dieser Reihenfolge vorliegen.Ich gehe von nullbasierten Array-Indizes aus.

Nennen wir die Anfangsposition des Tupels i b(i) und die Endposition e(i), sodass seine Gesamtlänge e(i) - b(i) + 1 beträgt.Definieren wir außerdem eine Funktion next(i), die die Position innerhalb der Tupelliste des ersten Tupels zurückgibt, das auf der rechten Seite von Tupel i erscheinen kann.Beachten Sie, dass next(i) mit einer binären Suche in O(log n)-Zeit berechnet werden kann:Behalten Sie einfach alle Tupel-Anfangspositionen b(i) in einem Array b[] bei und suchen Sie nach dem ersten j im Subarray b[i+1 ..n-1] mit b[j] > e(i).

Definieren wir f(i) als die maximale Abdeckung jeder nicht überlappenden Menge von Tupeln, die bei beginnt oder danach Tupel i.Da Tupel i selbst entweder in dieser optimalen Menge ist oder nicht, gilt:

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

Wir haben auch die Randbedingung f(n) = 0.

Offensichtlich ist die größtmögliche Abdeckung durch f(0) gegeben.Das lässt sich leicht berechnen.In Pseudo-C++:

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]);
    }
}

Die Schleife calc() wird n-mal ausgeführt und jede Iteration führt einen O(log n)-Aufruf an die binäre Suchfunktion durch upper_bound().

Wir können eine tatsächliche Menge dieser Größe rekonstruieren, indem wir beide Eingaben für max() für f(0) berechnen, sehen, welche tatsächlich das Maximum erzeugt hat, aufzeichnen, ob dies das Vorhandensein oder Nichtvorhandensein von Tupel 0 impliziert, und dann eine Rekursion durchführen, um das zu verarbeiten Rest (entsprechend entweder f(next(0)) oder f(1)).(Wenn beide Eingaben gleich sind, gibt es mehrere optimale Lösungen und wir können einer von beiden folgen.)

Answer 2

Der folgende Algorithmus funktioniert, indem er rekursiv die größte nicht überlappende Menge abruft, in der jedes Element das am weitesten links stehende Mitglied ist, und dann diejenige mit der größten Abdeckung zurückgibt.Siehe Kommentare im Code.

In PHP implementiert.Hier können Sie es testen http://viper-7.com/xowTRF

Ich denke, die Komplexität dieses Algorithmus ist O(2^N) oder O(N^2) Wenn Sie mit dem Caching nicht einverstanden sind, können Sie gerne einen Kommentar hinterlassen.

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