« poprzedni punkt | następny punkt » |
Problem NWP
Dane są dwa ciągi X i Y, X = (x1,...,xm), Y = (y1,..., yn). Znaleźć ciąg znaków Z = (z1,...,zk) 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):
(1) istnieją i1,..., ik takie, że z1= xi1, ..., zk= xik, oraz 1 £ i1£ ... £ ik£ m,
(2) istnieją j1,..., jk takie, że z1= yj1, ...,zk= yjk oraz 1 £ j1£ ... £ jk £ n.
Najdłuższy wspólny podciąg ciągów X i Y oznaczamy przez nwp(X,Y).
Przykład 3.1
Jeżeli X = bracbdeweczsagdjłaaopt i Y = dgadbreschrtadkłewo, to nwp(X,Y) = abecadło. J
Rozwiązanie tego problemu mogłoby wyglądać następująco:
- 1. Wygenerować wszystkie możliwe podciągi ciągu X.
- 2. Dla każdego z nich sprawdzić, czy jest podciągiem ciągu Y.
- 3. Zapamiętać najdłuższy z takich ciągów.
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(2m) elementów. Nawet dla małych m byłby to zbyt kosztowny algorytm.
Przyjmijmy następujące oznaczenie dla ciągu X = ( x1,...,xm), Xi niech oznacza i pierwszych znaków ciągu X tzn. i-ty prefiks X. Dla i=0, X0 jest ciągiem pustym dla i=m, Xm jest po prostu ciągiem X.
Lemat 3.1 Niech Z= (z1,...,zk) będzie najdłuższym wspólnym podciągiem ciągu X = (x1,...,xm), Y = (y1,..., yn).
(1) Jeżeli xm = yn, to zk = xm = yn oraz Zk-1 = nwp(X m-1, Yn-1).
(2) Jeżeli xm ¹ yn, to
Z = nwp(Xm-1, Y), gdy zk ¹ xm oraz
Z = nwp(X, Yn-1), gdy zk ¹ yn.
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 Xm i Yn nie są jednakowe, to albo ostatni element ciągu Xm nie występuje w najdłuższym wspólnym podciągu, albo ostatni element ciągu Yn 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 Xm-1, Yn i najdłuższego wspólnego ciągu Xm, Yn-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
"najdłuższy_wspólny_podciąg" i "programowanie_dynamiczne"
Algorytm rekurencyjny
nwp(X,Y){ | |
if (xm = yn) then | |
Z := nwp(Xm-1, Yn-1) o xm; | |
else | |
Z1 := nwp(Xm-1,Y) ; | |
Z2 := nwp( X, Yn-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
T(1) = 0, T(2) = 1, T (k) = 2 *T(k-1).
Rozwiązaniem tego prostego równania rekurencyjnego jest funkcja T(n) = 2n-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(Xm-1, Yn-1), albo jako lepsze z optymalnych rozwiązań podproblemów nwp(Xm-1,Y), nwp( X, Yn-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
dl(X,Y) = dl(Xm-1, Yn-1) +1, gdy xm = yn,
dl(X,Y) = max (dl(Xm-1,Y),( X, Yn-1)), xm ¹ yn.
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 X5
i Y6 wymaga albo wyliczenia dl(X4,Y5),
albo dl(X4,Y6)
i dl(X5,Y5).
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(Xi, Yj). 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.
Przykład 3.2
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:
b(i,j) = "|" oznacza, że podproblem, który posłużył nam do znalezienia optymalnej długości najdłuższego wspólnego ciągu odpowiada pozycji "w górę", tzn. (i-1,j),
b(i,j) = "\" oznacza, że podproblem, który posłużył do znalezienia optymalnej długości najdłuższego wspólnego ciągu odpowiada pozycji "po przekątnej", tzn. (i-1,j-1),
b(i,j) = "¬" oznacza, że podproblem, który posłużył do znalezienia optymalnej długości najdłuższego wspólnego ciągu odpowiada pozycji "w lewo", tzn. (i,j-1).
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?
« poprzedni punkt | następny punkt » |