E09 LIS Longest Increasing Subsequence
Nas aulas de 14/9/2021 e 16/9/2021, discutimos o Problema da Subsequência Crescente Mais Longa (SSC Mais Longa, SSCML) ou Longest Increasing Subsequence (LIS). O Exercício T06 também trata desse assunto. Estude o enunciado do T06 antes continuar.
Neste exercício, você deverá implementar o algoritmo guloso para jogar paciência, e deve adicionar elementos ao seu programa para que ele também produza uma SSC Mais Longa (SSCML). Seu programa deve chamar-se Patience.java.
Modos de execução. Patience.java deve ter três modos de execução, como ilustrados a seguir:
$ java-algs4 RandomSeq 10 20 121
13 6 6 8 1 19 0 19 17 19
$ java-algs4 RandomSeq 10 20 121 | java-algs4 Patience
LIS: 4 elements
$ java-algs4 RandomSeq 10 20 121 | java-algs4 Patience +
LIS:
0: 2 / 6
1: 3 / 8
2: 8 / 17
3: 9 / 19
LIS: 4 elements
$ java-algs4 RandomSeq 10 20 121 | java-algs4 Patience ++
0: 13 6 6 1 0
1: 8
2: 19 19 17
3: 19
LIS:
0: 2 / 6
1: 3 / 8
2: 8 / 17
3: 9 / 19
LIS: 4 elements
Sem nenhum argumento, Patience.java fornece apenas o número de elementos em uma SSC mais longa (SSCML). Com o argumento "+", ele deve também produzir uma SSCML. Note que se a entrada é \(s=(s_0,s_1,\dots,s_{N-1})\), os elementos da SSCML são dados na forma "\(i\) / $s_i$".
Observação importante. Note que, para a saída ser uma SSC, é necessário que os valores de $i$ sejam crescentes e os valores de $s_i$ também sejam crescentes. Em particular, não basta os $s_i$ serem crescentes. No exemplo acima, os $i$ são crescentes $(2, 3, 8, 9)$ e os $s_i$ são crescentes $(6, 8, 17, 19)$. Note que a sequência $(0,8,17,19)$, formada pelos topos das pilhas, é uma sequência crescente, mas não é uma subsequência da sequência original, e portanto não é uma SSCML.
Finalmente, com o argumento "++", Patience.java deve imprimir as pilhas de cartas obtidas pelo algoritmo guloso.
Algoritmo linearítmico, isto é, $O(N\log N)$. Patience.java deve implementar o algoritmo guloso, de forma que ele tenha complexidade de tempo $O(N\log N)$ e complexidade de espaço $O(N)$ para entradas com $N$ elementos. Para tanto, use, obrigatoriamente, Stack.java de S&W, que tem complexidade $O(1)$ para operações de inicialização e push().
O algoritmo baseado em programação dinâmica. É possível resolver o SSCML reduzindo-o ao Problema da Subsequência Comum Mais Longa (LCS, Longest Common Subsequence): dada uma sequência $s=(s_0,s_1,\dots,s_{N-1})$, produzimos uma sequência $t=(t_0,t_1,\dots,t_{M-1})$ da seguinte forma: ordenamos $s_0,\dots,s_{N-1}$ e removemos repetições. Ai então encontramos um LCS entre $s$ e $t$. Esse algoritmo está implementado no programa LISDP.java abaixo. Esta solução, que é baseada em programação dinâmica, funciona bem nos casos em que $M$ é pequeno (número de elementos distintos em $s$).
Exemplos de execução. Exemplos de execução são dados nos arquivos experiments*.txt abaixo.
Entrega. Neste exercício, basta você entregar seu programa Patience.java.
Observação (adicionada 28/10/2021). Por conta de o que escrevi neste item no fórum, resolvi refazer os experimentos neste enunciado e fazer mais alguns experimentos. Arquivos adicionais foram anexados ao enunciado.
- 18 de octubre de 2021, 19:52
- 18 de octubre de 2021, 19:52
- 28 de octubre de 2021, 09:12
- 28 de octubre de 2021, 09:12
- 28 de octubre de 2021, 09:12
- 28 de octubre de 2021, 09:12
- 28 de octubre de 2021, 09:12