Subsequência crescente máxima

Esta página resolve o problema da subsequência crescente máxima.  Esse problema é uma boa introdução à técnica de programação dinâmica.

Veja o capítulo 15 (em especial o problema 15.4-5) de CLRS.  Veja também o verbete Longest increasing subsequence problem na Wikipedia.  Veja ainda a página Sequence Comparison: Some Theory and Some Practice de Imre Simon.

O problema

Suponha que A[1..n] é uma sequência de números naturais. Uma subsequência de A[1..n] é o que sobra depois que um conjunto arbitrário de termos é apagado.  (Não confunda subsequência com segmento: um segmento de A[1..n] é o que sobra depois que apagamos um número arbitrário de termos no início de A e um número arbitrário de termos no fim de A.)

Em outras palavras, B[1..k] é uma subsequência de A[1..n] se existem índices i1,i2,…,ik tais que   1 ≤ i1 < i2 < … < ik ≤ n   e

B[1] = A[i1],  B[2] = A[i2],  … ,  B[k] = A[ik] .

Dizemos que o índice 1 de B casa com o índice i1 de A,  que o índice 2 de B casa com o índice i2 de A,  etc.  Cuidado: podemos ter B[5] = A[19], por exemplo, sem que o índice 5 de B esteja casado com índice 19 de A.

Adotaremos a abreviatura ssc para dizer subsequência crescente.  Uma ssc de A[1..n] é máxima se não existe outra ssc mais longa.

Problema da ssc máxima:  Encontrar o comprimento de uma ssc máxima de A[1..n].

Exemplos:

Exercício

  1. Considere o seguinte problema:  decidir se B[1..k] é uma subsequência de A[1..n].  Escreva um algoritmo eficiente para resolver o problema.  Prove que o seu algoritmo está correto.
  2. Execute o algoritmo abaixo com m = 1,2,…,n.  É verdade que o maior dos resultados devolvidos é uma solução do problema ssc máxima?
    Guloso (A, n, m)
    1 _ k ← 1
    2 _ B[k] ← A[m]
    3 _ para  im+1  até  n  faça
    4 ____ se  B[k] ≤ A[i]
    5 ______ então  kk+1
    6 ______ então  B[k] ← A[i]
    7 _ devolva  k
  3. Discuta o seguinte algoritmo: Para cada sequência b[1..n] de bits, considere a subsequência de A[1..n] que corresponde aos bits 1 de b.  Descarte as subsequências não crescentes.  Escolha a mais longa das sequências restantes.
  4. [Bom!]  Acompanhe o seguinte raciocício, que pode levar a um bom algoritmo. Suponha que B[1..k] é uma ssc máxima de A[1..n].  Há duas possibilidades: ou o índice k de B casa com índice n de A ou não. No segundo caso, B[1..k] é uma ssc de A[1..n−1]. Isto é excelente, pois reduz a instância do problema a uma instância menor. No primeiro caso, B[1..k−1] é uma ssc de A[1..n−1]. Isso está certo?

Algoritmo recursivo

Para que possamos formular um algoritmo recursivo para um problema, é preciso que o problema tenha estrutura recursiva,  ou seja,  é preciso que toda solução de uma instância do problema contenha soluções de instâncias menores (ou melhor, de subinstâncias da instância dada).

O problema da ssc máxima não parece ter estrutura recursiva (veja exercício acima), mas um parente próximo do problema tem.  Para introduzir esse parente, precisamos da seguinte definição: uma ssc com término fixo de A[1..n] é qualquer ssc B[1..k] de A[1..n] tal que o índice k de B casa com o índice n de A.   Adote a abreviatura ssctf para a expressão ssc com término fixo.  Eis o novo problema:

Problema da ssctf máxima:  Encontrar o comprimento de uma ssctf de A[1..n] que tenha comprimento máximo.

O problema da ssctf máxima tem estrutura recursiva.  De fato, se B[1..k] é uma ssctf máxima de A[1..n] então existe i tal que   B[1..k−1]  é ssctf máxima de  A[1..i] .   O seguinte algoritmo usa essa estrutura recursiva para resolver o problema:

SSCTF-Max-Rec (A, n)
1 _ c ← 1
2 _ para  in−1  decrescendo até 1  faça
3 ____ se  A[i] ≤ A[n]
4 _______ então  dSSCTF-Max-Rec (A, i)
5 _______ então  se  d+1 > c  então  cd+1
6 _ devolva  c

(O algoritmo supõe que n ≥ 1. O caso n = 1 é a base da recursão.)   O algoritmo é muito ineficiente, pois invoca SSCTF-Max-Rec (Ai) muitas vezes com o mesmo valor de i.

Para resolver o problema da ssc máxima, basta invocar SSCTF-Max-Rec (Am) com m = 1,2,…,n e escolher o maior resultado.

Exercícios

  1. Critique a seguinte definição: uma ssctf de A[1..n] é qualquer ssc B[1..k] de A[1..n] tal que B[k] = A[n].
  2. Prove, detalhadamente, que o algoritmo SSCTF-Max-Rec está correto.
  3. Calcule o consumo de tempo do algoritmo SSCTF-Max-Rec no pior caso.

Algoritmo de programação dinâmica

Para melhorar dramaticamente a eficiência da solução recursiva acima, basta recorrer à técnica da programação dinâmica.  Como no algoritmo recursivo, cada instância do problema é resolvida a partir da solução de suas subinstâncias. As soluções das subinstâncias são guardadas numa tabela, digamos c[1..n].  Para cada m,

