Algoritmo per trovare la massima copertura delle sequenze non sovrapposte.(Cioè, l'intervallo ponderato pianificazione prob.)

Question

Ho una domanda molto simile a Intervallo ponderato Problema di pianificazione . Questo è un caso speciale del Problema di pianificazione dell'intervallo .

@ @ J_Random_Hacker's Risposta, sotto, è, infatti, la soluzione nota al problema della pianificazione dell'intervallo ponderato, con una complessità in tempo di O(N log(N)).

Answer 1

Ecco un O (Nlog N) -Time, O (N) -Space Algoritmo. Innanzitutto, ordina la serie di tuple con la loro posizione di partenza se non sono già in questo ordine. Assumerò indici di array a zero basati su zero.

Chiamiamo la posizione iniziale della tupla Ib (i) e la posizione finale e (i), in modo che la sua lunghezza totale sia E (i) - B (i) + 1. Definiamo anche una funzione successiva (I) Ciò restituisce la posizione all'interno dell'elenco delle tuple della prima tupla che può apparire sul lato destro della tupla I. Si noti che il prossimo (i) può essere calcolato in o (log n) tempo con una ricerca binaria: tenere tutte le posizioni di inizio della tupla B (I) in un array b [] e cerca il primo J nel sottoarray B [ I + 1 .. N-1] Avere B [J]> E (i).

Definiamo f (i) per essere la copertura massima di qualsiasi set di tuple non sovrapplicazione che inizia a o dopo tupla I. Poiché Tuple I stesso è in questo set ottimale o no, abbiamo:

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

.

Abbiamo anche le condizioni del boundary f(n) = 0.

chiaramente la più grande copertura possibile è data da f (0). Questo è facilmente calcolato. 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]);
    }
}

.

Il ciclo in generazione calc() funziona n volte e ogni iterazione fa una chiamata O (log n) alla funzione di ricerca binaria upper_bound().

Possiamo ricostruire un set effettivo di questa dimensione calcolando sia gli ingressi a max () per f (0), vedere quale ha effettivamente prodotto il massimo, registrazione se implica la presenza o l'assenza di tupla 0, e quindi ricorrendo per gestire il resto (corrispondente a entrambi f (Avanti (0)) o F (1)). (Se entrambi gli ingressi sono uguali, ci sono molteplici soluzioni ottimali e possiamo seguire uno.)

Answer 2

L'algoritmo sottostante funziona recuperando ricorsivamente il più grande set non sovrapposto che ciascun elemento è il membro più a sinistra e quindi restituire quello con la più grande copertura.Vedi Commenti nel codice.

implementato in PHP.Puoi testarlo qui http://viper-7.com/xowtrf

Penso che la complessità di questa algoritmo sia O(2^N) o O(N^2) con la cache, sentiti libero di lasciare un commento se non sei d'accordo.

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

.