MAC0122 Princípios de Desenvolvimento de Algoritmos (2023ii, EC/EP)

Consideramos aqui uma versão muito simplificada do jogo de paciência.  Em nossa versão, temos como entrada uma sequência de inteiros \(s=(x_0,\dots,x_{N-1})\) e desejamos obter uma decomposição $d=(d_0,\dots,d_{p-1})$ de $s$ em subsequencias decrescentes. Queremos assim que cada $d_i$ seja uma subsequência decrescente de $s$ e queremos que cada elemento de $s$ pertença a exatamente um $d_i$. Ademais, queremos que $p$, o número de sequências decrescentes que compõe $d$, seja o menor possível. Chamaremos tais decomposições $d$ com $p$ mínimo de decomposições mínimas ou decomposições ótimas.

Exemplo 1. Considere a sequência de inteiros $s=(6, 3, 5, 10, 11, 2, 9, 14, 13, 7, 4, 8, 12)$. Uma decomposição ótima $d=(d_0,\dots,d_{p-1})$ para essa sequência é

0: 6 3 2
1: 5 4
2: 10 9 7
3: 11 8
4: 14 13 12

Na decomposição acima, temos $p=5$. É fácil ver que $d$ acima decompõe $s$. Não é imediatamente claro por que $d$ é mínimo, mas isso ficará claro à frente (veja Exercício A abaixo).

Algoritmo guloso (greedy algorithm). Uma ideia natural para se encontrar uma solução $d$ para uma dada sequência $s=(x_0,\dots,x_{N-1})$ é a seguinte. Começamos com $d$ vazio. Suponha agora que $0\leq i<N$ e que já colocamos os $x_j$ com $j<i$ em sequências decrescentes $d_0,\dots,d_{p-1}$. Queremos agora decidir onde colocar $x_i$. Usamos um "critério guloso": escolhemos o menor $k$ tal que, adicionado $x_i$ no fim de $d_k$, continuamos tendo uma sequência decrescente. Caso não exista tal $k$, começamos uma nova sequência $d_p$ formada pelo elemento $x_k$.

Se você executar o algoritmo guloso na sequência $s$ do Exemplo 1, você obterá a decomposição $d=(d_0,d_1,d_2,d_3,d_4)$ dada naquele exemplo.

Você pode achar interessante ver o arquivo greedy.pdf fornecido abaixo, que mostra a relação do problema acima com o jogo de paciência e que também fala da estratégia gulosa (greedy algorithm).

Subsequências crescentes. Seja dada uma sequência de inteiros $s=(x_0,\dots,x_{N-1})$. Estamos interessados em encontrar uma subsequência crescente de $s$ que tenha o maior número de elementos possível.

Exemplo 2. Considere a sequência $s$ de inteiros do Exemplo 1, a saber, $s=(6, 3, 5, 10, 11, 2, 9, 14, 13, 7, 4, 8, 12)$. Observe que $s$ contém a subsequência crescente $c=(3, 5, 7, 8, 12)$ com $5$ elementos. É possível verificar, por inspeção, que $s$ não contém subsequências crescentes com mais de $5$ elementos, de forma que $c$ é uma subsequência crescente mais longa de $s$ (ou uma LIS de $s$, de longest increasing subsequence).

Observação importante. Lembre que vimos uma decomposição $d$ de $s$ com $5$ sequências no Exemplo 1. Vimos no Exemplo 2 uma subsequência crescente $c$ de $s$ com $5$ elementos.

Exercício A. O fato que o número de elementos em $c$ é igual ao número de sequências em $d$ implica que $d$ é uma decomposição mínima e que $c$ é uma subsequência crescente mais longa, isto é, $c$ é uma LIS. Justifique essas duas afirmações (que $d$ é mínimo e que $c$ é máximo, pelo fato de terem os mesmo "tamanho" $5$).  [Sugestão.  Seja $x$ uma subsequência crescente de $s$ e seja $y$ uma subsequência decrescente de $s$.  Quantos elementos em comun podem ter $x$ e $y$?]

Algoritmo para LIS. Vimos que o algoritmo guloso pode ser usado para produzir uma decomposição de uma sequência dada $s$ em subsequências decrescentes. Vamos agora ver como adicionar um pequeno componente àquele algoritmo para encontrar subsequências crescentes de $s$ também.

Considere $s=(x_0,\dots,x_{N-1})$. Fixe $0\leq i<N$ e suponha que já distribuímos os $x_j$ ($j<i$) em sequências decrescentes $d_0,\dots,d_{p-1}$. Usamos o critério guloso para escolher $k$ tal que vamos adicionar $x_i$ à sequência $d_k$ (possivelmente $k=p$, e nesse caso todo os $d_l$ ($l<p$) não mudam e começamos uma nova sequência $d_p=(x_k)$ com um único elemento).

Além de adicionar $x_i$ à sequência $d_k$, fazemos agora $x_k$ "apontar" para o elemento $x_l$ que está no fim da sequência $d_{k-1}$ naquele momento. Note que $x_l<x_i$, pois caso contrário teríamos adicionado $x_i$ à sequência $d_{k-1}$ (lembre que estamos usando o critério guloso).

Você pode achar instrutivo estudar a figura ponteiros.png abaixo, que mostra os tais ponteiros criados no algoritmo acima.

Note que os ponteiros criados pelo algoritmo acima codificam subsequências crescentes da sequência $s$ dada. Além disso, note que essas subsequências crescentes têm número de elementos igual ao número de elementos na decomposição $d$ encontrada para a sequência dada.

Exercício B. Prove que o algoritmo guloso encontra uma decomposição mínima da sequência de entrada $s$ e o esquema adicional de ponteiros descrito acima determina uma LIS de $s$.

Elementos repetidos.  No Exemplo 1, consideramos uma sequência sem repetições ($s$ naquele exemplo é uma permutação dos números $2,\dots,14$). Podemos tratar sequências $s$ com repetições interpretando "sequência crescente" e "sequência decrescente" de forma apropriada: interprete "sequência crescente" como "sequencia estritamente crescente" e "sequência decrescente" como "sequência não-crescente", isto é, sequências $a_0,a_1,a_2,\dots$ com $a_0\geq a_1\geq a_2\geq\dots$.

Implementação.  Uma implementação do algoritmo discutido acima (incluindo o esquema para se encontrar uma LIS) é dada no programa PatiencePlain.java abaixo.