Programowanie dynamiczne

(optymalizacja dynamiczna)

A

lg

o

ry

tm

y

i

s

tr

u

k

tu

ry

d

a

n

y

c

h

Programowanie Dynamiczne

Programowanie Dynamiczne

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.

Programowanie Dynamiczne

Programowanie Dynamiczne



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

Zasada Programowania Dynamicznego

Etapy programowania dynamicznego

*



Scharakteryzowanie struktury optymalnego

rozwiązania



Rekurencyjne zdefiniowanie kosztu

optymalnego rozwiązania.



Obliczenie optymalnego kosztu metodą

wstępującą.



Konstruowanie optymalnego rozwiązania na

podstawie wcześniejszych
obliczeń.

Przykład Programowania
Dynamicznego

a

Przykład:

Problem znużonego wędrowca
(problem znajdowania najkrótszej ścieżki)

A

C

F

E

D

B

G

3

2

5

3

1 1

7

7

5

1 4

6

7

6



Niech będzie dany następujący skierowany

graf acykliczny (spójny):

Przykład Programowania
Dynamicznego

Przykład Programowania
Dynamicznego



Znużony wędrowiec ma dotrzeć z miasta A do miasta B.



Zachłanne podejście do tego zadania dałoby w wyniku
następująca ścieżkę:



Jej całkowity koszt wynosi 15.

A

C

F

E

D

B

G

3

6

6

A

C

F

E

D

B

G

5

3

5



Najkrótsza droga pomiędzy A i B wynosi 13 i

ma postać:

Zachłanność w tym przypadku nie popłaca.



Wyznaczenie optymalnego rozwiązania było
możliwe dzięki zastosowaniu programowania
dynamicznego.

Iteracja – przykłady

Iteracja – przykłady

START

s:=0

i:=1

s:=s+a

i:=i+1

s

STOP

N

T

a

a>

5

i>6

T

N

Po zmianie kolejności bloczków
warunkowych otrzymujemy poprawny
algorytm

i

a

s

0

1

2

2

6

6

3

8

14

4

3

5

4

6

7

21

7

[2, 6 , 8 , 3, 4, 7]

Obszar zaznaczony na

żółto jest

charakterystyczny dla

wszystkich algorytmów

operujących na wektorach

(ciągach)

Iteracja – przykłady

Iteracja – przykłady

Schemat blokowy algorytmu wczytującego wyrazy n-elementowego wektora

a=[a

1

, a

2

, ... a

n

]

START

„błędny

rozmiar

wektora

”

STOP

N

T

n

n>

0

i=>

n

N

T

i:=1

a

i

i:=i+1

Jeżeli w algorytmie, na wektorze

są wykonywane jakieś operacje

to winny one być umieszczone

po bloczku wczytującym

element wektora (czytaj a

i

)

START

„błędny

rozmiar

wektora

”

STOP

N

T

n

n>

0

i>n

N

T

i:=1

a

i

i:=i+1

Iteracja – przykłady

Iteracja – przykłady

Schemat blokowy algorytmu

wczytującego wyrazy tablicy o
rozmiarze m

x

n



































mn

2

m

1

m

n

2

22

21

n

1

12

11

a

a

a

a

a

a

a

a

a

a













STOP

START

„błędne

rozmiar

y

tablicy”

N

T

n,m

j>n

N

T

i:=1

a

ij

j:=j+1

j:=1

N

T

i>

m

i:=i+1

n>0 ^ m >0

Iteracja – przykłady

Iteracja – przykłady

Schemat blokowy algorytmu obliczającego wartość wyrażenia









1

i

2

i

a

s















..

3

,

2

,

1

i

dla

i

2

1

0

i

dla

1

a

i

001

.

0

a

a

1

i

i







gdzie

i := 1

pop := 1

s := 0

akt := 1 /

(2*i)

s := s +

akt*akt

(pop-akt) < 0.001

N

T

START

i := i + 1

pop := akt

s

STOP

Ciąg a

i

jest

ciągiem

malejącym,

zbieżnym do

wartości 0, co

powoduje, że

suma s jest

ograniczona.

Niech a

i-1

=pop oraz

a

i

=akt

Iteracja – przykłady

Iteracja – przykłady

STAR

T

p

N

T

a,

eps

a>=0 ^ eps

> 0

T

N

p:=1

p

2

<

a

p:=p+1

p

2

=

a

p:=p-1

x:=(p+a/p)

/2

|p-x|

>=eps

x

STOP

N

T

p:=x

T

N

Algorytm Newtona-

Raphsona obliczania

pierwiastka kwadratowego

z liczby a z dokładnością

eps

9

4

1

q

5

a

0.001

eps

2,23611

2,25

2

3

2

1

p

2,23606

2,23611

2,25

x