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
(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