Ćwiczenie numer: 6 Data oddania ćwiczenia: Temat: Programowanie dynamiczne

1. Treść zadania.

Znajomość metod programowania dynamicznego oraz zakresu jej stosowania. Znajomość problemu znajdowania najdłuższego wspólnego podciągu.

Przebieg ćwiczenia.

a) Dla obranych z ciągu symboli zbioru liter alfabetu łacińskiego, wyznaczyć najdłuższy wspólny podciąg LWP. Podciągiem nazywamy ciąg, który otrzymuje się z ciągu oryginalnego prze usunięcie z niego niektórych lub żadnego elementu. Wspólnym podciągiem nazywamy podciąg występujący w obu ciągach wejściowych.

Rozwiązać dwoma metodami:

- algorytmem przeszukiwania wyczerpującego przestrzeni rozwiązań (generacja wszystkich podciągów X i sprawdzanie, czy jest ono również podciągiem Y i zapamiętywanie najdłuższego znalezionego podciągu).

- metody programowania dynamicznego.

b) Opisz ogólnie działanie algorytmu na idei programowania dynamicznego ilustrując go przykładem znajdowania NWP(X,Y)

c) Zbadaj zależność czasu obliczeń metod od długości ciągów wejściowych. Można założyć równą długość obu ciągów. T=f(n) przedstawić ma odrębnych wykresach dla poszczególnych algorytmów i na wykresie wspólnym

d) Sformować wnioski z przeprowadzonych badań :

do jakiej klasy problemów należą zagadnienia znajdowania najdłuższego wspólnego podciągu. Jaka jest zależność obliczeń obu metod i jakie ma konsekwencje dla efektywności ich działań. Do jakiego typu problemu możliwe jest zastosowanie programowania dynamicznego.

2. Znajdowanie najdłuższego wspólnego podciągu metodą wyczerpującą.

Algorytm wyszukiwania najdłuższego wspólnego podciągu polega na generacji wszystkich możliwych podciągów ciągu X i sprawdzaniu dla każdego z nich, czy jest też podciągiem ciągu Y, zapamiętując najdłuższy wspólny podciąg dotychczas znaleziony. Każdy podciąg ciągu X odpowiada jednoznacznie podzbiorowi (1,2,..,n) indeksów ciągu X. Istnieje zatem 2ⁿ podciągów X, co przy dużej ilości elementów w ciągu powoduje, że algorytm ten staje się bezużyteczny. Złożoność tego algorytmu jest wykładnicza O(2ⁿ).

Przykład:

X=<A,B,C>

Y=<W,A,C>

Wszystkie możliwe kombinacje wyglądają następująco:

Zbiór pusty; C; B; CB; A; AC; AB; ABC

Jak można zauważyć pasuje kilka kombinacji w ciągu Y, które spełniają warunek podciągu ciągu X jednak tą najdłuższą jest ciąg AC, który metoda wybierze i przedstawi jako wynik.

3. Znajdowanie najdłuższego wspólnego podciągu metodą programowania dynamicznego.

Wstęp teoretyczny.

Metoda programowania dynamicznego opiera się na tzw. "Zasadzie tymalnści" . Optymalny ciąg decyzji ma taką własność, że niezależnie od stanu początkowego i początkowych decyzji, następne decyzje muszą tworzyć optymalny ciąg decyzji względem stanu zastanego.

Opis działania algorytmu.

Procedura ciag_dynamicznie dla danych ciągów X=<x1,x2,..xm> i Y=<y1,y2,..yn> oblicza wartości c[i,j] i zapamiętuje je w tablicy c[0..m,0..n]. Obliczenia te są wykonywane wzdłuż wierszy, a w każdym wierszu od strony lewej do prawej. Tworzona jest także tablica b[1..m,1,..n], która ułatwia później konstrukcję optymalnego rozwiązania. Intuicyjnie, wartość b[i,j] wskazuje na pole w tablicy c, odpowiadające wybranemu podczas obliczania c[i,j] optymalnemu rozwiązaniu podproblemu. Procedura ciąg_dynamicznie oblicza tablice b i c; pole c[m,n] zawiera długość NWP ciągów X i Y. Czas działania tej procedury wynosi O(nm), ponieważ obliczone wartości każdego z pól tablicy c i b zajmuje O(1) jednostek czasu.

procedure ciag_dynamicznie;

var

m,n,i,j:integer;

begin

m:=nx;

n:=ny;

for i:=1 to m do

c[i,0]:=0;

for j:=0 to n do

c[0,j]:=0;

for i:=1 to m do

for j:=1 to n do

if x[i]=y[j] then

begin

c[i,j]:=c[i-1,j-1]+1;

b[i,j]:=skos;

end

else

begin

if c[i-1,j]>=c[i,j-1] then

begin

c[i,j]:=c[i-1,j];

b[i,j]:=gora;

end

else

begin

c[i,j]:=c[i,j-1];

b[i,j]:=lewo;

end;

end;

end;

Przykład

X=<A,B,C,D,E>

Y=<B,A,D,C,E>

