Algoritmo para encontrar a cobertura máxima de não-sobreposição de seqüências.(I. e., o cálculo do Intervalo de Agendamento Prob.)

Question

Eu tenho uma pergunta que é muito semelhante ao algoritmo para encontrar o maior de não-sobreposição de seqüências.

A única diferença para os ligados questão é que em vez de encontrar o conjunto de não-sobreposição de tuplas que representam o maior sequência, Eu preciso encontrar o conjunto de não-sobreposição de tuplas que representam o a cobertura máxima, eu quero dizer que o soma dos tupla comprimentos é o máximo (um a tupla de comprimento sendo last - first + 1 dada a definição de tuple na próxima frase).

Eu represento a minha tuplas de forma diferente do que o problema associado.Em vez de (starting index, length), Eu represento a minha tuplas como (first, last);por exemplo, a tupla (3,7) representa o conjunto dos números [3, 4, 5, 6, 7].(Uma tupla sobrepõe-se outra tupla mesmo se os pontos de partida;por exemplo, (2,6) e (6,8) sobreposição e, portanto, não pode aparecer tanto na solução.)

Como um exemplo, considere o seguinte conjunto de tuplas, ordenados por first:

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

A máxima definida, aqui, seria [(0,100), (110,190), (191,200)] com uma cobertura de 101 + 81 + 10 = 192.(Note que o de tuplas nesta solução são não-sobreposição.)

O que é um exemplo do menos complexo algoritmo para resolver isso, e o que é a complexidade do algoritmo?(Isso seria ótimo se isso poderia ser resolvido em O(N), mas eu não sei no momento em que se pode ser.)

ADENDA: Em retrospecto, parece que a pergunta que eu estou pedindo aqui é equivalente a ponderada intervalo problema de agendamento de.Este é um caso especial de intervalo problema de agendamento de.

@j_random_hacker a resposta, abaixo, é, na verdade, a solução conhecida para o cálculo do intervalo de problema de agendamento, com uma complexidade em tempo de O(N log(N)).

Answer 1

Aqui está um O(nlog n) em tempo O(n)-espaço algoritmo.Primeiro, classificar a matriz de tuplas por sua posição inicial, se eles já não estão, nesta ordem.Eu vou assumir zero matriz baseada em índices.

Vamos chamar a posição de início de tupla i b(i) e a posição final e(i), de modo que seu comprimento total é de e(i) - b(i) + 1.Também vamos definir uma função seguinte(i) que retorna a posição dentro da tupla lista da primeira tupla que podem aparecer ao lado direito da tupla eu.Observe que o seguinte(i) pode ser calculado em O(log n) com um binário de pesquisa:basta manter todos os tupla início posições de b(i) em uma matriz b[], e procurar a primeira j no subarray b[i+1 ..n-1] com b[j] > e(eu).

Vamos definir f(i) ser a máxima cobertura de qualquer nonoverlapping conjunto de tuplas que começa no ou depois de tupla eu.Desde tupla eu próprio é neste conjunto otimizado ou não, temos:

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

Nós também temos a condição de contorno f(n) = 0.

Claramente, o mais possível, a cobertura é dada por f(0).Isso é facilmente calculado.Em 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]);
    }
}

O ciclo em calc() é executado n vezes, e a cada iteração, faz um tempo O(n log n) chamada para a pesquisa binária função upper_bound().

Podemos reconstruir um conjunto real de este tamanho calculando-se as entradas para max() para f(0), ver o que realmente produziu o máximo, gravação se ela implica a presença ou ausência de tupla 0 e, em seguida, recursing para lidar com o restante (correspondente ao f(próximo(0)) ou f(1)).(Se ambas as entradas forem iguais, então existem várias soluções e podemos seguir qualquer um.)

Answer 2

O algoritmo abaixo funciona por recursivamente obter o maior não-sobreposição do conjunto de que cada elemento é o mais à esquerda membro de e, em seguida, retornar a um com a maior cobertura.Consulte os comentários no código.

Implementado em PHP.Você pode testá-lo aqui http://viper-7.com/xowTRF

Eu acho que este algoritmo de complexidade de O(2^N) ou O(N^2) com o cache, sinta-se livre para deixar um comentário se você discordar.

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