AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 1

Techniki budowania algorytmów

Co dziś w ramach wykładu?

1. Rekurencja

2. Dziel i zwyciężaj

3. Programowanie dynamiczne

4. Metoda zachłanna

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 2

Przykład 1 - Ciąg Fibonacci’ego

















1

dla

2)

-

(

1)

-

(

1

lub

0

dla

1

)

(

n

n

Fib

n

Fib

n

n

n

Fib

Definicja rekurencyjna:

sugeruje zastosowanie techniki „dziel i zwyciężaj”:

long Fib(int n)
{

if (n==0 || n==1) return 1;
return Fib(n-1) + Fib(n-2);

}

Wady:
1.Obliczenie Fib(20) wymaga ponad 14 000 operacji dodawania.
2.Te same podproblemy wykonywane są wielokrotnie, np. Fib(10)
wywoływane jest 76 razy.
3.Szybkie zapełnianie stosu.

Odwrócenie kolejności obliczeń, tzn. rozpoczęcie obliczania od małych
podproblemów daje algorytm wymagający n – 1 dodawań (czyli 19 dla
Fib(20))

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 3

long Fib(int n)
{

int a, b = 1, f = 1, i;
for (i = 1; i <= n; i++)

{ a = f + b; b = f; f

= a; }

return f;

}

Ciąg Fibonacci’ego techniką programowania

dynamicznego

long Fib(int n)
{

if (n==0 || n==1) return 1;
else {

long x[]; x[0] = x[1] = 1;

for (int i = 2; i <= n; i++)

x[i] = x[i-1] + x[i-2];

}
return x[n];

}Ponieważ nie trzeba pamiętać wszystkich wyników podproblemów (tylko

dwa ostatnie) – nie trzeba używać tablicy:

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 4

Programowanie dynamiczne

- metoda znajdowania rozwiązań

problemów optymalizacyjnych podobna do metody „dziel i zwyciężaj” - w
metodzie tej zadany problem dzielimy na podproblemy, rozwiązujemy je, a
następnie łączymy rozwiązania podproblemów.

• metoda „dziel i zwyciężaj” - wielokrotnie rozwiązuje ten sam

problem, wykonuje więc dużo więcej pracy

• programowanie dynamiczne - algorytm oparty na tej metodzie

rozwiązuje każdy podproblem tylko jeden raz zapamiętując wynik,
unika się w ten sposób wielokrotnych obliczeń dla tego samego
podproblemu

Różnice

Programowanie dynamiczne

Opracowanie algorytmu programowania
dynamicznego

1. Określamy zależność rekurencyjną, która pozwala znaleźć

rozwiązanie problemu

2. Rozwiązujemy problem zgodnie z podejściem wstępującym,

najpierw rozwiązując mniejsze podproblemy

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 5

Przykład 2 - Współczynniki dwumianowe

)!

