algorithm
Najdłuższa wspólna kolejność
Szukaj…
Najdłuższe wspólne wyjaśnienie sekwencji
Jedną z najważniejszych implementacji programowania dynamicznego jest znalezienie najdłuższej wspólnej podsekwencji . Najpierw zdefiniujmy niektóre podstawowe terminologie.
Kolejność:
Podsekwencja to sekwencja, którą można uzyskać z innej sekwencji poprzez usunięcie niektórych elementów bez zmiany kolejności pozostałych elementów. Powiedzmy, że mamy ciąg ABC . Jeśli usuniemy zero lub jeden lub więcej niż jeden znak z tego ciągu, otrzymamy podsekwencję tego ciągu. Tak więc podsekwencje ciągu ABC będą to { „A” , „B” , „C” , „AB” , „AC” , „BC” , „ABC” , „” }. Nawet jeśli usuniemy wszystkie znaki, pusty ciąg będzie również podsekwencją. Aby znaleźć podsekwencję, dla każdego znaku w ciągu mamy dwie opcje - albo przyjmujemy znak, albo nie. Jeśli więc długość ciągu wynosi n , istnieją 2 n podciągów tego ciągu.
Najdłuższa wspólna kolejność:
Jak sama nazwa wskazuje, spośród wszystkich wspólnych podsekwencji między dwoma łańcuchami najdłuższa wspólna podsekwencja (LCS) to ta o maksymalnej długości. Na przykład: Wspólne podsekwencje między „HELLOM” i „HMLD” to „H” , „HL” , „HM” itd. Tutaj „HLL” jest najdłuższym wspólnym podsekwencją o długości 3.
Metoda Brute-Force:
Możemy wygenerować wszystkie podsekwencje dwóch łańcuchów za pomocą śledzenia wstecznego . Następnie możemy je porównać, aby znaleźć typowe podsekwencje. Po tym będziemy musieli znaleźć ten o maksymalnej długości. Widzieliśmy już, że istnieją 2 n podsekwencje ciągu o długości n . Rozwiązanie problemu zajęłoby lata, gdyby nasze n przekroczyło 20-25 .
Metoda programowania dynamicznego:
Podejdźmy do naszej metody z przykładem. Załóżmy, że mamy dwa ciągi abcdaf i acbcf . Oznaczmy je za pomocą s1 i s2 . Zatem najdłuższym wspólnym podsekwencją tych dwóch ciągów będzie „abcf” , który ma długość 4. Ponownie przypominam, podsekwencje nie muszą być ciągłe w ciągu. Aby skonstruować „abcf” , zignorowaliśmy „da” w s1 i „c” w s2 . Jak możemy się tego dowiedzieć za pomocą programowania dynamicznego?
Zaczniemy od tabeli (tablicy 2D) zawierającej wszystkie znaki s1 w rzędzie i wszystkie znaki s2 w kolumnie. Tutaj tabela jest indeksowana do 0, a my umieszczamy znaki od 1 do kolejnych. Przejdziemy przez tabelę od lewej do prawej dla każdego wiersza. Nasz stół będzie wyglądał następująco:
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 | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Tutaj każdy wiersz i kolumna reprezentują długość najdłuższego wspólnego podsekwencji między dwoma łańcuchami, jeśli weźmiemy znaki tego wiersza i kolumny i dodamy do przedrostka przed nim. Na przykład: Tabela [2] [3] reprezentuje długość najdłuższej wspólnej podsekwencji między „ac” i „abc” .
0-ta kolumna reprezentuje pustą podsekwencję s1 . Podobnie 0-ty rząd reprezentuje pustą podsekwencję s2 . Jeśli weźmiemy pusty podciąg łańcucha i spróbujemy dopasować go do innego łańcucha, bez względu na długość drugiego podłańcucha, wspólny podciąg będzie miał długość 0. Możemy więc wypełnić 0-te rzędy i 0-te kolumny zerami. Otrzymujemy:
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Zaczynajmy. Kiedy wypełniamy tabelę [1] [1] , zadajemy sobie pytanie, czy jeśli mielibyśmy ciąg a i kolejny ciąg a i nic więcej, jaka będzie najdłuższa wspólna podsekwencja? Długość LCS tutaj będzie wynosić 1. Spójrzmy teraz na Tabelę [1] [2] . Mamy ciąg ab i ciąg a . Długość LCS będzie wynosić 1. Jak widać, reszta wartości będzie również równa 1 dla pierwszego wiersza, ponieważ uwzględnia tylko łańcuch a z abcd , abcda , abcdaf . Nasz stół będzie wyglądał następująco:
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Dla wiersza 2, który będzie teraz obejmował c . Dla tabeli [2] [1] mamy ac z jednej strony i a z drugiej strony. Zatem długość LCS wynosi 1. Skąd wzięliśmy ten 1? Od góry, co oznacza LCS a między dwoma podciągami. Mówimy więc, że jeśli s1 [2] i s2 [1] nie są takie same, to długość LCS będzie maksymalną długością LCS u góry lub po lewej stronie . Biorąc pod uwagę długość LCS u góry, oznacza to, że nie bierzemy obecnej postaci z s2 . Podobnie, biorąc pod uwagę długość LCS po lewej stronie, oznacza to, że nie bierzemy obecnego znaku z s1, aby utworzyć LCS. Otrzymujemy:
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Tak więc naszą pierwszą formułą będzie:
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
Przechodząc dalej, do tabeli [2] [2] mamy ciąg ab i ac . Ponieważ C i B nie są takie same, możemy umieścić maksymalnie górę lub w lewo tutaj. W tym przypadku jest to znowu 1. Następnie, dla tabeli [2] [3] mamy ciąg abc i ac . Tym razem aktualne wartości zarówno wiersza, jak i kolumny są takie same. Teraz długość LCS będzie równa maksymalnej dotychczasowej długości LCS + 1. Jak uzyskać maksymalną długość LCS do tej pory? Sprawdzamy wartość przekątną, która reprezentuje najlepsze dopasowanie między ab a a . Z tego stanu dla bieżących wartości dodaliśmy jeszcze jeden znak do s1 i s2, które okazały się być takie same. Długość LCS oczywiście wzrośnie. W tabeli [2] [3] umieścimy 1 + 1 = 2 . Dostajemy
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Zatem naszą drugą formułą będzie:
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
Zdefiniowaliśmy oba przypadki. Korzystając z tych dwóch formuł, możemy wypełnić całą tabelę. Po wypełnieniu tabeli będzie wyglądać następująco:
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 |
+-----+-----+-----+-----+-----+-----+-----+-----+
Długość LCS między s1 i s2 będzie wynosić Tabela [5] [6] = 4 . Tutaj 5 i 6 są odpowiednio długością s2 i s1 . Nasz pseudo-kod będzie:
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]
Złożoność czasowa dla tego algorytmu wynosi: O (mn) gdzie m i n oznacza długość każdego łańcucha.
Jak znaleźć najdłuższą wspólną podsekwencję? Zaczniemy od prawego dolnego rogu. Sprawdzimy, skąd pochodzi wartość. Jeśli wartość pochodzi z przekątnej, to znaczy, jeśli tabela [i-1] [j-1] jest równa tabeli [i] [j] - 1 , naciskamy albo s2 [i], albo s1 [j] (oba są takie same) i poruszają się po przekątnej. Jeśli wartość pochodzi z góry, oznacza to, że jeśli Tabela [i-1] [j] jest równa Tabeli [i] [j] , przechodzimy na górę. Jeśli wartość pochodzi z lewej strony, oznacza to, że jeśli Tabela [i] [j-1] jest równa Tabeli [i] [j] , przechodzimy w lewo. Gdy dojdziemy do lewej lub najwyższej kolumny, nasze wyszukiwanie się kończy. Następnie usuwamy wartości ze stosu i drukujemy je. Pseudo-kod:
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
Należy zauważyć: jeśli zarówno Tabela [i-1] [j], jak i Tabela [i] [j-1] jest równa Tabeli [i] [j] i Tabela [i-1] [j-1] nie jest równe tabeli [i] [j] - 1 , dla tego momentu mogą istnieć dwa LCS. Ten pseudo-kod nie uwzględnia tej sytuacji. Musisz rozwiązać to rekurencyjnie, aby znaleźć wiele LCS.
Złożoność czasowa dla tego algorytmu wynosi: O (maks. (M, n)) .
