Escalonamento de intervalos

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.

O problema

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?

Exercício

  1. Seja S uma coleção de intervalos. É verdade que toda subcoleção disjunta maximal de S é máxima?

A estrutura recursiva do problema

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

f1f2 ≤ … ≤ 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 XSDM-Recursivo (s, f, n−1)
4 oooo senão in
5 oooo senão faça ii−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.

Exercícios

  1. Estime o consumo de tempo do algoritmo SDM-Recursivo em função do número n de intervalos.
  2. Escreva uma versão de SDM-Recursivo para o caso em que os intervalos são dados em ordem crescente de início.

Algoritmo de programação dinâmica

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 fism. 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)
o X[0] ← { }
o para m ← 1 até n faça
oooo im
oooo faça ii−1
ooooooo até que i = 0 ou fi < sm
oooo X[m] ← max (X[m−1] , X[i] ∪ {m})
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).

Exercícios

  1. Se você estivesse programando pra valer, que comentários acrescentaria ao código de SDM-Prog-Din?  [Solução]
  2. No algoritmo SDM-Prog-Din, quantas vezes a comparação fi < sm é executada?  Deduza da resposta que o algoritmo consome Θ(n2) unidades de tempo.
  3. Escreva uma versão de SDM-Prog-Din que aceite dados em ordem crescente de início.
  4. O algoritmo SDM-Prog-Din envolve a manipulação de subconjuntos de {1,…,n}.  Não é óbvio como fazer isso de maneira eficiente.  Uma boa ideia é trocar o vetor X[0..n] por um vetor t[0..n] em que cada t[m] é o tamanho de uma sdm da instância (s,f,m) do problema.  Depois que o vetor t tiver sido calculado, é fácil extrair dele uma sdm.  Implemente essa ideia.

Algoritmo guloso

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 XX ∪ {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)
o X ← { }
o i ← 1
o enquanto in faça
oooo XX ∪ {i}
oooo ki + 1
oooo enqunto kn e sk < fi faça
ooooooo kk + 1
oooo ik
o devolva X

O código pode ser reescrito de maneira mais elegante:

SDM-Guloso (s, f, n)
o f0 ← −∞
o X ← { }
o i ← 0
o para k ← 1 até n faça
oooo se sk > fi
ooooooo então XX ∪ {k}
ooooooo então ik
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.

Consumo de tempo

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.

O algoritmo guloso está correto

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 nX  faz parte de alguma sdm de {1,2,…,n}.  Em termos mais precisos,

  existe uma parte Y de {k,k+1,…,n}
tal que XY é 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.

Exercícios

  1. Suponha dado um conjunto C de intervalos.  Seja (s′,f′) um intervalo em C que tem início máximo. Seja (s″,f″) um intervalo em C que tem término máximo.  É verdade que (s′,f′) faz parte de toda subcoleção disjunta máxima de C?  É verdade que (s′,f′) faz parte de alguma coleção disjunta máxima de C?  É verdade que (s″,f″) faz parte de toda coleção disjunta máxima de C?  É verdade que (s″,f″) faz parte de alguma coleção disjunta máxima de C?
  2. [CLR 17.1-3]  Digamos que a duração de um intervalo i é fisi. Coloque os intervalos em ordem crescente de duração. Escolha os intervalos gulosamente respeitando a ordem crescente de duração. Este algoritmo resolve o problema do escalonamento de intervalos?
  3. Para implementar o algoritmo SDM-Guloso de maneira eficiente, convém representar o conjunto X por seu vetor característico x[1..n].  Escreva essa versão do algoritmo.
  4. Escreva os detalhes da prova do invariante (*).
  5. Suponha dados intervalos 1,2,…,n tais que  s1 ≤ s2 ≤ … ≤ sn . Escreva um algoritmo guloso que determine uma sdm da coleção de intervalos. Seu algoritmo deve tirar proveito da ordem em que os intervalos foram dados. 

Mais exercícios

  1. [Generalização: Intervalos com pesos]  Considere a seguinte generalização do problema do escalonamento de intervalos:  Dada uma coleção S de intervalos e um peso numérico pi ≥ 0 para cada intervalo i, encontrar uma subcoleção disjunta de S que tenha peso máximo.  Escreva um algoritmo de programação dinâmica para o problema.
  2. [Generalização: Intervalos com sobpreposição limitada]  Seja {a,a+1,…,z} um conjunto de números naturais. Diremos que esse conjunto é nosso universo.  A cada elemento q do universo está associado um número natural cq que chamaremos capacidade.  Dada uma coleção S de intervalos cujos inícios e términos pertencem ao universo, diremos que uma subcoleção T de S respeita as capacidades se, para cada q no universo, no máximo cq elementos de T contêm q.  Problema: dada uma coleção S de intervalos cujos inícios e términos pertencem ao universo, encontrar uma subcoleção máxima de S dentre as que respeitam as capacidades.  Escreva um algoritmo para o problema.

 


Apêndice: identidade minimax

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.

Exercícios

  1. Modifique o algoritmo SDM-Guloso para que ele devolva uma sdm e uma cobertura mínima.

Valid HTML 4.01 Strict Valid CSS!