(

!

!

k

n

k

n

k

n

















50! = 30414093201713378043612608166064768844377641568960512000000000000
40! = 815915283247897734345611269596115894272000000000

Tymczasem

0

1027227817

!

10

!

40

!

50

40

50







































 





































n

k

k

n

k

n

n

k

k

k

n

0

dla

1

1

1

lub

0

dla

1

Zależność rekurencyjna:

Razem wyliczanych jest

składników

1

2















k

n

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 6

Współczynniki dwumianowe c.d.

Programowanie dynamiczne

1.Wykorzystujemy tablicę B, w której B[i][j] będzie zawierać wartość

2.Rozwiązujemy problem w porządku wstępującym, rozpoczynając od
pierwszego wiersza i wyliczając po kolei wartości w wierszach tablicy B.













j

i























n

j

j

i

j

j

i

B

j

i

B

j

i

B

lub

0

1

0

]

][

1

[

]

1

][

1

[

]

][

[

0 1 2 3 4

j



k

0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1

i



n

int Bin2 (int n, int k)
{

int i, j;
int B[0..n][0..k]
for (i = 0; i <= n; i++)

for (j = 0; j <= minimum(i, k); j++)

if (j == 0 || j == i) B[i][j] = 1;
else B[i][j] = B[i-1][j-1] + B[i-1][j];

return B[n][k];

}

Wystarczy wyliczać tylko

k pierwszych kolumn

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 7

Współczynniki dwumianowe c.d.

i

0

1

2

3

…

k

k+1

…

n

Liczba przebiegów

pętli for-j

1

2

3

4

…

k+1 k+1

…

k+1

)

(

2

)

1

)(

2

2

(

)

1

)(

1

(

2

)

1

(

)

1

(

)

1

(

)

1

(

4

3

2

1

nk

k

k

n

k

k

n

k

k

k

k

k

k























































Złożoność czasowa

Dodatkowe możliwości poprawienia algorytmu:

1.Nie trzeba całej tablicy, tylko jeden wiersz (tablicę jednowymiarową

indeksowaną

od 0 do k).

2.Można wykorzystać zależność:





























k

n

n

k

n

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 8

Przykład 3 – Droga przez tablicę

Problem

Dana jest prostokątna tablica T liczb całkowitych o rozmiarach nm.

Zadanie polega na znalezieniu drogi przez tablicę o następujących
własnościach:
a)droga rozpoczyna się w dowolnym polu pierwszej kolumny i kończy w
dowolnym polu ostatniej kolumny tablicy;
b)w jednym kroku posuwamy się zawsze o jedną kolumnę w prawo oraz
c)możemy przejść o jeden wiersz w górę, w dół lub pozostać w tym samym
wierszu;
d)spośród wszystkich dróg o powyższych własnościach interesuje nas droga
optymalna, tzn. taka, dla której suma wartości zawartych w polach, przez
które przechodzi droga, jest największa.

Dróg spełniających warunki a)-c) jest prawie n·3

m-1

(co najmniej n·2

m-1

)

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 9

Droga przez tablicę c.d.

Do pola [i, j] droga może wchodzić z jednego z trzech (czasami dwóch) pól z
poprzedniej kolumny: [i-1, j-1] , [i, j-1] lub [i+1, j-1]. Najlepsza z tych dróg
jest drogą optymalną prowadzącą do [i, j]. Jej koszt jest więc największą z
liczb:

• koszt optymalnej drogi do [i-1, j-1] plus T[i, j]
• koszt optymalnej drogi do [i, j-1] plus T[i, j]
• koszt optymalnej drogi do [i+1, j-1] plus T[i, j]

Algorytm Optymalna droga przez tablicę
{Algorytm polega na wyliczaniu wartości tablicy D[n, m] w ten sposób,
by D[i, j] było kosztem optymalnej drogi rozpoczynającej się w
pierwszej kolumnie, a kończącej w polu [i, j]}

int D[n+2,m];

 wszystkie elementy zerujemy

for (i=1; i<=n; i++) D[i, 1] = T[i, 1];
for (j=1; j<=m; j++)

for (i=1; i<=n; i++)