Strzałki w tej tablicy oznaczają zawartość tablicy b, wartości liczbowe oznaczają wartości zapisane w tabeli c . Prawa dolna komórka w tabeli informuje o długości podciągu a komórki zaznaczone kolorem oznaczają drogę wskazywaną przez strzałki od tego pola. Strzałki ukośne w polach na tej drodze wskazują elementy składające się na podciąg.

4. Kod programu.

program ciagi;

uses

dos,crt;

const

max_y=5;

max_x=5;

krok=5;

wyswietlanie=true;

type

strzalki=(lewo,gora,skos);

var

c:array[0..max_x,0..max_y] of integer;

b:array[0..max_x,0..max_y]of strzalki;

x:array[1..max_x]of char;

y:array[1..max_y]of char;

xx:array [1..max_x] of byte;

yy:array [1..max_y] of byte;

j,i,nx,ny:integer;

stan:strzalki;

czas_w,czas_d,poczatek,koniec:real;

f:text;

Function WlaczTimer :LongInt;

Var Reg :Registers;

Znacznik :Byte;

Begin

Znacznik:=0;

Reg.AH:=$83;

Reg.AL:=0;

Reg.CX:=$7FFF;

Reg.DX:=$FFFF;

Reg.BX:=Ofs(Znacznik);

Reg.ES:=Seg(Znacznik);

Intr($15,Reg);

WlaczTimer:=$7FFFFFFF;

End;

Function WylaczTimer :LongInt;

Var Reg :Registers;

Begin

WylaczTimer:=MemL[$0040:$009C];

Reg.AH:=$83;

Reg.AL:=1;

Intr($15,Reg);

End;

Function CzasWykonania :Real;

Var Czas :Real;

Begin

Czas:=(Poczatek-koniec);

CzasWykonania:=Czas;

End;

procedure losuj_ciagi;

var

i:integer;

begin

for i:=1 to max_x do

x[i]:=chr(random(25)+65);

for i:=1 to max_y do

y[i]:=chr(random(25)+65);

end;

procedure przelicz_x(liczba:integer);

var

i,j:integer;

begin

for i:=1 to nx do

begin

if (liczba mod 2)=0 then xx[i]:=0

else xx[i]:=1;

liczba:=liczba div 2;

end;

end;

procedure wyczerpujaco;

var

p:char;

i,j,k,max,licznik:integer;

m,maska,max_maska:longint;

label 1,2;

begin

max:=0;

maska:=1;

for i:=1 to nx do maska:=maska*2;

while maska>1 do

begin

maska:=maska-1;

m:=maska;

k:=1;

licznik:=0;

for j:=1 to nx do

begin

if m mod 2=1 then

begin

while k<=ny do

begin

if(y[k]=x[j]) then

begin

k:=k+1;

licznik:=licznik+1;

goto 1; {znaleziony pasujacy znak}

end;

k:=k+1;

end;

goto 2; {nia ma tego znaku w tablicy Y}

end; {ta maska jest zla}

1:

m:=m div 2;

end;

{ok. ten wzorzec pasuje}

if max<licznik then

begin

max:=licznik;

max_maska:=maska;

end;

2:

end;

if wyswietlanie then

begin

write('wyczerpujace: ');

if max>0 then

begin

przelicz_x(max_maska);

for j:=1 to nx do

begin

if xx[j]=1 then write(x[j],' ');

m:=m div 2;

end;

if wyswietlanie then writeln;

end

end;

end;

procedure pokaz;

var

i:integer;

begin

writeln('ciag x');

for i:=1 to nx do write(' ',x[i]);

writeln;

writeln('ciag y');

for i:=1 to ny do write(' ',y[i]);

end;

procedure ciag_dynamicznie;

var

m,n,i,j:integer;

begin

m:=nx;

n:=ny;

for i:=1 to m do

c[i,0]:=0;

for j:=0 to n do

c[0,j]:=0;

for i:=1 to m do

for j:=1 to n do

if x[i]=y[j] then

begin

c[i,j]:=c[i-1,j-1]+1;

b[i,j]:=skos;

end

else

begin

if c[i-1,j]>=c[i,j-1] then

begin

c[i,j]:=c[i-1,j];

b[i,j]:=gora;

end

else

begin

c[i,j]:=c[i,j-1];

b[i,j]:=lewo;

end;

end;

end;

procedure pisz_ciag(i,j:integer);

begin

if (i=0) or (j=0) then exit;

if b[i,j]=skos then

begin

pisz_ciag(i-1,j-1);

write(X[i]);

end

else

if b[i,j]=gora then

pisz_ciag(i-1,j)

else

pisz_ciag(i,j-1)

end;

procedure test;

begin

x[1]:='A';x[2]:='B';x[3]:='C';x[4]:='D';x[5]:='E';

y[1]:='B';y[2]:='A';Y[3]:='D';Y[4]:='C';Y[5]:='E';

end;

begin

clrscr;

randomize;

ny:=0;

nx:=0;

poczatek:= WlaczTimer;

koniec:=wylaczTimer;

Assign(f,'ciagi.txt');

rewrite(f);

writeln('ile znakow | wyczerpujaco | dynamicznie');