c[m]  é o comprimento de uma ssctf máxima de A[1..m].

A estrutura recursiva do problema garante que   c[m] = max{1+c[i] : i < m  e  A[i] ≤ A[m]}.   É fácil traduzir essa recorrência em código e assim preencher a tabela c da esquerda para a direita:

SSCTF-Max-PD (A, n)
_ para  m ← 1  até  n  faça
____ c[m] ← 1
____ para  im−1  decrescendo até  1  faça
_______ se  A[i] ≤ A[m]  e  c[i]+1 > c[m]
__________ então  c[m] ← c[i]+1
_ devolva  c[1..n]

Quanto tempo o algoritmo consome no pior caso?  É fácil ver que o consumo de tempo é proporcional ao número de execuções da comparação A[i] ≤ A[m] na linha 4.  Esse número é  0+1+...+(n−1) = n(n−1)/2.  (Outra maneira de ver isso: a tabela c tem n posições e o cálculo de cada uma delas consome no máximo n unidades de tempo.)  Portanto, o algoritmo consome

Ο(n2)

unidades de tempo no pior caso.

De volta ao problema original:  para obter o comprimento de uma ssc máxima de A[1..n], basta calcular o máximo do vetor c[1..n], o que pode ser feito em Ο(n) unidades de tempo.

Exercícios

  1. Mostre que o algoritmo SSCTF-Max-PD com argumentos A e n consome Θ(n2) unidades de tempo em todos casos (tanto no pior quanto no melhor).
  2. Escreva um algoritmo de programação dinâmica que devolva não só o comprimento de uma ssc máxima de A[1..n], mas também a correspondente ssc.
  3. Digamos que c[1..n] é o vetor calculado pelo algoritmo SSCMTF-Max-PD. É verdade que c[n] é o número de componentes do vetor A[1..n] que são menores ou iguais a A[n]?
  4. O algoritmo abaixo resolve o problema da ssc máxima?
    SSC-Max (A, n)
    _ t[0] ← 0
    _ para  m ← 1  até  n  faça
    ____ im
    ____ repita  ii−1
    ______ até que  i = 0  ou  A[i] ≤ A[m]
    ____ t[m] ← max (t[m−1], t[i]+1)
    _ devolva  t[n]

    (No fim de cada execução da linha 6, t[m] é o comprimento de uma ssc máxima de A[1..m].)

  5. Escreva um algorimo que receba uma sequência A[1..n] e devolva uma subsequência máxima de A[1..n] dentre as que são palíndromos.  (Uma sequência B[1..k] é palíndromo de B[1] = B[k], B[2] = B[k−1], etc.)

 


Apêndice: identidade minimax

O problema da ssc máxima goza de uma propriedade minimax interessante.  (Trata-se de uma manifestação da dualidade em programação linear.)  Digamos que uma cobertura de A[1..n] é um conjunto de subsequências de A[1..n] dotada da seguinte propriedade: todo elemento de A[1..n] pertence a pelo menos uma das subsequências do conjunto.  Se todas as sequências da cobertura forem estritamente decrescentes, temos uma cssed (cobertura por subsequências estritamente decrescentes).

É fácil verificar que, para qualquer sequência A[1..n], toda cssed é pelo menos tão grande quanto qualquer ssc.  (Portanto, se uma cssed tem o mesmo tamanho que uma ssc então a cssed é mínima e a ssc é máxima.)

Por exemplo, o conjunto de sequências {(9,6,4), (5,3), (7), (9,6,4)} é uma cssed da sequência  (9,5,6,3,9,6,4,7).  Esta cssed prova que não existe uma ssc de comprimento maior que quatro.  Mais que isso:  como existe uma ssc de tamanho quatro — como (5,6,6,7), por exemplo — a cssed é mínima e toda ssc de tamanho quatro é máxima.

Uma cssed de A[1..n] é mínima se não existe outra cssed com menos subsequências.   Não é muito difícil verificar a seguinte propriedade minimax:

para qualquer A[1..n],  o comprimento de uma ssc máxima é igual ao tamanho de uma cssed mínima.

É um ótimo exercício modificar o algoritmo da ssc máxima para que ele devolva também uma cssed mínima.

Mais exercícios

  1. Invente um algoritmo que resolva o problema da ssc máxima em Ο(n lg n) unidades de tempo no pior caso.
  2. Exiba uma ssc máxima da sequência (32,19,32,17,31,43,30,29,54,16,28,52,15,41,65,14,50). Prove que sua solução é de fato máxima. (Para isso, exiba uma cobertura apropriada e use esse cobertura para provar a maximalidade da sua solução.)
  3. [Número de coorrências]  Escreva um algoritmo que conte o número de ocorrências de A[1..m] como subseqüência de B[1..n].  O seu algoritmo pode consumir tempo Ο(mn).
  4. [Subsequência comum máxima de duas sequências]  Considere o problema da subsequência comum máxima (= longest common subsequence) de duas sequências.  (Por exemplo,  (2,3,2,1)  é uma subsequência comum máxima de  (1,2,3,2,4,1,2)  e  (2,4,3,1,2,1).)   Mostre que o problema da ssc máxima é um caso especial do problema da subsequência comum máxima de duas sequências.
  5. [Subsequência comum máxima de duas sequências]  Resolva o problema da subsequência comum máxima de duas sequências.

Valid HTML 4.01 Strict Valid CSS!