D[i, j] = T[i,j] + max(D[i-1, j-1] , D[i, j-1] , D[i+1, j-1];

return max (D[1, m] , D[2, m] , … , D[n, m])

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 10

Droga przez tablicę c.d.

Przykład

1

3

2

7

3

1

3

6

2

4

1

1

5

2

7

1

1

3

2

4

0

0

0

0

1

6

8

1

9

3

4

1

2

1

8

2

9

1

0

1

7

5

7

1

6

1

7

1

8

1

0

2

0

0

0

0

0

Tablica T

Tablica D

Złożoność czasowa algorytmu wynosi O(m·n)

Jak zmodyfikować algorytm, by odtwarzał optymalną drogę?

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 11

Problem:

Dla danego ciągu n macierzy <A

1

, A

2

, ..., A

n

>, gdzie

dla i=1, 2, ..., n macierz A

i

ma wymiar p

i-1

x p

i

, wyznaczyć za

pomocą jak najmniejszej liczby obliczeń iloczyn macierzy A

1

· A

2

·...·A

n

.

Przykład 4 – Mnożenie ciągu macierzy

Standardowy algorytm mnożenia dwóch macierzy:

MNOŻENIE_MACIERZY(A,B)
1

if ile_kolumn[A]ile_wierszy[B]

2

then error

3

else for i=1 to ile_wierszy[A] do

4

for j=1 to ile_kolumn[B] do

5

{ C[i,j]:=0

;

6

for k=1 to ile_kolumn[A] do

7

C[i,j]:=C[i,j]+A[i,k]·B[k,j] ;

8

}

9 return C ;

Czas obliczeń jest zdeterminowany przez ilość mnożeń skalarnych w
wierszu 7. Jeśli A i B są macierzami o rozmiarze odpowiednio p x q i q x r,
to ilość mnożeń w wierszu 7 wynosi p·q·r.

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 12

Jeśli

A

1

ma rozmiar 10 x 100

A

2

ma rozmiar 100 x 5

A

3

ma rozmiar 5 x 50

to liczba mnożeń skalarnych:

• ((A

1

A

2

)A

3

)

10 x 100 x 5 + 10 x 5 x 50 = 5000 + 2500

= 7500
• (A

1

(A

2

A

3

) 100 x 5 x 50 + 10 x 100 x 50 = 25000 + 50000 =

75000

Wniosek: Kolejność wykonywania operacji („nawiasowanie”) ma

znaczenie!

Fakt: Ciąg n macierzy można wymnożyć na
sposobów.

Np. dla n = 10 jest to 4862, a dla n =13: 208012

Mnożenie ciągu macierzy c.d.

Uogólnienie: Umieszczenie nawiasów w podciągu A

1

A

2

… A

k

w

optymalnym nawiasowaniu A

1

A

2

....A

n

jest optymalnym

nawiasowaniem A

1

A

2

…A

k.

Podproblemy: wyznaczenie optymalnego nawiasowania
iloczynów A

i

A

i+1

…A

j

gdzie 1  i  j  n

















1

)

1

(

2

1

n

n

n

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 13

Rekurencyjna definicja kosztu
optymalnego.

Oznaczenie: m[i, j] – minimalna liczba mnożeń skalarnych
niezbędnych do obliczenia macierzy A

i..j

0

dla i = j

m[i, j] =

min

ik<j

{m[i, k] + m[k+1, j] + p

i

–1

p

k

p

j

}

dla i < j

Oznaczenie: s[i, j] – wartość k, która realizuje minimalną wartość m[i, j]

Oznaczenie: A

i..j

= A

i

A

i+1

·…·A

j

A

i..k

ma rozmiary p

i –1

p

k

A

k+1..j

ma rozmiary p

k

p

j

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 14

1..
4

1..1

2..4

1..2

3..4

1..3

4..4

2..2 3..4 2..3

4..4

1..1

2..2

3..3

4..4

1..1

2..3

1..2

3..3

3..3 4..4

2..2

3..3

2..2

3..3

1..1

2..2

Drzewo rekursji procedury obliczającej rekurencyjnie koszt mnożenia
macierzy

Na

czerwono

– węzły występujące kolejny raz.

Obliczanie optymalnego kosztu

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 15

Mnożenie ciągu macierzy c.d.

Obliczanie m[1, n] metodą programowania dynamicznego polega na
wyliczaniu odpowiednich wartości m[i, j] w takiej kolejności by:

1. rozpocząć od przypadków trywialnych (i = j);
2. w momencie obliczania m[i, j] mieć już obliczone wszystkie

potrzebne wartości, tzn.:
(m[i, i], m[i+1, j]) , (m[i, i+1], m[i+2, j]) , (m[i, i+2], m[i+3, j]) , … ,
(m[i, j-1], m[j, j])

3. zakończyć obliczanie na m[1, n]

Powyższe warunki będą spełnione, jeżeli będziemy obliczać wartości m[i, j]
w kolejności:

1. m[1, 1] , m[2, 2] , m[3, 3] , … , m[n-1, n-1] , m[n, n] (ciągi długości

1)

2. m[1, 2] , m[2, 3] , m[3, 4] , … , m[n-2, n-1] , m[n-1, n] (ciągi

długości 2)
…

k. m[1, k] , m[2, k+1] , m[3, k+2] , … , m[n-k, n-1] , m[n-k+1, n]

(ciągi długości k)
…

n. m[1, n] (ciąg długości n)

Zastosowanie programowania
dynamicznego

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 16

Pseudokod procedury MACIERZE_KOSZT

Dane wejściowe: ciąg p = <p

0

, p

1

, ...,p

n

> rozmiarów macierzy;

Używamy macierzy m[1..n,1..n] oraz s[1..n,1..n] do zapamiętywania
kosztów oraz indeksów k dających optymalny podział

MACIERZE_KOSZT(p)
1 n:=długość[p]-1
2 for i=1 to n
3 do m[i, i]:=0
4 for l=2 to n
5 do for i=1 to n-l+1
6 do j=i+l-1
7 m[i,j]:=
8

for k=i to j-1

9

do q:=m[i,k]+m[k+1,j]+p

i-1

p

k

p

j

10

if q<m[i,j] then

11

do m[i,j]:=q, s[i,j]:=k

12 return m oraz s

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 17

Macierz
Wymiar

A

1

30x35

A

2

35x15

A

3

15x5

A

4

5x10

A

5

10x20

A

6

20x25

Przykładowe obliczenia

1

s[1,6]=3



(A

1

A

2

A

3

)

(A

4

A

5

A

6

)

2

s[1,3]=1



(A

1

(A

2

A

3

))

(A

4

A

5

A

6

)

3

s[4,6]=5



(A

1

(A

2

A

3

))

((A

4

A

5

)A

6

)

i

m

1

2

3

4

5

6

6 15125 10500 5375 3500 5000

0

5 11875 7125 2500 1000

0

j 4 9375 4375

750

0

3 7875 2625

0

2 15750

0

1

0

n = 6
p = <30, 35, 15, 5, 10, 20, 25>

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 18

Pseudokod procedury MNOŻENIE
_ŁAŃCUCHA_MACIERZY

Procedura rekurencyjna oblicza iloczyn A

i..j

dla danego ciągu macierzy

<A

1

, A

2

, .., A

n

>, tablicy s i indeksów i oraz j.

MNOŻENIE_ŁAŃCUCHA_MACIERZY(A, s, i, j)

1 if j>i then

2 { X:= MNOŻENIE_ŁAŃCUCHA_MACIERZY(A, s, i, s[i, j])

3 Y:= MNOŻENIE_ŁAŃCUCHA_MACIERZY(A, s, s[i, j]
+1, j)

4 return MNOŻENIE_MACIERZY(X, Y)

5 }

6 else return A

i

Konstruowanie optymalnego rozwiązania

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 19

Przykład 5 – Najdłuższy wspólny podciąg

Definicje

Niech X = (x

1

, x

2

, … , x

n

), gdzie x

1

, x

2

, … , x

n

 , będzie ciągiem nad

alfabetem .

1.Prefiksem

X jest każdy podciąg X postaci (x

1

, x

2

, … , x

j

), gdzie j  n (dla

j < n jest to

prefiks właściwy

). Prefiks długości j oznaczamy X

j

.

2.Podciągiem

X jest każdy ciąg postaci: (x

i1

, x

i2

, … , x

im

), gdzie 1  i

1

< i

2

<

… < i

m

 n

3.Z jest

wspólnym podciągiem

X i Y, jeżeli jest podciągiem X i jest

podciągiem Y.
4.Z jest

najdłuższym wspólnym podciągiem

X i Y (piszemy Z = NWP(X, Y),

jeśli jest wspólnym podciągiem X i Y i nie istnieje dłuższy podciąg będący
jednocześnie podciągiem X i Y.

Dla ciągów X = AABAABBABAA i Y = ABBBABAB
•AAAAAAA = AABAABBABAA jest podciągiem X i nie jest podciągiem Y;
•AAB i A są prefiksami X (odpowiednio X

3

i X

1

);

•AAA = AABAABBABAA = ABBBABAB jest wspólnym podciągiem X i Y
•NWP(X, Y) = ABBBABA = AABAABBABAA = ABBBABAB

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 20

Najdłuższy wspólny podciąg – c.d.

Wszystkich podciągów n-elementowego ciągu X jest 2

n

.

Twierdzenie

Niech X = X’x i Y = Y’y będą ciągami, X’ i Y’ ich prefiksami, a x i y ostatnimi
symbolami. Wtedy

x = y  NWP(X, Y) = NWP(X’, Y’)x

x

 y  NWP(X,Y) = NWP(X’,Y) lub NWP(X,Y) = NWP(X,Y’)

Argumenty za programowaniem dynamicznym:

•wszystkie pojawiające się podczas obliczeń podproblemy polegają na
policzeniu NWP pewnego prefiksu X i pewnego prefiksu Y, tzn. NWP(X

i

,

Y

j

)

•wszystkich podproblemów jest n·m – niewiele!!!
•podproblemy należy wyliczać w takiej kolejności, by w momencie
obliczania NWP(X

i

, Y

j

) były znane NWP(X

i-1

, Y

j

) i NWP(X

i

, Y

j-1

) . Dobra jest

więc np. kolejność:

NMP(X

1

, Y

1

) , NWP(X

1

, Y

2

), … , NWP(X

1

, Y

m

)

NMP(X

2

, Y

1

) , NWP(X

2

, Y

2

), … , NWP(X

2

, Y

m

)

…
NMP(X

n

, Y

1

) , NWP(X

n

, Y

2

), … , NWP(X

n

, Y

m

)

•

podproblemy trywialne to przypadki, gdy i = 0 lub j = 0,

wtedy NWP(X

i

, Y

j

) = 

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 21

Najdłuższy wspólny podciąg – c.d.

Złożoność czasowa powyższego algorytmu wynosi O(n·m)

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 22

Przykład

Niech X = ABBBABAB i Y = AABAABBABAA

NWP(X

8

, Y

11

) = NWP(X

8

, Y

10

) = NWP(X

7

, Y

10

) = NWP(X

6

, Y

9

)A = NWP(X

5

, Y

8

)BA =

= NWP(X

4

, Y

7

)ABA = NWP(X

3

, Y

6

)BABA = NWP(X

2

, Y

5

)BBABA= NWP(X

2

, Y

4

)BBABA =

= NWP(X

2

, Y

3

)BBABA = NWP(X

1

, Y

2

)BBBABA = NWP(, Y

1

)ABBBABA = ABBBABA

Najdłuższy wspólny podciąg – c.d.

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 23

1. Problem wykazuje optymalną podstrukturę, jeśli jego

optymalne rozwiązanie jest funkcją optymalnych rozwiązań
podproblemów; metoda dowodzenia jest następująca:
zakładamy, że jest lepsze rozwiązanie podproblemu, po czym
pokazujemy, iż to założenie zaprzecza optymalności rozwiązania
całego problemu

2. Mówimy, że problem ma własność wspólnych

podproblemów, jeśli algorytm rekurencyjny wielokrotnie
oblicza rozwiązanie tego samego podproblemu; algorytmy
oparte na programowaniu dynamicznym rozwiązują dany
podproblem tylko jeden raz i zapamiętują gotowe rozwiązania,
które potem wystarczy odczytać w stałym czasie.

Jeśli problem wykazuje te dwie własności warto spróbować, czy daje się
stosować metoda programowania dynamicznego.

Ponadto:

3.„Rozsądnie mała” przestrzeń istotnie różnych podproblemów

Kiedy można stosować metodę programowania

dynamicznego

AiSD - Wykład 5 – Programowanie dynamiczne

Slajd 24

Inne zastosowania techniki programowania

dynamicznego

1. Algorytm Floyda określania najkrótszej drogi w grafie (zostanie

omówiony w temacie „Grafy”)

2. Optymalne drzewa wyszukiwania binarnego (będzie przy okazji drzew

binarnych)

3. Problem komiwojażera
4. Dyskretny problem plecakowy (będzie przy okazji metod zachłannych)
5. Optymalna triangulacja wielokąta (Cormen, Leiserson, Rivest, rozdz.

16.4.)

6. Wyprowadzanie słowa w gramatyce (Aho, Hopcroft, Ullman)

i wiele, wiele innych

