Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Programação Dinâmica: Encontre a maior subsequência comum entre duas sequências

+3 votos
34 visitas
perguntada Jun 7 em Programação Computacional por Adriana Molinari (111 pontos)  
editado Jun 7 por Adriana Molinari

Considere o problema de encontrar a maior subsequência comum entre duas sequências usando programação dinâmica. Discuta esse problema e implemente uma solução.

Compartilhe

1 Resposta

+2 votos
respondida Jun 7 por Adriana Molinari (111 pontos)  
editado Jun 7 por Adriana Molinari

Para resolvermos a questão por programação dinâmica vamos decompor o problema em subproblemas. A ideia é reduzir as sequências que serão comparadas ao menor tamanho possível e achar a maior subsequência comum. Em seguida, incrementamos as sequências a serem comparadas e mais uma vez achamos a maior subsequência comum. Ou seja, encontramos a solução ótima dos subproblemas para então acharmos o ótimo do problema como um todo.

O código abaixo segue os seguintes passos:

  1. Encontraremos a solução do problema usando a matriz M(m+1 x n+1)

  2. Para as posições M[i][0] e M[0][j] da matriz M a solução ótima será 0, tendo em vista que quando comparamos uma sequência com outra sequência de tamanho zero não há subsequência comum

  3. A linha i da matriz M irá guardar o tamanho da maior subsequência comum quando comparamos a sequência que vai do elemento 0 até o elemento i da primeira sequência(seq1) com todos os elementos j da segunda sequência (seq2)

  4. Se o elemento i for igual ao elemento j, então a posição M[i][j] da matriz será preenchida pelo número 1 somado ao elemento da posição na diagonal superior. Ou seja, M[i][j] = M[i-1][j-1] + 1.

  5. Caso o elemento i da primeira sequência (seq1) seja diferente do elemento j da segunda sequência (seq2) então a posição M[i][j] da matriz M será preenchida pela maior subsequência comum entre as sequências que foram avaliadas em M[i-1][j] e M[i][j-1]. Neste caso, M[i][j] = max(M[i-1][j], M[i][j-1])

  6. A matriz M resultante apresenta a solução ótima dos subproblemas

  7. A segunda parte do código nos retorna a maior subsequência comum entre as duas sequências e o seu tamanho

Precisaremos usar a seguinte biblioteca:

import numpy as np  

Implementação:

def longest_common_subsequence(seq1, seq2):  
    # l e c nos retorna o tamanho das strings seq1 e seq1 
    l = len(seq1)  # número de linhas da matriz M
    c = len(seq2)  # número de colunas da matriz M
    # gerando uma matriz de zeros para guardar os valores da programação dinâmica
    M = [[0]*(c + 1) for i in range(l + 1)]
    for i in range(l + 1):  # iterando sobre as linhas da matriz
        for j in range(c + 1):  # iterando sobre as colunas da matriz
            if i == 0 or j == 0:
                M[i][j] = 0
            elif seq1[i-1] == seq2[j-1]:
                M[i][j] = M[i-1][j-1]+1
            else:
                M[i][j] = max(M[i-1][j], M[i][j-1])
    matriz_dp = np.array(M)
    print("M = ", matriz_dp)
    # A segunda parte do código nos retorna a maior subsequência comum e o seu tamanho
    tamanho = M[l][c]
    # Vamos criar uma lista para guardar os elementos da maior subsequência
    subseq = [""] * (tamanho + 1)
    subseq[tamanho] = ""

    # Começando pelo último elemento das sequências
    # Vamos adicionar os elementos comuns às duas sequências à lista subseq
    i = l
    j = c
    while i > 0 and j > 0:
        # Se os elementos em questão de seq1 e seq2 são iguais, então o elemento deve entrar em subseq
        if seq1[i - 1] == seq2[j - 1]:
            subseq[tamanho - 1] = seq1[i - 1]
            i = i - 1 
            j = j - 1
            tamanho = tamanho - 1
        # Caso contrário, devemos seguir a iteração em direação a maior susequência
        elif M[i - 1][j] > M[i][j - 1]:
            i = i - 1
        else:
            j = j - 1 
print("A maior subseqência comum entre", seq1, "e", seq2, "tem tamanho", M[l][c], "e é dada por", "".join(subseq))

Exemplo:

longest_common_subsequence('123456','2456789') 

Output:

M = [[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 1 1 1 1 1 1 1]
[0 1 1 1 1 1 1 1]
[0 1 2 2 2 2 2 2]
[0 1 2 3 3 3 3 3]
[0 1 2 3 4 4 4 4]]
A maior subseqência comum entre 123456 e 2456789 tem tamanho 4 e é dada por 2456

comentou Jul 17 por CP (37 pontos)  
Em programação computacional, um problema bastante parecido com o problema da maior subsequência comum é o problema da maior susbtring comum. No primeiro caso, como apresentado na solução, a maior subsequência comum não precisa ser contínua. Ou seja, deve-se preservar a relação de ordenação presente nas sequências que estão sendo comparadas, entretanto a continuidade não é necessária. Já no problema da maior substring comum, a continuidade deve ser preservada. O seguinte exemplo ilustra a diferença entre os dois problemas.

Considere as seguintes sequências: abcdaf e bcdf. A maior subsequência comum é dada por bcdf. Já a maior substring comum é dada por bcd.
...