terça-feira, 13 de novembro de 2012

Programação Dinâmica - Maior Subsequência Comum

O problema da maior subsequência comum (longest commom subsequence) (LCS) é o problema de encontrar a maior subsequência comum a duas sequências X e Y. Este é um problema clássico para
compação de arquivos e bioinformática.

Uma subsequência de uma sequência X de caracteres  pode ser obtida removendo alguns caracteres dessa sequência. Por exemplo,

Considere a seguinte sequência X = ABCBDAB, podemos obter  2^|X| subsequência  distintas de X. Por exemplo, BCBDAB e ACDAB são uma subsequência de X.
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX 100
using namespace std;
int main()
{

    char X [MAX];
    char temp[MAX];
    int m;

    scanf("%s",X);

    m = strlen(X);

    int i,j,index;

    for(i = 0; i < 1<<m ; i++){
        index = 0;
        for(j=0; j<m; j++){
            if( (i & (1<<j)) != 0 ){
              temp[index++] = X[j];
            }
        }
        temp[index] = '\0';
        printf("%s\n",temp);
    }

    return 0;
}
Entrada
BCBD
Saída
B
C
BC
B
BB
CB
BCB
D
BD
CD
BCD
BD
BBD
CBD
BCBD


A solução força bruta consiste em comparar cada subsequencia de X com os símbolos de Y.

Se |X| = m, |Y| = n ,  $2^m$ subsequência de X então a solução força bruta é O(n$2^m$).

Algoritmo Força Bruta
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX 100

using namespace std;

int main()
{

    char X [MAX];
    char Y [MAX];
    char temp[MAX];
    char sol[MAX];
    int m;
    int n;
    int maior, cont;
    int index;

    scanf("%s %s",X,Y);

    m = strlen(X);
    n = strlen(Y);

    int i,j;
    maior = 0;

    for(i = 0; i < 1<<m ; i++){
        index = 0;
        for(j=0; j<m; j++){
            if( (i & (1<<j)) != 0 ){
              temp[index++] = X[j];
            }
        }
        temp[index] = '\0';
        printf("%s\n",temp);

        cont = 0;
        for(j=0;j<n && temp[cont]!='\0';j++){
          if(Y[j] == temp[cont]){
            cont++;
          }
        }

        if(temp[cont]=='\0' && cont > maior){
          maior = cont;
          strcpy(sol,temp);
        }

    }


    printf("%d\n",maior);
    printf("%s\n",sol);



    return 0;
}
Entrada
ABCBDAB BDCABA 
Saída

BCBA

Visualmente, a solução ótima pode ser vista da seguinte maneira:

AB-C-BDAB 
 | | | |
-BDCAB-A- 

Para diminuir a complexidade para resolver este problema, primeiramente, precisamos encontrar uma maneira de decompor o problema grande em termos de subproblemas menores de tal maneira que a solução ótima do problema maior dependa da solução ótima de subproblemas menores. Essa propriedade chamamos de subestrutura ótima.

Definição do problema c[i,j] = problema de encontrar a maior subsequencia comum das seguintes sequência X[1..i] e Y[1..j]. Essas duas sequências são sequências prefixos das sequências inicias.

Subsestrutura Ótima
Caso Base:

  • Se i=0 ou j=0 então c[i,j] = 0. Se umas das sequências é nula então a maior sequência comum também é nula.


  • Se X[i]=X[j] então c[i,j] = c[i-1,j-1] + 1. Se o último caracter for igual nas duas sequências então este caractere está na maior subsequencia comum e podemos reduzir o problema para c[i-1,j-1].


  • Se X[i]!=X[j] então c[i,j] = max(c[i,j-1],c[i-1,j]). Se o último caracter não for igual nas duas sequências então temos duas opções: 
    • deletamos o último caractere da sequência Y e comparamos com a sequência X completa(c[i,j-1])  
    • deletamos o último caractere da sequência X e comparamos com a sequência Y completa(c[i-1,j])
          A solução ótima será dada pelo máximo entre os dois subproblemas.

