Notatnik techniczny

Programowanie dynamiczne #2

Poprzedni wpis z kategorii programowanie dynamiczne: 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.

Programowanie dynamiczne

Pierwsze znaki w obu ciągach to “a”, więc dla komórki (1,1) mamy maksymalną długość 1.

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

Programowanie dynamiczne

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

Programowanie dynamiczne

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

Programowanie dynamiczne

Widzimy, że LCS ma długość 4. Aby poznać wartość tego ciągu, musimy określić drogę, która prowadziła do ostatniego pola. Dla pokazanego zestawu danychx kilka różnych ciągów może spełniać warunek najdłuższego.

Programowanie dynamiczne

Kod demo Python 3

A = "ABRSFBORGSNIDFMSOAFBGNETGRIFNIREYJNBSDF"
B = "UKRYTRIFNIREYJNBSTHDBRHFDHMD"
 
db = [[0 for b in range(len(B)+1)] for a in range(len(A)+1)]
 
for a in range(len(A)):
    prev_row = db[a]
    curr_row = db[a+1]
    a_char = A[a]
    for b in range(len(B)):
        b_char = B[b]
        if a_char == b_char:
            curr_row[b+1] = prev_row[b]+1
            continue
        curr_row[b+1] = max(curr_row[b], prev_row[b+1])
 
a = len(A)
b = len(B)
wynik = []
 
while a > 0 and b > 0:
    a_char = A[a-1]
    b_char = B[b-1]
    if a_char == b_char:
        a -= 1
        b -= 1
        wynik.append(a_char)
        continue
    if db[a-1][b] > db[a][b-1]:
        a -= 1
        continue
    b -= 1
 
print ("".join([str(a) for a in wynik[::-1]]))

Kod demo C++

#include <iostream>
 
using namespace std;
 
char A[] = "ABRSFBORGSNIDFMSOAFBGNETGRIFNIREYJNBSDF";
char B[] = "UKRYTRIFNIREYJNBSTHDBRHFDHMD";
 
constexpr int lenA = sizeof(A) / sizeof(A[0]);
constexpr int lenB = sizeof(B) / sizeof(B[0]);
 
int main() {
    auto C = new int[lenA+1][lenB+1]();  //c++11
 
    for ( int a=0; a < lenA; ++a ) {
        char a_char = A[a];
 
        for (int b = 0; b < lenB; ++b) {
            char b_char = B[b];
            if (a_char == b_char) {
                C[a+1][b+1] = C[a][b]+1;
                continue;
            }
            C[a+1][b+1] = max(C[a+1][b], C[a][b+1]);
        }
    }
 
    int a = lenA;
    int b = lenB;
    string buf;
 
    while (a > 0 and b > 0) {
        char a_char = A[a - 1];
        char b_char = B[b - 1];
        if (a_char == b_char) {
            a --;
            b --;
            buf.append(&a_char,1);
            continue;
        }
        if (C[a - 1][b] > C[a][b - 1]) {
            a --;
            continue;
        }
        b --;
    }
 
    string wynik(buf.rbegin(), buf.rend());
    cout << wynik << endl;
 
 
    return 0;
}

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