Algorithme pour trouver une couverture maximale de séquences qui ne se chevauchent pas.(C'est-à-dire le problème de planification d'intervalles pondérés.)

Question

J'ai une question qui ressemble beaucoup à algorithme pour trouver les séquences les plus longues qui ne se chevauchent pas.

La seule différence avec la question liée est qu'au lieu de trouver l'ensemble des tuples qui ne se chevauchent pas et qui représentent le séquence la plus longue, je dois trouver l'ensemble de tuples qui ne se chevauchent pas et qui représentent le couverture maximale, j'entends par là le somme des longueurs de tuples est maximum (un longueur du tuple être last - first + 1 compte tenu de la définition de tuple dans la phrase suivante).

Je représente mes tuples différemment du problème lié.Au lieu de (starting index, length), je représente mes tuples comme (first, last);par exemple, le tuple (3,7) représente l'ensemble des nombres [3, 4, 5, 6, 7].(Un tuple chevauchements un autre tuple même si les extrémités correspondent ;c'est à dire., (2,6) et (6,8) chevaucher et ne peuvent donc pas apparaître tous les deux dans la solution.)

À titre d'exemple, considérons l'ensemble de tuples suivant, triés par first:

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

L'ensemble maximal ici serait [(0,100), (110,190), (191,200)] avec une couverture de 101 + 81 + 10 = 192.(Notez que les tuples de cette solution sont sans chevauchement.)

Quel est un exemple de l’algorithme le moins complexe pour résoudre ce problème, et quelle est la complexité de cet algorithme ?(Ce serait tout simplement génial si cela pouvait être résolu O(N), mais je ne sais pas pour le moment si c'est possible.)

ADDENDA: Rétrospectivement, il s'avère que la question que je pose ici équivaut à la problème de planification d'intervalles pondérés.Il s'agit d'un cas particulier du problème de planification d'intervalles.

La réponse de @j_random_hacker, ci-dessous, est, en fait, la solution connue au problème de planification d'intervalles pondérés, avec une complexité en temps de O(N log(N)).

Answer 1

Voici un O(nlog n)-temps, O(n)-espace algorithme.Tout d’abord, triez le tableau de tuples par leur position de départ s’ils ne sont pas déjà dans cet ordre.Je suppose que les indices de tableau de base zéro.

Appelons la position de début du tuple i b(i) et la position de fin e(i), de sorte que sa longueur totale soit e(i) - b(i) + 1.Définissons également une fonction next(i) qui renvoie la position dans la liste de tuples du premier tuple qui peut apparaître à droite du tuple i.Notez que next(i) peut être calculé en un temps O(log n) avec une recherche binaire :conservez simplement toutes les positions de début du tuple b(i) dans un tableau b[] et recherchez le premier j dans le sous-tableau b[i+1 ..n-1] ayant b[j] > e(i).

Définissons f(i) comme étant la couverture maximale de tout ensemble de tuples non chevauchants commençant à ou après tuple je.Puisque le tuple i lui-même est soit dans cet ensemble optimal, soit non, nous avons :

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

On a aussi la condition aux limites f(n) = 0.

Clairement, la plus grande couverture possible est donnée par f(0).Ceci se calcule facilement.En 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]);
    }
}

La boucle dans calc() s'exécute n fois, et chaque itération effectue un appel O(log n) à la fonction de recherche binaire upper_bound().

Nous pouvons reconstruire un ensemble réel de cette taille en calculant les deux entrées de max() pour f(0), en voyant laquelle a réellement produit le maximum, en enregistrant si cela implique la présence ou l'absence du tuple 0, puis en effectuant une récurrence pour gérer le reste (correspondant à f(next(0)) ou f(1)).(Si les deux entrées sont égales, alors il existe plusieurs solutions optimales et nous pouvons suivre l'une ou l'autre.)

Answer 2

L'algorithme ci-dessous fonctionne en récupérant de manière récursive le plus grand ensemble non chevauchant dont chaque élément est le membre le plus à gauche, puis en renvoyant celui avec la plus grande couverture.Voir les commentaires dans le code.

Implémenté en PHP.Vous pouvez le tester ici http://viper-7.com/xowTRF

Je pense que la complexité de cet algorithme est O(2^N) ou O(N^2) avec la mise en cache, n'hésitez pas à laisser un commentaire si vous n'êtes pas d'accord.

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