Dane są dwa ciągi X i Y, X = (x₁,...,x_m), Y = (y₁,..., y_n). Znaleźć ciąg znaków Z = (z₁,...,z_k) taki, że Z jest najdłuższym podciągiem zarówno ciągu X jak i ciągu Y, tzn. Z jest najdłuższym ciągiem spełniającym warunki (1), (2):

Jeżeli X = bracbdeweczsagdjłaaopt i Y = dgadbreschrtadkłewo, to nwp(X,Y) = abecadło. J

Taki algorytm rzeczywiście rozwiązuje problem, ale niestety nie może zostać zastosowany w praktyce. Jego złożoność jest wykładnicza. Jeśli X ma m elementów, to zbiór wszystkich jego pociągów ma O(2^m) elementów. Nawet dla małych m byłby to zbyt kosztowny algorytm.

Przyjmijmy następujące oznaczenie dla ciągu X = ( x₁,...,x_m), X_i niech oznacza i pierwszych znaków ciągu X tzn. i-ty prefiks X. Dla i=0, X₀ jest ciągiem pustym dla i=m, X_m jest po prostu ciągiem X.

Lemat 3.1 Niech Z= (z₁,...,z_k) będzie najdłuższym wspólnym podciągiem ciągu X = (x₁,...,x_m), Y = (y₁,..., y_n).

(1) Jeżeli x_m = y_n, to z_k = x_m = y_n oraz Z_k-1 = nwp(X _m-1, Y_n-1).

(2) Jeżeli x_m ¹ y_n, to

Z = nwp(X_m-1, Y), gdy z_k ¹ x_m oraz

Z = nwp(X, Y_n-1), gdy z_k ¹ y_n.

Wydaje się, że przedstawiony tu lemat daje przepis na znajdowanie najdłuższego ciągu wspólnego: jeśli ostatnie znaki ciągów są identyczne, to jest to ostatni element najdłuższego wspólnego ciągu. Jeśli ostatnie znaki w ciągach X_m i Y_n nie są jednakowe, to albo ostatni element ciągu X_m nie występuje w najdłuższym wspólnym podciągu, albo ostatni element ciągu Y_n nie występuje w najdłuższym wspólnym podciągu. Prowadzi to do dwóch mniejszych problemów: znalezienia najdłuższego wspólnego ciągu X_m-1, Y_n i najdłuższego wspólnego ciągu X_m, Y_n-1. Dłuższy z tych ciągów jest najdłuższym wspólnym podciągiem ciągów X i Y.

Pytanie 4: Z ilu znaków składa się najdłuższy wspólny podciąg ciągów

nwp(X,Y){
	if (x_m = y_n) then
	Z := nwp(X_m-1, Y_n-1) o x_m;
	else
	Z1 := nwp(X_m-1,Y) ;
	Z2 := nwp( X, Y_n-1);
	Z := dłuższy z ciągów Z1, Z2 ;
	fi;
}

Niech T(k) oznacza koszt pesymistyczny tego algorytmu, gdzie k jest sumą długości ciągów X i Y. Mamy

Rozwiązaniem tego prostego równania rekurencyjnego jest funkcja T(n) = 2^n-2. Wynika stąd, że należy szukać innego rozwiązania problemu: algorytm rekurencyjny jest zbyt kosztowny.

To była zła nowina. Dobra nowina jest taka, że problem NWP ma własność optymalnej podstruktury: przecież optymalne rozwiązanie znajdziemy, albo jako wynik optymalnego rozwiązania problemu nwp(X_m-1, Y_n-1), albo jako lepsze z optymalnych rozwiązań podproblemów nwp(X_m-1,Y), nwp( X, Y_n-1). To sugeruje, że być może metoda programowania dynamicznego da dobry algorytm. Gdybyśmy jeszcze wiedzieli, który z podproblemów należy rozwiązać, to zadanie stałoby się proste. Oczywiście chcemy rozwiązać ten podproblem, którego rozwiązanie daje dłuższy ciąg.

Wyliczmy najpierw długość najdłuższego wspólnego podciągu postępując tak, jak w algorytmie rekurencyjnym. Oznaczmy przez dl(A,B) długość najdłuższego wspólnego podciągu danych ciągów A i B. Mamy

Pytanie 5: Jaki jest koszt rekurencyjnego algorytmu obliczania długości najdłuższego wspólnego ciągu danych dwóch ciągów?

Na rysunku 14.4 przedstawiono fragment drzewa rekurencyjnych wywołań przy obliczaniu funkcji dl. W węzłach drzewa umieszczone są parametry wywołań. Na przykład, wierzchołek (5,6) odpowiadający za wywołanie funkcji dla ciągów X₅ i Y₆ wymaga albo wyliczenia dl(X₄,Y₅), albo dl(X₄,Y₆) i dl(X₅,Y₅). Zauważmy, że niektóre podproblemy, które musimy rozważać, powtarzają się wielokrotnie. Zatem zapiszmy uzyskane wcześniej wyniki w tablicy i zamiast wywołania rekurencyjnego skorzystajmy z nich.

