Nous avons abordé les sous-problèmes de chevauchement et les propriétés de sous-structure optimales des ensembles 1 et 2, respectivement. Nous avons également abordé un exemple de problème dans la série 3. Expliquons maintenant le problème de la plus longue sous-séquence commune (LCS) en tant que problème supplémentaire pouvant être résolu à l'aide de la programmation dynamique.
Déclaration de problème LCS: Étant donné deux séquences, trouvez la longueur de la plus longue sous-séquence présente dans les deux. Une sous-séquence est une séquence qui apparaît dans le même ordre relatif, mais pas nécessairement contigu. Par exemple, “abc”, “abg”, “bdf”, “aeg”, “” acefg ”, etc. sont des sous-séquences de“ abcdefg ”. Ainsi, une chaîne de longueur n a 2 ^ n-1 différentes sous-séquences possibles.
Il s’agit d’un problème informatique classique, à la base de diff (un programme de comparaison de fichiers qui affiche les différences entre deux fichiers), et qui a des applications en bioinformatique.
Exemples:
LCS pour les séquences d'entrée «ABCDGH» et «AEDFHR» est «ADH» de longueur 3.
LCS pour les séquences d'entrée "AGGTAB" et "GXTXAYB" est "GTAB" de longueur 4.
La solution naïve à ce problème consiste à générer toutes les sous-séquences des deux séquences données et à trouver la sous-séquence correspondante la plus longue. Cette solution est exponentielle en terme de complexité temporelle. Voyons comment ce problème possède les deux propriétés importantes d'un problème de programmation dynamique (DP).
Sous-structure optimale:
Soit X [0..m-1] et Y [0..n-1] de longueur m et n respectivement. Soit L (X [0..m-1], Y [0..n-1]) la longueur de LCS des deux séquences X et Y. Voici la définition récursive de L (X [0 .. m-1], Y [0..n-1]).
Si les derniers caractères des deux séquences correspondent (où X [m-1] == Y [n-1]), alors
L (X [0..m-1], Y [0..n-1]) = 1 + L (X [0..m-2], Y [0..n-2])
Si les derniers caractères des deux séquences ne correspondent pas (où X [m-1]! = Y [n-1]), alors
L (X [0..m-1], Y [0..n-1]) = MAX (L (X [0..m-2], Y [0..n-1]), L ( X [0..m-1], Y [0..n-2])).
Exemples:
1) Considérez les chaînes d'entrée «AGGTAB» et «GXTXAYB». Les derniers caractères correspondent aux chaînes. Donc, la longueur de LCS peut être écrite comme suit:
L («AGGTAB», «GXTXAYB») = 1 + L («AGGTA», «GXTXAY»)
Considérant les chaînes d'entrée "ABCDGH" et "AEDFHR. Les derniers caractères ne correspondent pas pour les chaînes. Donc, la longueur de LCS peut être écrite comme suit:
L ("ABCDGH", "AEDFHR") = MAX (L ("ABCDG", "AEDFHR"), L ("ABCDGH", "AEDFH")) Le problème LCS a donc une propriété de sous-structure optimale, le problème principal pouvant être résolu en utilisant des solutions aux sous-problèmes.
Chevauchement de sous-problèmes:
Voici une implémentation récursive simple du problème LCS. La mise en œuvre suit simplement la structure récursive mentionnée ci-dessus.
Fonction LCS(x,y :chaine de caractére ; m,n :entier ;)
Debut
Si(m=0 ou n=0) alors retourner 0 ;
Si(x[m-1]=y[n-1]) alors retourner 1+lcs(x,y,m-1, n-1)
Sinon retourner max(lcs(x,y,m,n-1), lcs(x,y,m-1,n))
Fin fonction
La complexité temporelle de l'approche récursive naïve ci-dessus est O (2 ^ n) dans le pire des cas et le pire des cas se produit lorsque tous les caractères de X et Y ne correspondent pas, c'est-à-dire que la longueur de LCS est égale à 0.
Compte tenu de l'implémentation ci-dessus, voici un arbre de récursion partielle pour les chaînes d'entrée «AXYT» et «AYZX».
Dans l’arbre de récursion partielle ci-dessus, lcs (“AXY”, “AYZ”) est résolu deux fois. Si nous dessinons l’arbre de récursion complet, alors nous pouvons voir qu’il existe de nombreux sous-problèmes qui sont résolus à plusieurs reprises. Ce problème a donc une propriété de sous-structure se chevauchant et le recalcul des mêmes sous-problèmes peut être évité en utilisant la mémorisation ou la tabulation. Voici une mise en œuvre tabulée pour le problème LCS.
Fonction lcs (x, y :chaine caractéres ; m,n :entier) :entier
Var L :tableau [1..n+1, 1..m+1] d’entier
I,j :entier ;
Debut
Pour iß 0 à m faire
Pour j ß 0 à n faire
Si(i=0 ou j=0) l[i][j]=0 ;
Sinon si x[i-1]=y[j-1] alors L[i][j]ß L[i-1]L[j-1]+1 ;
Sinon L[i][j]ß max (L[i-1][j],L[i][j-1]);
Fin
Fin
Fin
Retourner L[m][n]
Complexité :
La complexité de la mise en œuvre ci-dessus est O (mn), ce qui est bien meilleur que la complexité temporelle de la mise en œuvre Naive Recursive dans le pire des cas.