Esta página discute o problema da coleção disjunta máxima de intervalos. O melhor algoritmo para o problema usa estratégia gulosa.
Veja o capítulo 16 de CLRS, onde o problema é chamado Activity-Selection Problem. Veja também a seção 4.1 de KT.
Um intervalo é um conjunto de números naturais consecutivos. Um intervalo como {s,s+1,…,f−1,f} será denotado por (s,f). O primeiro número do par é o início do intervalo e o segundo é o término. (As letras "s" e "f" lembram start e finish respectivamente.)
Se temos vários intervalos, numerados de 1 a n, o início de um intervalo i será denotado por si e o término por fi. Suporemos sempre que si ≤ fi.
Um intervalo i é anterior a um intervalo j se fi < sj. Analogamente, i é posterior a j se si > fj. Dois intervalos i e j são disjuntos se e somente se i é posterior a j ou anterior a j. Uma coleção de intervalos é disjunta se os intervalos da coleção são disjuntos dois a dois.
Problema do escalonamento de intervalos: Dada uma coleção S de intervalos, encontrar uma subcoleção disjunta máxima de S.
Uma subcoleção disjunta X de S é máxima se não existe outra maior. Em outras palavras, se não existe subcoleção disjunta X′ de S tal que |X′| > |X|.
Usaremos a abreviatura sdm para a expressão "subcoleção disjunta máxima". Nosso problema consiste, portanto, em encontrar uma sdm de uma coleção de intervalos dada. Se os intervalos são numerados de 1 a n, uma sdm pode ser representada por um subconjunto de {1,2,…,n}.
Exemplo: A figura abaixo especifica uma coleção de intervalos e uma sdm da coleção. A sdm é indicada pelos "1" do seu vetor característico x:
| s f | 4 8 | 6 7 | 13 14 | 4 5 | 2 4 | 6 9 | 7 10 | 9 11 | 1 6 | 3 13 | 9 12 |
| x | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
É fácil verificar que a coleção de 4 intervalos definida por x é disjunta. Mas não é óbvio que ela seja máxima. Você tem certeza de que não existem 5 intervalos disjuntos dois a dois?
O problema do escalonamento de intervalos tem estrutura recursiva, como mostraremos a seguir. Digamos que nossos intervalos são 1,2,…,n e suponha que X é um subconjunto de {1,2,…,n} que representa uma sdm. Então
No segundo caso, como podemos determinar, de maneira eficiente, a coleção de todos os intervalos disjuntos de n? Se os intervalos estiverem em ordem crescente de término, ou seja, se
f1 ≤ f2 ≤ … ≤ fn ,
então a coleção dos intervalos disjuntos de n é igual à coleção de todos os intervalos anteriores a n. Esta última tem a forma 1,2,…,i, sendo i o maior índice tal que fi < sn. (Isso não é tão óbvio quanto parece!) Assim, reduzimos a instância 1..n à instância 1..i.
O seguinte algoritmo recursivo devolve uma sdm da coleção de intervalos definida por (s,f,n). O algoritmo supõe que f1 ≤ … ≤ fn e n ≥ 0:
| SDM-Recursivo (s, f, n) |
| 1 o se n ≤ 1 |
| 2 oooo então se n = 0 então devolva { } senão devolva {1} |
| 3 oooo senão X ← SDM-Recursivo (s, f, n−1) |
| 4 oooo senão i ← n |
| 5 oooo senão faça i ← i−1 |
| 6 oooo senão ooo até que i = 0 ou fi < sn |
| 7 oooo senão X′ ← SDM-Recursivo (s, f, i) |
| 8 oooo senão devolva max (X , X′ ∪ {n}) |
A invocação do algoritmo da linha 7 está correta pois i ≥ 0 e f1 ≤ … ≤ fi. Algo análogo ocorre na linha 3.
O algoritmo tem mau desempenho porque invoca SDM-Recursivo várias vezes com os mesmos valores dos argumentos. A seção seguinte procura remediar esse defeito.
O algoritmo SDM-Recursivo é o ponto de partida de um algoritmo muito mais eficiente que usa a técnica da programação dinâmica. Essa técnica pode ser descrita como uma maneira esperta de transformar recursão em iteração com o apoio de uma tabela.
Para cada m, denote por X[m] uma sdm da coleção de intervalos {1,…,m}. Se nossos intervalos estiverem em ordem crescente de término então, graças à estrutura recursiva do problema, teremos
X[m] = max (X[m−1] , X[i] ∪ {m}) ,
onde i é o maior índice tal que fi < sm. Se tal i não existe, podemos dizer que i = 0 e adotar X[0] = { }. O vetor X pode ser calculado pelo seguinte algoritmo, que supõe f1 ≤ … ≤ fn e n ≥ 0:
| SDM-Prog-Din (s, f, n) |
| 1 o X[0] ← { } |
| 2 o para m ← 1 até n faça |
| 3 oooo i ← m |
| 4 oooo faça i ← i−1 |
| 5 ooooooo até que i = 0 ou fi < sm |
| 6 oooo X[m] ← max (X[m−1] , X[i] ∪ {m}) |
| 7 o devolva X[n] |
É possível implementar o algoritmo de modo que o seu consumo de tempo fique em Ο(n2) no pior caso (veja exercício abaixo).
Nosso problema pode ser resolvido por um algoritmo guloso que é mais rápido e mais simples que a programação dinâmica. Para descrever o algoritmo, precisamos do seguinte conceito. Digamos que o primeiro intervalo de um coleção de intervalos é o que tem o menor término. (Eu deveria dizer "um primeiro", pois a coleção pode ter vários primeiros intervalos. Mas vou continuar dizendo "o primeiro" por comodismo.)
Eis o esboço do algoritmo guloso. Ele recebe uma coleção S de intervalos e devolve uma sdm de S:
X ← { }
enquanto S ≠ { } faça
xxx i ← primeiro intervalo de S
xxx X ← X ∪ {i}
xxx S ← coleção dos intervalos posteriores a i
devolva X
Antes de transformar esse esboço em pseudocódigo de nível mais baixo, convém exigir que os intervalos estejam em ordem crescente de término. (Com isso, o primeiro intervalo é o de índice 1.)
O algoritmo supõe f1 ≤ … ≤ fn e n ≥ 0 e devolve uma sdm da coleção de intervalos definida por (s,f,n):
| SDM-Guloso (s, f, n) |
| 1 o X ← { } |
| 2 o i ← 1 |
| 3 o enquanto i ≤ n faça |
| 4 oooo X ← X ∪ {i} |
| 5 oooo k ← i + 1 |
| 6 oooo enqunto k ≤ n e sk < fi faça |
| 7 ooooooo k ← k + 1 |
| 8 oooo i ← k |
| 9 o devolva X |
O código pode ser reescrito de maneira mais elegante:
| SDM-Guloso (s, f, n) |
| 1 o f0 ← −∞ |
| 2 o X ← { } |
| 3 o i ← 0 |
| 4 o para k ← 1 até n faça |
| 5 oooo se sk > fi |
| 6 ooooooo então X ← X ∪ {k} |
| 7 ooooooo então i ← k |
| 8 o devolva X |
(A linha 1 cria um intervalo fictício que é anterior a todos os demais. Isto é necessário para que a primeira execução da linha 5 faça sentido.)
O algoritmo é guloso: ele abocanha o primeiro intervalo viável k que encontra, sem se preocupar com o que vem depois. Uma característica importante da estratégia gulosa: o algoritmo jamais se arrepende de uma decisão. Uma vez tomada a decisão de colocar k na sdm (linhas 6 e 7), essa decisão nunca será revista.
O algoritmo guloso consome Ο(n) unidades de tempo no pior caso. Isso não inclui o tempo Ο(n log n) necessário para fazer a ordenação prévia dos intervalos, mas mesmo levando em conta esse tempo adicional, o algoritmo guloso é mais rápido que a programação dinâmica.
A prova da correção do algoritmo SDM-Guloso é um tanto sutil, como acontece com a maioria dos algoritmo gulosos. O principal invariante do processo iterativo poderia ser formulado assim: no início de cada iteração, o conjunto X dos intervalos já escolhidos é uma sdm de {1,2,.…,k−1}. Mas é melhor formular o invariante de uma maneira que é mais típica de algoritmos gulosos.
No início de cada iteração imediatamente antes da comparação de k com n, X faz parte de alguma sdm de {1,2,…,n}. Em termos mais precisos,
| existe uma parte Y de {k,k+1,…,n} tal que X∪Y é uma sdm. | (*) |
(Se estivesse programando pra valer, eu faria questão de escrever esse comentário logo depois da linha 4.) É claro que (*) vale no início da primeira iteração. Suponha agora que (*) vale no início de uma iteração qualquer. Se sk ≤ fi na linha 5 então é claro que (*) continua valendo no início da próxima iteração, pois X não se altera. Suponha agora que sk > fi. Se Y contém k então é claro que (*) vale com
X ∪ {k} e Y − {k}
nos papéis de X e Y antes da execução da linha 6 e portanto (*) vale no início da próxima iteração. Suponha, finalmente, que Y não contém k e seja l o primeiro intervalo de Y (é claro que l > k). Não é difícil perceber que
(Y−{l}) ∪ {k}
satisfaz (*) tanto quanto Y. Assim, recaímos na situação anterior, em que k estava em Y.
Essa troca de l por k é um truque típico na análise da correção de qualquer algoritmo guloso.
O problema do escalonamento de intervalos goza de uma interessante propriedade minimax. (Trata-se de uma manifestação da dualidade em programação linear.) Suponha que inícios e términos de todos os intervalos da coleção S pertencem a um intervalo (a,z) que chamaremos universo. (O universo é (1,14) no exemplo que usamos no topo desta desta página.)
Uma cobertura de S é qualquer subconjunto C do universo (a,z) tal que todo intervalo contém pelo menos um elemento de C. É evidente que para toda subcoleção disjunta X de S e toda cobertura C de S tem-se
|X| ≤ |C|.
Portanto, se |X| = |C| então X é uma sdm (e C é uma cobertura mínima). Assim, uma cobertura pequena pode ser usada como prova da maximalidade de uma sdm. (No exemplo acima, o conjunto {4,7,11,13} é uma cobertura. Esta cobertura prova que naquele exemplo não existe uma subcoleção disjunta com mais que quatro intervalos.)
Os algoritmos SDM-Prog-Din e SDM-Guloso podem ser modificados de modo a produzir uma sdm X e uma cobertura C de mesmo tamanho.