Niech d będzie tablicą o wymiarach n ´ m, w której zapisywać będziemy wartości funkcji dl, d(i,j)= dl(X_i, Y_j). W jakiej kolejności mamy wyliczać wielkości d(i,j), tak by odpowiednie elementy tablicy miały już policzone wartości w chwili, gdy chcemy z nich skorzystać? Do wyliczenia d(i,j) potrzebne są nam pozycje (i-1,j-1) oraz pozycje w górę i na lewo od (i,j). Wystarczy zatem wypełniać tablicę d wierszami.

Rozważmy ciągi X ="barakuda" i Y="abrakadabra". W tabeli na rysunku 14.5 przedstawiono wartości funkcji dl(X,Y). Symbole ¬, |, \ pokazują jak obliczyliśmy wynik. Na przykład liczba 3 na pozycji (4, 4) oznacza, że najdłuższy wspólny podciąg ciągów BARA i ABRA składa się z 3 liter, natomiast znak \ oznacza, że aby to wyliczyć musieliśmy znać rozwiązanie zadania "po przekątnej", czyli długość najdłuższego wspólnego ciągu "BRA" i "ABR". Liczba 4 na pozycji (5,6) oznacza, że nwp(BARAK, ABRAKA) = 4. Wyliczyliśmy to biorąc maksimum z dwóch rozwiązań nwp(BARAK,ABRAK) oraz nwp(BARA,ABRAKA). Strzałka w lewo na pozycji (5,6) pokazuje, że maksimum znajdowało się na pozycji sąsiedniej w lewo.J

W algorytmie obliczania długości NWP używamy dwóch tablic: tablicy d o wymiarach (|X|+1)´(|Y|+1) i tablicy b o wymiarach (|X|´|Y|). Tablica d służy do zapamiętania długości najdłuższego wspólnego podciągu, a w tablicy b na pozycji (i,j) zapamiętamy zadanie, które trzeba rzeczywiście rozwiązać, aby uzyskać optymalną wartość d(i,j). Wiersz o numerze 0 i kolumna o numerze 0 w tablicy d, mają charakter pomocniczy - pozwalają uprościć algorytm. Tablica b posłuży nam później do odczytania ostatecznego rozwiązania.

dlNWP(X,Y){
	m := \|X\|; n := \|Y\|;
	for i :=1 to m do d(i,0) := 0 od; // inicjalizacja
	for j :=1 to n do d(0,j) := 0 od;
	for i :=1 to m do // wypełniamy obie tablice wierszami
	for j :=1 to n do
	if (X[i] =Y[i]) then
	d(i,j) := d(i-1,j-1) +1; b(i,j):="\";
	else
	if (d(i-1,j) ³ d(i,j-1)) then
	d(i,j) := d(i-1,j); b(i,j) := "\|";
	else
	d(i,j) := d(i,j-1); b(i,j) := "¬";
	if
	if
	od
}

Koszt algorytmu jest oczywiście wielomianowy: wykonujemy rzędu O(n*m) operacji arytmetycznych, gdzie m jest długością ciągu X, a n długością ciągu Y.

Znaki "|", "\" oraz "¬" kodują pozycję podproblemu, który trzeba rozwiązać, aby w danej chwili znaleźć optymalne rozwiązanie:

Korzystając z tablicy b możemy wypisać rozwiązanie, najdłuższy wspólny podciąg danych ciągów. Wystarczy w tym celu rozpocząć przeglądanie tablicy b od pozycji (m,n), gdzie m jest długością ciągu X, a n długością ciągu Y, i poruszać się zgodnie ze znakami |,\, ¬. Wypisujemy wspólny znak tylko wtedy, gdy trafimy na \. Na rysunku 14.5 zaznaczono ścieżkę, którą trzeba przejść aby odczytać rozwiązanie, którym, w tym przypadku, jest słowo " ARAKDA ". Algorytm wypisywania najdłuższego wspólnego podciągu jest przedstawiony w rekurencyjnej procedurze drukuj.

drukuj(i,j){
	if (i=0 lub j =0) then return fi;
	if (b(i,j) = "\") then // po przekątenej
	drukuj(i-1, j-1);
	write (X[i])
	else
	if (b(i,j) ="\|") then // w górę
	drukuj(i-1,j)
	else // w lewo
	drukuj(i,j-1)
	if
	if
}

Koszt związany z wykonaniem procedury drukuj dla parametrów n, m wynosi O(n+m). Rzeczywiście, w każdym rekurencyjnym wywołaniu algorytmu co najmniej jedna z wartości albo i, albo j jest zmniejszana, a po osiągnięciu zera przez dowolną z nich, algorytm kończy obliczenie.

Wniosek Koszt algorytmu znalezienia najdłuższego wspólnego podciągu ciągów X, Y o długości odpowiednio m i n wynosi O(n*m).

Pytanie 6: W jakiej kolejności zostaną wypisane elementy najdłuższego wspólnego ciągu, jeśli korzystamy z procedury drukuj?