algorithm
La più lunga successiva in comune
Ricerca…
La più lunga Spiegazione successiva
Una delle implementazioni più importanti della programmazione dinamica è scoprire la più lunga sequenza secondaria . Definiamo prima alcune delle terminologie di base.
Sotto sequenza:
Una sottosequenza è una sequenza che può essere derivata da un'altra sequenza eliminando alcuni elementi senza modificare l'ordine degli elementi rimanenti. Diciamo che abbiamo una stringa ABC . Se cancelliamo zero o uno o più di un carattere da questa stringa otteniamo la sottosequenza di questa stringa. Quindi le sottosequenze della stringa ABC saranno { "A" , "B" , "C" , "AB" , "AC" , "BC" , "ABC" , "" }. Anche se rimuoviamo tutti i caratteri, la stringa vuota sarà anche una sottosequenza. Per scoprire la sottosequenza, per ogni personaggio in una stringa, abbiamo due opzioni: o prendiamo il personaggio o non lo facciamo. Quindi se la lunghezza della stringa è n , ci sono 2 n sottosequenze di quella stringa.
La più lunga comune successiva:
Come suggerisce il nome, tra tutte le sottosequenze comuni tra due stringhe, la sottosequenza comune più lunga (LCS) è quella con la lunghezza massima. Ad esempio: Le sottosequenze comuni tra "HELLOM" e "HMLD" sono "H" , "HL" , "HM" ecc. Qui "HLL" è la sottosequenza comune più lunga che ha lunghezza 3.
Metodo a forza bruta:
Possiamo generare tutte le sottosequenze di due stringhe usando il backtracking . Quindi possiamo confrontarli per scoprire le sottosequenze comuni. Dopo avremo bisogno di trovare quello con la lunghezza massima. Abbiamo già visto che ci sono 2 n sottosequenze di una stringa di lunghezza n . Ci vorrebbero anni per risolvere il problema se le nostre n croci 20-25 .
Metodo di programmazione dinamica:
Avviciniamoci al nostro metodo con un esempio. Supponiamo che, abbiamo due stringhe abcdaf e acbcf . Indichiamo questi con s1 e s2 . Quindi la sottosequenza comune più lunga di queste due stringhe sarà "abcf" , che ha lunghezza 4. Ancora una volta vi ricordo che le sottosequenze non devono essere continue nella stringa. Per costruire "abcf" , abbiamo ignorato "da" in s1 e "c" in s2 . Come lo scopriamo usando la programmazione dinamica?
Inizieremo con una tabella (una matrice 2D) con tutti i caratteri di s1 in una riga e tutti i caratteri di s2 nella colonna. Qui la tabella è 0-indexed e inseriamo i caratteri da 1 in poi. Attraverseremo il tavolo da sinistra a destra per ogni riga. La nostra tabella sarà simile a:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Qui ogni riga e colonna rappresentano la lunghezza della sottosequenza comune più lunga tra due stringhe se prendiamo i caratteri di quella riga e colonna e aggiungiamo al prefisso prima di esso. Ad esempio: Table [2] [3] rappresenta la lunghezza della sottosequenza comune più lunga tra "ac" e "abc" .
La colonna 0 ° rappresenta la sottosuccessione vuota di s1 . Allo stesso modo la riga 0 ° rappresenta la sottosequenza vuota di s2 . Se prendiamo una sottosequenza vuota di una stringa e proviamo ad abbinarla ad un'altra stringa, indipendentemente dalla lunghezza della seconda sottostringa, la sottosuccessione comune avrà lunghezza 0. Quindi possiamo riempire le righe 0-esime e le colonne 0-esime con 0. Noi abbiamo:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Cominciamo. Quando riempiamo Table [1] [1] , ci stiamo chiedendo, se avessimo una stringa a e un'altra stringa a e nient'altro, quale sarà la sottosequenza comune più lunga qui? La lunghezza dell'LCS qui sarà 1. Ora diamo un'occhiata a Table [1] [2] . Abbiamo string ab e string a . La lunghezza dell'LCS sarà 1. Come puoi vedere, il resto dei valori sarà anche 1 per la prima riga poiché considera solo la stringa a con abcd , abcda , abcdaf . Quindi il nostro tavolo sarà simile a:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Per la riga 2, che includerà ora c . Per la tabella [2] [1] abbiamo ac su un lato e una dall'altro. Quindi la lunghezza della LCS è 1. Da dove abbiamo preso questo 1? Dall'alto, che indica la LCS a tra due sottostringhe. Quindi, quello che stiamo dicendo è che se s1 [2] e s2 [1] non sono gli stessi, allora la lunghezza dell'LCS sarà il massimo della lunghezza di LCS in alto o a sinistra . Prendendo la lunghezza della LCS in alto denota che, non prendiamo il carattere corrente da s2 . Allo stesso modo, Prendendo la lunghezza del LCS a sinistra denota che, non prendiamo il carattere corrente da s1 per creare l'LCS. Noi abbiamo:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Quindi la nostra prima formula sarà:
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
Andando avanti, per Table [2] [2] abbiamo string ab e ac . Dato che c eb non sono gli stessi, mettiamo il massimo della cima o della sinistra qui. In questo caso, è ancora 1. Dopo di ciò, per Table [2] [3] abbiamo string abc e ac . Questa volta i valori correnti di entrambe le righe e colonne sono gli stessi. Ora la lunghezza dell'LCS sarà uguale alla lunghezza massima di LCS finora + 1. Come otteniamo la lunghezza massima di LCS finora? Controlliamo il valore diagonale, che rappresenta la migliore corrispondenza tra ab e a . Da questo stato, per i valori attuali, abbiamo aggiunto un altro carattere a s1 e s2, che è risultato essere lo stesso. Quindi ovviamente aumenterà la lunghezza di LCS. Inseriremo 1 + 1 = 2 nella Tabella [2] [3] . Noi abbiamo,
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Quindi la nostra seconda formula sarà:
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
Abbiamo definito entrambi i casi. Usando queste due formule, possiamo popolare l'intera tabella. Dopo aver riempito il tavolo, sarà simile a questo:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
+-----+-----+-----+-----+-----+-----+-----+-----+
La lunghezza dell'LCS tra s1 e s2 sarà Table [5] [6] = 4 . Qui, 5 e 6 sono rispettivamente la lunghezza di s2 e s1 . Il nostro pseudo-codice sarà:
Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
Table[0][i] = 0
endfor
for i from 1 to s2.length
Table[i][0] = 0
endfor
for i from 1 to s2.length
for j from 1 to s1.length
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
else
Table[i][j] = max(Table[i-1][j], Table[i][j-1])
endif
endfor
endfor
Return Table[s2.length][s1.length]
La complessità temporale per questo algoritmo è: O (mn) dove m e n denota la lunghezza di ciascuna stringa.
Come scopriamo la sottosequenza comune più lunga? Inizieremo dall'angolo in basso a destra. Controlleremo da dove arriverà il valore. Se il valore proviene dalla diagonale, ovvero se Table [i-1] [j-1] è uguale a Table [i] [j] - 1 , spingiamo s2 [i] o s1 [j] (entrambi sono uguali) e si muovono in diagonale. Se il valore proviene dall'alto, ciò significa che se Tabella [i-1] [j] è uguale a Tabella [i] [j] , passiamo all'inizio. Se il valore proviene da sinistra, ciò significa che se Table [i] [j-1] è uguale a Table [i] [j] , ci spostiamo a sinistra. Quando raggiungiamo la colonna più a sinistra o più in alto, la ricerca termina. Quindi inseriamo i valori dallo stack e li stampiamo. Lo pseudo-codice:
Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
S.push(s1[j]) //or S.push(s2[i])
i := i - 1
j := j - 1
else if Table[i-1][j] == Table[i][j]
i := i-1
else
j := j-1
endif
endwhile
while S is not empty
print(S.pop)
endwhile
Punto da notare: se la tabella [i-1] [j] e la tabella [i] [j-1] sono uguali a Tabella [i] [j] e Tabella [i-1] [j-1] non è uguale a Table [i] [j] - 1 , ci possono essere due LCS per quel momento. Questo pseudo-codice non considera questa situazione. Dovrai risolvere questo in modo ricorsivo per trovare più LCS.
La complessità temporale per questo algoritmo è: O (max (m, n)) .