writeln(f,'ile znakow | wyczerpujaco | dynamicznie');

repeat

czas_w:=0;

czas_d:=0;

nx:=nx+krok;

ny:=nx;

for j:=1 to 10 do

begin

losuj_ciagi;

{ TEST;}

poczatek:= WlaczTimer;

ciag_dynamicznie;

koniec:=wylaczTimer;

czas_d:=czas_d+czaswykonania;

if wyswietlanie then

begin

pokaz;

writeln;

writeln('dynamicznie') ;

pisz_ciag(nx,ny);

writeln;

writeln('metoda wyczerpujaca');

end;

poczatek:= WlaczTimer;

wyczerpujaco;

koniec:=wylaczTimer;

czas_w:=czas_w+czaswykonania;

end;

writeln(nx:8,czas_w:15:0,czas_d:15:0);

writeln(f,nx:8,czas_w:15:0,czas_d:15:0);

until max_x<nx+krok;

close(f);

writeln(' ********KONIEC********');

writeln;

sound(1000);

delay(100);

nosound;

readln;

end.

5. Tabela pomiarów.

Czas = sumie 10 pomiarów

ile znakow	wyczerpujaco	dynamicznie
[-]	[s]	[s]
1	0.000976	0.000976
2	0.000976	0.000976
3	0.000976	0.000976
4	0.000976	0.000976
5	0.001952	0.000976
6	0.001952	0.001952
7	0.003904	0.000976
8	0.004880	0.002928
9	0.014640	0.001952
10	0.031232	0.001952
11	0.064416	0.003904
12	0.137616	0.003904
13	0.313296	0.002928
14	0.573888	0.000976
15	1.117520	0.001952
16	2.283840	0.002928
17	5.468528	0.001952
18	10.674512	0.002928
19	22.449952	0.003904
20	41.101312	0.003904
21	107.866544	0.002928

6. Wykresy.

7. Wnioski.

Ze względu na niedokładność funkcji obliczających czas wykonywania się algorytmów zastosowałem w swoich pomiarach sumaryczny czas 10 kolejnych wywołań algorytmu dla tej samej ilości znaków.

Zacznę od omówienia metody wyczerpującej. Jest to metoda bardzo nieefektywna, gdyż czas wykonywania się algorytmu bardzo mocno wzrasta wraz z ilością znaków w ciągu. I tak np. dla 10 znaków algorytm wykonuje się 0,3 ms a dla 20 znaków aż 10 s. Dzieje się to dlatego, że algorytm ten sprawdza wszystkie możliwe kombinacje, których jest 2ⁿ (n - liczba znaków). Przykładowo dla 4 znaków jest 16 kombinacji, które można zapisać jako liczba binarna od 1111 do 0000 za każdym zmniejszając jej wartość o 1 czyli w każdej kolejnej iteracji pętli głównej algorytmu odejmujemy 1 od maski np. 1111 > 1110 > 1101 itd. . Łatwo zauważyć, że złożoność obliczeniowa tego algorytmu jest wykładnicza i wynosi O(2ⁿ) co w praktyce dyskwalifikuje ten algorytm do jakichkolwiek zastosowań praktycznych oprócz demonstracji poprzez porównanie z tą metoda innych metod np. metody programowania dynamicznego.

Przeciwieństwem metody wyczerpującej jest metoda dynamiczna, która jest bardzo szybka i efektywna. Jej złożoność obliczeniowa jest wykładnicza i wynosi O(m*n) a przy dwóch jednakowej długości ciągach O(n²) . Jej wykładniczy charakter w tym przypadku nie jest wadą ponieważ w porównaniu z bardzo stromą charakterystyką przy metodzie wyczerpującej wypada ona fenomenalnie. Porównajmy dwa przypadki czas wykonania algorytmu NWP dla metody wyczerpującej przy długości ciągu równej 20 wynosi 2²⁰ jednostek czasu czyli 1048576 jednostek. Dla porównania metodą programowania dynamicznego przy równych co do długości ciągach X i Y czas wykonania jest równy 20² jednostek czasu czyli 400 . Wniosek dla tego przypadku programowanie dynamiczne jest 2600 razy szybsze i wraz ze wzrostem długości ciągu będzie ta dysproporcja rosnąć. Na wykresach to można bardzo dobrze zaobserwować, jednak ze względu na duże różnice na wspólnym wykresie zastosowałem skalę logarytmiczną.

Zastosowanie programowania dynamicznego.

W algorytmie opartym na programowaniu dynamicznym rozwiązuje się każdy problem tylko raz, w każdym kroku wybierając najbardziej optymalne rozwiązanie. Następnie zapamiętuje się wynik w odpowiedniej tabeli , unikając w ten sposób wielokrotnych obliczeń dla tego samego podproblemu.

Programowanie to ma zastosowanie wszędzie tam, gdzie mamy do czynienia z problemami optymalizacyjnymi. W tego typu zagadnieniach możliwych jest wiele rozwiązań. Za każdym razem rozwiązanie jest pewną liczbą. Rozwiązanie optymalne to takie, które za każdym razem ma optymalny (min. max.) koszt.

1

5

---