Algoritmo para encontrar la máxima cobertura de secuencias que no se superponen.(Es decir, el problema de programación de intervalos ponderados).

Question

Tengo una pregunta que es muy similar a algoritmo para encontrar secuencias más largas que no se superpongan.

La única diferencia con la pregunta vinculada es que en lugar de encontrar el conjunto de tuplas no superpuestas que representan el secuencia más larga, necesito encontrar el conjunto de tuplas no superpuestas que representan el cobertura máxima, con lo que me refiero a suma de las longitudes de la tupla es máximo (un longitud de tupla ser last - first + 1 dada la definición de tupla en la siguiente frase).

Represento mis tuplas de manera diferente al problema vinculado.En lugar de (starting index, length), represento mis tuplas como (first, last);por ejemplo, la tupla (3,7) representa el conjunto de números [3, 4, 5, 6, 7].(Una tupla se superpone otra tupla incluso si los puntos finales coinciden;es decir., (2,6) y (6,8) superposición y por lo tanto no pueden aparecer ambos en la solución).

Como ejemplo, considere el siguiente conjunto de tuplas, ordenadas por first:

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

El conjunto máximo aquí sería [(0,100), (110,190), (191,200)] con una cobertura de 101 + 81 + 10 = 192.(Tenga en cuenta que las tuplas en esta solución son no superpuesto.)

¿Cuál es un ejemplo del algoritmo menos complejo para resolver esto y cuál es la complejidad de ese algoritmo?(Sería genial si esto pudiera resolverse en O(N), pero no sé por el momento si puede ser).

APÉNDICE: En retrospectiva, resulta que la pregunta que hago aquí es equivalente a la problema de programación de intervalos ponderados.Este es un caso especial de la problema de programación de intervalos.

La respuesta de @j_random_hacker, a continuación, es, de hecho, la solución conocida al problema de programación de intervalos ponderados, con una complejidad en el tiempo de O(N log(N)).

Answer 1

Aquí hay un O(nlog n)-tiempo, O(n)-espacio algoritmo.Primero, ordene la matriz de tuplas por su posición inicial si aún no están en este orden.Asumiré índices de matriz de base cero.

Llamemos a la posición inicial de la tupla i b(i) y a la posición final e(i), de modo que su longitud total sea e(i) - b(i) + 1.También definamos una función next(i) que devuelva la posición dentro de la lista de tuplas de la primera tupla que puede aparecer en el lado derecho de la tupla i.Observe que next(i) se puede calcular en tiempo O(log n) con una búsqueda binaria:simplemente mantenga todas las posiciones iniciales de la tupla b(i) en una matriz b[] y busque la primera j en la submatriz b[i+1 ..n-1] teniendo b[j] > e(i).

Definamos f(i) como la cobertura máxima de cualquier conjunto de tuplas no superpuestas que comience en o después tupla i.Dado que la propia tupla i está en este conjunto óptimo o no, tenemos:

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

También tenemos la condición de frontera. f(n) = 0.

Claramente, la mayor cobertura posible viene dada por f(0).Esto se calcula fácilmente.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]);
    }
}

El bucle en calc() se ejecuta n veces y cada iteración realiza una llamada O(log n) a la función de búsqueda binaria upper_bound().

Podemos reconstruir un conjunto real de este tamaño calculando ambas entradas a max() para f(0), viendo cuál realmente produjo el máximo, registrando si implica la presencia o ausencia de la tupla 0, y luego recurriendo para manejar el resto (correspondiente a f(next(0)) o f(1)).(Si ambas entradas son iguales, entonces hay múltiples soluciones óptimas y podemos seguir cualquiera de ellas).

Answer 2

El siguiente algoritmo funciona recuperando recursivamente el conjunto más grande no superpuesto del que cada elemento es el miembro más a la izquierda y luego devuelve el que tiene la mayor cobertura.Ver comentarios en el código.

Implementado en PHP.Puedes probarlo aquí http://viper-7.com/xowTRF

Creo que la complejidad de este algoritmo es O(2^N) o O(N^2) con el almacenamiento en caché, no dudes en dejar un comentario si no estás de acuerdo.

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