Programowanie dynamiczne #2

Zadanie – Longest Common Subsequence

Rozwiązanie – programowanie dynamiczne

Rozpatrzmy uproszczony przypadek.

A = “abcdef”
B = “accbdea”

Jeśli wiadomo, że najdłuższym wspólnym podciągiem dla abc oraz acc jest ac, można wykorzystać tę informację do określenia najdłuższego wspólnego podciągu po dopisaniu jednej litery do pierwszego ciągu. Podstawową obserwacją jest to, że najdłuższy wspólny podciąg będzie zawsze mniejszy lub równy długości krótszego z argumentów. Z tego wynika, że pierwszą kolumnę i pierwszy wiersz można wypełnić zerami. Wartości w komórkach tabeli reprezentują długość najdłuższego wspólnego podciągu.

Pierwsze znaki w obu ciągach to a, dlatego dla komórki (1,1) maksymalna długość wynosi 1. Ponieważ pierwsze znaki się pasują, maksymalna długość wspólnego podciągu dla ciągów o długości 1 wynosi również 1. Pierwszy rząd i pierwsza kolumna zostały wypełnione.

Do dwóch jednoznakowych ciągów dopisuje się po jednej literce. Obliczenie LCS dla LCS(ac, ab) wymaga wykorzystania tabeli. Dodane znaki są różne, więc nie mogą wydłużyć wspólnego podciągu rozpoczętego pierwszymi znakami. Ponadto nie pogarszają wyniku. Uzyskana zależność to:

Wartość LCS(ac, abc) uzyskuje się poprzez dodanie znaku w taki sposób, że ostatnie znaki obu ciągów są identyczne i stanowią część wspólnego podciągu.

Formuła matematyczna określająca maksymalną długość LCS przyjmuje postać:

Tabelę wypełnia się wykorzystując otrzymaną zależność.

Długość LCS wynosi 4. Wartość tego ciągu można określić poprzez śledzenie ścieżki prowadzącej do ostatniego pola tabeli. Dla danego zestawu danych kilka różnych ciągów może spełniać warunek maksymalnej długości.

Kod demo Python oraz C++

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]]))

#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 każdego elementu wymaga inspekcji nie więcej niż trzech innych elementów tablicy, co daje złożoność obliczeniową O(m\*n). Rekonstrukcja ciągu wymaga nie więcej niż O(m+n) operacji. Całkowita złożoność obliczeniowa wynosi O(m\*n).

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

Wytłumaczenie Video