Algoritmo programação dinâmica

    int n,m;
    int i,j;

    scanf("%s",X);
    scanf("%s",Y);
    
    n = strlen(X);
    m = strlen(Y);

    for(i=0;i<=n;i++)
      c[i][0] = 0;

    for(j=0;j<=m;j++)
      c[0][j] = 0;


    for(i=1;i<=n;i++)
      for(j=1;j<=m;j++)
        if(X[i-1]==Y[j-1])
          c[i][j] = c[i-1][j-1] + 1;
        else
          c[i][j] = max( c[i-1][j] , c[i][j-1]);



    printf("%d\n",c[n][m]);

Entrada
ABCBDAB BDCABA
Saída
 4

A tabela com todos os subproblemas obtida é:

c
B D C A B A

0 0 0 0 0 0 0
A 0 0 0 0 1 1 1
B 0 1 1 1 1 2 2
C 0 1 1 2 2 2 2
B 0 1 1 2 2 3 3
D 0 1 2 2 2 3 3
A 0 1 2 2 3 3 4
B 0 1 2 2 3 4 4


Consultando a tabela, podemos descobrir a solução do problema lcs('AB','BD') = 1 (vermelho) ou do problema lcs('ABCB','BDCAB') = 3 (azul).

A maior subsequência comum pode ser extraída da tabela da seguinte maneira:
i = n;
j = m;

stack <char> pilha;

while(i!=0 && j!=0){
   if(X[i-1]==Y[j-1]){
      pilha.push(X[i-1]);
      i--;
      j--;
    }else if(c[i-1][j] > c[i][j-1]){
      i--;
    }else{
      j--;
    }
}

while( !pilha.empty() ){
    cout << pilha.top() ;
    pilha.pop();
}
cout << endl;

A maior subsequência comum pode ser obtida recursivamente da seguinte maneira:
void lcs(int i,int j){
  if(i!=0 && j!=0){
      if(X[i-1]==Y[j-1]){
        lcs(i-1,j-1);
        printf("%c",X[i-1]);
      }else if(c[i-1][j] > c[i][j-1]){
        lcs(i-1,j);
      }else{
        lcs(i,j-1);
      }
  }
}

Chamada
lcs(n,m);
cout << endl;

Para calcular a solução de um subproblema em particular, precisamos apenas de duas linhas para obter a solução dos subproblemas c[i-1,j], c[i,j-1], c[i-1,j-1]. Podemos otimizar a utilização da memória aproveitando este fato da seguinte maneira:
char X[MAXN];
char Y[MAXN];
int c[2][MAXN];

int n,m;
int i,j;

scanf("%s",X);
scanf("%s",Y);

n = strlen(X);
m = strlen(Y);

for(j=0;j<=m;j++)
  c[0][j] = 0;

for(i=1;i<=n;i++)
  for(j=1;j<=m;j++)
    if(X[i-1]==Y[j-1])
      c[i&1][j] = c[(i-1)&1][j-1] + 1;
    else
       c[i&1][j] = max(c[(i-1)&1][j] , c[i&1][j-1]);

printf("%d\n",c[n&1][m]);
Este problema tem variações interessantes:
  • Encontrar a menor supersequência comum entre duas string. Por exemplo, a menor supersequência comum entre AAATTT e GAATCT é GAAATCTT. Observe que AAATTT e GAATCT são subsequência de GAAATCTT e GAAATCTT é a menor sequência com essa propriedade.Esse problema foi explorado em: http://br.spoj.pl/problems/PARQUE/
  •  Encontrar a menor distância entre duas strings A e B. A distância entre duas string é dada pelo menor número de operações necessária para transformar A em B. As operações permitidas são deletar um caractere, adicionar um caractere ou substituir um caractere por outro. Pode ser encontrado aqui: http://www.spoj.pl/problems/EDIST/
Links interessantes:

4 comentários:

Renata Ghisloti Duarte de Souza Granha disse...

Legal! Adorei o blog! :)

David disse...

Essa função max é nativa do C?

Leonardo Lima disse...

Muito bom. Parabéns pelo blog.

agora eu tenho dois desafios pra você:

dado 1 string contendo apenas pontos e hifens ex.: "----..---..---.-.-" queremos descobrir a maior substring que se repete nela. no caso seria: "---..---."

outro problema: dado uma string "BANANAS" queremos descobrir qual maior subsequencia que fixada alguma letra seria Palindromo. ex: fixando o B no exemplo teriamos "ANBNA"

Anônimo disse...

Cara muito bom! Gostei muito!