Imagine que vários eventos (feiras, congressos, etc.) querem usar um certo centro de convenções. Cada evento i gostaria de usar o centro durante um intervalo de tempo que começa num dia a[i] e termina num dia b[i]. Dois eventos são compatíveis se seus intervalos de tempo são disjuntos. A administração do centro de convenções quer atender o maior número possível de eventos que sejam compatíveis dois a dois. Este é um exemplo do problema da coleção disjunta máxima de intervalos.
Esta página discute um algoritmo guloso para o problema da coleção disjunta máxima de intervalos. A página foi inspirada no capítulo 16 de CLRS, onde o problema é chamado Activity-Selection Problem.
Suponha que a[p .. r] e b[p .. r] são dois vetores de números inteiros positivos tais que a[i] ≤ b[i] para cada i. Portanto, para cada i, o intervalo a[i] .. b[i] não é vazio. Diremos que o par (a, b) de vetores é uma coleção de intervalos.
Os índices
p, p+1, … ,
r
são os nomes
dos intervalos da coleção.
Portanto, podemos usar expressões como
a coleção de intervalos { p, p+1, … , r }
para falar da coleção de intervalos (a, b).
Para cada intervalo i, diremos que a[i] é o início do intervalo e b[i] é o término do intervalo. Um intervalo i é anterior a um intervalo k se b[i] < a[k], ou seja, se i termina antes do início de k. Nas mesmas condições, k é posterior a i. Dois intervalos são disjuntos se e somente se o primeiro é anterior ou posterior ao segundo.
Uma subcoleção da coleção de intervalos { p, … , r } é disjunta se seus elementos são disjuntos dois a dois. Uma subcoleção disjunta é máxima se não existe uma maior. Em outras palavras, uma subcoleção disjunta X é máxima se não existe subcoleção disjunta Y tal que tal que ⎮Y⎮ > ⎮X⎮.
Problema da Coleção Disjunta Máxima de Intervalos: Encontrar uma subcoleção disjunta máxima de uma coleção (a[p .. r], b[p .. r]) de intervalos.
Usaremos a abreviatura SCD para a expressão
subcoleção disjunta
.
Nosso problema consiste, então,
em encontrar uma SCD máxima de uma coleção de intervalos.
Uma SCD da coleção de intervalos { p, … , r } poderia ser representada por seu vetor característico x[p .. r]. Mas nesta página trataremos cada SCD como um mero subconjunto de { p, … , r }.
Exemplo B: Considere a coleção de 8 intervalos representada na figura. (Mesma coleção do exemplo A.) A subcoleção { 7, 8 } é disjunta. A subcoleção { 1, 2, 6 } também é disjunta. A primeira não é uma SCD máxima pois a segunda é maior. A segunda é máxima? Existe uma SCD com quatro intervalos?
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| a b | 6 15 | 25 30 | 9 15 | 23 28 | 7 16 | 18 24 | 30 34 | 1 26 |
| ☑ | ☑ | |||||||
| ☑ | ☑ | ☑ |
O problema da SCD máxima admite um algoritmo guloso. Cada iteração do algoritmo escolhe um intervalo de término mínimo e remove da coleção todos os intervalos que não são posteriores ao intervalo escolhido.
Em outras palavras, o algoritmo consiste no seguinte:
Cada iteração começa com uma subcoleção D
da coleção de intervalos dada.
Em cada iteração,
o algoritmo escolhe um intervalo de término mínimo
dentre os que são
posteriores aos de D
e acrescenta esse intervalo a D.
O algoritmo é guloso porque escolhe,
repetidamente,
o intervalo mais apetitoso
da iteração sem medir as consequências dessa escolha.
É evidente que o algoritmo guloso produz uma SCD da coleção dada. Resta provar que a SCD produzida é máxima. Para isso, é preciso entender as duas propriedades a seguir.
Propriedade da Escolha Gulosa: Todo intervalo de término mínimo pertence a alguma SCD máxima.
Prova: Seja m um intervalo de término mínimo e X uma SCD máxima. Se m ∈ X, não há mais o que discutir. Suponha agora m ∉ X e seja q um intervalo de término mínimo em X. Observe que m é anterior a q e que todos os intervalos da subcoleção X são posteriores a q. Portanto, a coleção (X − { q}) ∪ {m} é disjunta, ou seja, é uma SCD. Ademais, essa nova coleção tem o mesmo tamanho que X, sendo portanto uma SCD máxima. Finalmente, observe que a nova coleção contém m, CQD.
Propriedade da Subestrutura Ótima: Seja m um intervalo de término mínimo e X uma SCD máxima. Se m ∈ X então X − {m} é uma SCD máxima da coleção de todos os intervalos posteriores a m.
Prova: Digamos que P é a coleção de todos os intervalos posteriores a m. É claro que a coleção X − {m} é disjunta. Como m tem término mínimo em X, a coleção X − {m} é uma subcoleção de P, ou seja, uma SCD de P. Resta mostrar que X − {m} é uma SCD máxima de P. Para isso, suponha que Y é uma SCD qualquer de P. Como Y ∪ {m} é disjunta, a maximalidade de X garante que ⎮Y ∪ {m}⎮ ≤ ⎮X⎮. Portanto ⎮Y⎮ ≤ ⎮X − {m}⎮, o que prova que X − {m} é uma SCD máxima de P, CQD.
Essas duas propriedades explicam por que o algoritmo guloso esboçado acima está correto.
Traduzir o algoritmo guloso em código exige um pouco de esforço. Para que o código seja eficiente, convém supor que os intervalos estão em ordem crescente de términos, ou seja, que
| b[p] ≤ b[p+1] ≤ ⋯ ≤ b[r] . | (A) |
Para escrever o algoritmo em estilo recursivo, será preciso adotar um intervalo fictício p − 1 com início e término nulos. O intervalo fictício será anterior a todos os demais intervalos pois todos têm inícios e términos positivos.
| SCD-Max-Guloso (a, b, p, r) ▷ p ≤ r |
| 1 . a[p−1] := b[p−1] := 0 |
| 2 . devolva SCD-Max-r (a, b, p−1, r) |
O subalgoritmo SCD-Max-r recebe uma coleção de intervalos (a[k .. r], b[k .. r]) em ordem crescente de términos e devolve uma SCD máxima da coleção de todos os intervalos que são posteriores ao intervalo k:
| SCD-Max-r (a, b, k, r) ▷ b crescente e k ≤ r |
| 1 . m := k + 1 |
| 2 . enquanto m ≤ r e a[m] ≤ b[k] |
| 3 .ooo m := m + 1 |
| 4 . se m ≤ r |
| 5 .ooo X := SCD-Max-r (a, b, m, r) |
| 6 .ooo devolva { m } ∪ X e pare |
| 7 . devolva { } |
No fim da linha 4, m é um intervalo de término mínimo dentre os que são posteriores a k. Na linha 6, m é escolhido para fazer parte da solução X. Na linha 7, o algoritmo devolve uma coleção vazia pois não encontrou intervalos posteriores a k.
A versão iterativa do algoritmo guloso é mais simples e mais interessante que a recursiva. Continuamos supondo que vale a condição (A), ou seja, que os intervalos são dados em ordem crescente de términos.
| SCD-Max-Gula (a, b, p, r) ▷ b crescente e p ≤ r |
| 1 . X := { p } |
| 2 . k := p |
| 3 . para m := p+1 até r |
| 4 .ooo se a[m] > b[k] |
| 5 .oooooo X := X ∪ { m } |
| 6 .oooooo k := m |
| 7 . devolva X |
No início da linha 4, k ∈ X e b[k] = maxi ∈ X b[i]. Portanto, todo intervalo m posterior a k é disjunto de todos os intervalos em X. Na linha 5, m é o primeiro intervalo posterior a k. O algoritmo escolhe m para fazer parte da solução X sem saber o que virá depois. A escolha de m é definitiva e nunca será revista.
Quanto tempo o algoritmo SCD-Max-Gula consome? Vamos medir o tempo em relação ao número r − p + 1 de intervalos. Se denotarmos esse número por n, é fácil constatar que o algoritmo consome
Θ(n)
unidades de tempo para qualquer coleção de n intervalos. Mas isso não inclui o pré-processamento que coloca os intervalos em ordem crescente de término.
Exemplo E: Considere a coleção de intervalos do exemplo B. A tabela abaixo registra a coleção em ordem crescente de términos. Execute o algoritmo SCD-Max-Gula com p = 1 e r = 8. O algoritmo percorre a tabela da esquerda para a direita. Os intervalos escolhidos para fazer parte da solução X (linha 5 do código) estão marcados com ☑ . Verifique se o algoritmo foi aplicado corretamente.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| a b | 6 15 | 9 15 | 7 16 | 18 24 | 1 26 | 23 28 | 25 30 | 30 34 |
| ☑ | ☑ | ☑ |
Exemplo F: A tabela abaixo registra uma coleção de 11 intervalos em ordem crescente de términos. Execute o algoritmo SCD-Max-Gula com p = 1 e r = 11. O algoritmo percorre a tabela da esquerda para a direita. Os intervalos escolhidos para fazer parte de X (linha 5 do código) estão marcados com ☑ .
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
| a b | 2 4 | 4 5 | 1 6 | 6 7 | 4 8 | 6 9 | 7 10 | 9 11 | 9 12 | 3 13 | 13 14 |
| X | ☑ | ☑ | ☑ | ☑ |
| SCD-Max-Gula-2 (a, b, p, r) |
| 1 . X := { } |
| 2 . k := p |
| 3 . enquanto k ≤ r |
| 4 .ooo X := X ∪ { k } |
| 5 .ooo m := k + 1 |
| 6 .ooo enquanto m ≤ r e a[m] ≤ b[k] |
| 7 .oooooo m := m + 1 |
| 8 .ooo k := m |
| 9 . devolva X |
O problema da SCD máxima de intervalos goza de uma interessante propriedade minimax. (Trata-se de uma manifestação da dualidade em programação linear.) Suponha dada uma coleção S de intervalos. Suponha que os inícios e términos de todos os elementos de S pertencem a um intervalo L .. M de números naturais que chamaremos universo. (No exemplo F acima, o universo é 1..14.)
Uma cobertura (= cover) de S é qualquer subconjunto Z do universo tal que todo intervalo em S contém pelo menos um elemento de Z. É evidente que
⎮X⎮ ≤ ⎮Z⎮
para toda SCD X de S e toda cobertura Z de S. Portanto, se ⎮X⎮ = ⎮Z⎮ então X é uma SCD máxima (e Z é uma cobertura mínima). Assim, uma cobertura pode ser usada como prova da maximalidade de uma SCD máxima. (No exemplo F acima, o conjunto {4, 7, 11, 13} é uma cobertura. Esta cobertura prova que naquele exemplo não existe SCD com mais que quatro intervalos.)
O algoritmo SCD-Max-Gula pode ser modificado de modo a produzir uma SCD máxima X e uma cobertura Z de mesmo tamanho.