Programowanie dynamiczne #2


Poprzedni wpis z kategorii programowanie dynamiczne: część pierwsza – Longest Increasing Sequence

Zadanie – Longest Common Subsequence

Mamy dwa ciągi znaków, znajdź najdłuższa możliwą sekwencje znaków (niekoniecznie kolejnych), występującą w obydwu ciągach.

Przykład:
A = ABRSFBORGSNIDFMSOAFBGNETGRIFNIREYJNBSDF
B = UKRYTRIFNIREYJNBSTHDBRHFDHMD
Wynik:  RTRIFNIREYJNBSDF

Rozwiązanie – programowanie dynamiczne

Algorytm

Rozpatrzmy uproszczony przypadek.

A = “abcdef”
B = “accbdea”

Czy wiedząc, że najdłuższym wspólnym podciągiem dla “abc” oraz “acc” jest “ac”, możemy jakoś wykorzystać tę informację i stwierdzić, jaki będzie najdłuższy wspólny podciąg, gdy dopiszemy jedną literkę do pierwszego ciągu? Przedstawmy naszą wiedzę w tabeli. Wartości w komórkach przedstawiają długość najdłuższego wspólnego podciągu. Możemy stwierdzić, że najdłuższy wspólny podciąg będzie zawsze mniejszy lub równy krótszemu z argumentów. Dzięki tej informacji możemy wypełnić pierwszą kolumnę i pierwszy wiersz zerami.

q1

Pierwsze znaki w obu ciągach to “a”, więc dla komórki (1,1) mamy maksymalną długość 1. Wartości w pierwszym rzędzie reprezentują następujące sytuacje:

Widzimy, że skoro pierwsze znaki pasują do siebie, to bez względu na kolejne wartości tak długo, jak jeden z argumentów będzie miał długość 1, to maksymalna długość wspólnego podciągu również będzie jeden.  Wypełniliśmy pierwszy rzad i pierwszą kolumnę.

Programowanie dynamiczne

Teraz do naszych dwóch jednoznakowych ciągów dopisujemy po jednej literce. Jaka będzie LCS dla {“ac“, “ab“}? Czy możemy wykorzystać naszą tabelkę, aby odpowiedzieć na to pytanie?
Dodane literki są różne, więc nie mogą wydłużyć naszego zaczętego przez pierwsze znaki ciągu, natomiast nie są one również zdolne do pogorszenia obecnej sytuacji.
W obecnym momencie LCS(ac, ab) = MAX(LCS(ac, a), LCS(a, ab)) = 1.

Programowanie dynamiczne

Ile wynosi LCS(“ac”, “abc“)? Dokładamy jeden znak, taki że ostatnie znaki są identyczne, czyli ostatnie znaki z obu argumentów są częścią naszego wspólnego ciągu.  LCS(ac, abc) = LCS(a, ab) + 1 = 2

Longest Common Subsequence

Możemy teraz napisać formułę matematyczną określającą maksymalną długość LCS.

  C[n,0] = C[0,n] = 0 \quad dla \quad n \in \mathcal{N} \vspace{10 mm} \newline  C[i,j] = C[i-1, j-1] + 1 \quad dla \quad X[i] = X[j] \newline  C[i,j] = MAX(C[i-1, j], C[i, j-1]) \quad dla \quad X[i] \neq X[j] \newline

Wykorzystując otrzymaną zależność, wypełniamy naszą tabelę.

Longest Common Subsequence

Widzimy, że LCS ma długość 4.
Teraz pytanie, jak określić wartość tego ciągu, a nie tylko długość? Aby to zrobić, musimy określić drogę, która prowadziła do ostatniego pola. Należy zaznaczyć, że dla danego zestawu danych wejściowych kilka różnych ciągów może spełniać warunek najdłuższego.

q6_

Kod demo Python 3

Kod demo C++

Dyskusja złożoności

Tablica C zawiera n*m elementów, wyliczenie wartości elementu tabeli C wymaga inspekcji nie więcej niż trzech innych elementów tej tablicy. Tak więc mamy złożoność obliczeniową O(m*n). Rekonstrukcja ciągu wymaga nie więcej niż O(m+n) operacji. Finalna złożoność obliczeniowa to O(m*n).

Pamięciowo potrzebujemy M(m*n) elementów tabeli C.

Powyższe rozwiązanie ma na celu pokazanie idei programowania dynamicznego. Autor zdaje sobie sprawę, że jest możliwe dalsze zmniejszenie wymagań pamięciowych.

Wytłumaczenie Video [EN]

 

Odnośniki

Dodaj komentarz

Twój adres email nie zostanie opublikowany.