Nadaje się do rozwiązywania problemów, które można podzielić na podproblemy, ale różne podproblemy mogą wymagać rozwiązania tych samych podpodproblemów.
(Metoda dziel i zwyciężaj rozwiązuje wtedy te same podpodproblemy wielokrotnie.)
Projektowanie algorytmu dynamicznego:
1. Scharakteryzowanie struktury optymalnego rozwiązania 2. Rekurencyjne zdefiniowanie kosztu optymalnego rozwiązania
3. Obliczenie rozwiązania metodą wstępującą ( bottom-up) 4. Konstruowanie optymalnego rozwiązania na podstawie wyników wcześniejszych obliczeń
M.Kik “AiSD 5” – p. 1
Dane: ciąg n macierzy A1,. . . An różnych rozmiarów (takich, że można wykonać mnożenie A1 · A2. . . ·An, t.j. macierz Ai ma wymiatry pi−1 × pi)
Wynik: nawiasowanie minimalizujące łączny koszt mnoże ń Matrix-Multiply(A,B)
1 if columns[A] 6= rows[B] then 2
error “niezgodne rozmiary”
3 else
3
for i ← 1 to rows[A] do
4
for j ← 1 to columns[B] do
5
C[i, j] ← 0
6
for k ← 1 to columns[A] do
7
C[i, j] ← C[i, j] + A[i, k] · B[k, j]
8
returnc C
Czas: Θ(p · q · r), gdzie p × q, q × r – wymiary macierzy M.Kik “AiSD 5” – p. 2
( 1
dla n = 1
P (n) =
Pn−1
k
P (k)P (n − k) dla n ≥ 2
=1
P (n) = C(n − 1), gdzie C(i) – i-ta liczba Catalana.
1 µ2n¶
C(n) =
= Ω(4n/n3/2)
n + 1
n
Rośnie wykładniczo ze względu na n.
M.Kik “AiSD 5” – p. 3
Struktura optymalnego nawiasowania
A1. . . An jest dzielony na (A1. . . Ak) oraz (Ak . . .
+1
An),
dla pewnego k, 1 ≤ k < n.
Umieszczenie nawiasów w A1. . . Ak (odp. Ak . . .
+1
An)
jest optymalnym nawiasowaniem dla A1. . . Ak (odp.
Ak . . .
+1
An)
Rozwiązanie rekurencyjne:
m[i, j] – optymalny koszt mnożenia podciągu Ai. . . Aj.
( 0
dla i = j
m[i, j] =
mini≤k<j{m[i, k] + m[k + 1, j] + pi−1pkpj} dla i < j UWAGA: liczba możliwych podproblemów wynosi:
¡n¢ + n = Θ(n2) (dokładnie jeden podproblem dla każdej 2
pary i,j, 1 ≤ i ≤ j ≤ n).
M.Kik “AiSD 5” – p. 4
Matrix-Chain-Order(p)
. p = hp0, ..., pni - wymiary
1 n ← length[p] − 1
2 for i ← 1 to n do
3
m[i, i] ← 0
4 for l ← 2 to n do . l - dł.
podciągu
5
for i ← 1 to n − l + 1 do
6
j ← i + l − 1
7
m[i, j] ← ∞
8
for k ← i to j − 1 do
9
q ← m[i, k] + m[k + 1, j] + pi−1pkpj
10
if q < m[i, j] then
11
m[i, j] ← q
12
s[i, j] ← k . podział Ai . . . Aj
13 return m i s
. czas Θ(n3), pam.
Θ(n2)
M.Kik “AiSD 5” – p. 5
Wykonanie optymalnego mnożenia s – tablica wyznaczona przez Matrix-Chain-Order.
Mnożenie podciągu Ai. . . Aj.
Matrix-Chain-Multiply(A,s,i,j)
1 if j > i then
2
X ←Matrix-Chain-Multiply(A,s,i,s[i, j])
3
Y ←Matrix-Chain-Multiply(A,s,s[i, j] + 1,j)
4
return Matrix-Multipy(X,Y )
5 else return Ai
Wywołanie: Matrix-Chain-Multiply(A,s,1,n)
M.Kik “AiSD 5” – p. 6
Recursive-Matrix-Chain(p,i,j)
1 if i = j
2
then return 0
3 m[i, j] ← ∞
4 for k ← i to j − 1 do
5
q ← Recursive-Matrix-Chain(p,i,k)
+Recursive-Matrix-Chain(p,k + 1,j)+pi−1pkpj
6
if q < m[i, j]
7
then m[i, j] ← q
8 return m[i, j]
Czas: T (n)
T (1) ≥ 1
T (n) ≥ 1 + Pn−1
k
(T (k) + T (n − k) + 1) dla n > 1
=1
(koszt wierszy 1-2 i 6-1 ≥ 1 jednostka czasu) M.Kik “AiSD 5” – p. 7
T (n) ≥ 1 + Pn−1
k
(T (k) + T (n − k) + 1)
=1
T (n) ≥ 2 Pn−1
i
T (i) + n
=1
Inducja: Podstawa: T (1) ≥ 20 = 1. Zał. ind.: dla i < n, T (i) ≥ 2i−1.
T (n) ≥ 2 Pn−1
i
2i−1 + n
=1
= 2 Pn−2
i
2i + n
=0
= 2(2n−1 − 1) + n
= (2n − 2) + n
≥ 2n−1
T (n) = Ω(2n) – czas wykładniczy (wielokrotnie rozwiązywany każdy z O(n2) podproblemów).
M.Kik “AiSD 5” – p. 8
Dla każdego podproblemu zapamiętujemy rozwiązanie i zaznaczamy, że jest już rozwiązany. Przy następnym napotkaniu tego samego podproblemu wykorzystujemy wcześniej wyznaczone rozwiązanie. (Wtedy niektóre z podproblemów rozwiązywanych w programowaniu metodą wstępującą mogą zostać pominięte.)
Przykład dla ciągu macierzy:
Memoized-Matrix-Chain(p)
1 n ← length[p] − 1
2 for i ← 1 to n do
3
for j ← i to n do
4
m[i, j] ← ∞
5 return Lookup-Chain(p,1,n)
M.Kik “AiSD 5” – p. 9
Lookup-Chain(p,i,j)
1 if m[i, j] < ∞
2
then return m[i, j]
3 if i = j then
4
m[i, j] ← 0
5 else
5
for k ← i to j − 1 do
6
q ←Lookup-Chain(p,i,k)
+Lookup-Chain(p,k + 1,j)+pi−1pkpj
7
if q < m[i, j]
8
then m[i, j] ← q
9 return m[i, j]
Czas: O(n3) – każde z Θ(n2) pól m[i, j] jest ≤ 1 raz wyznaczone w wierszach 4–8, co zajmuje O(n) (nie licząc czasu na wyznaczenie innych pól).
M.Kik “AiSD 5” – p. 10
Tw. (O optymalnej podstrukturze NWP) Niech X = hx1 . . . xmi i Y = hy1 . . . yni. Niech Z = hz1 . . . zki – NWP X i Y .
1. Jeśli xm = yn, to zk = xm = yn i Zk jest NWP
−1
Xm−1 i
Yn−1
2. Jeśli xm 6= yn i zk 6= xm, to Z jest NWP Xm−1 i Y .
3. Jeśli xm 6= yn i zk 6= yn, to Z jest NWP X i Yn−1.
Najdłuższy Wspólny Podciąg
Z = hz1 . . . zki jest podciągiem ciągu X = hx1 . . . , xmi, jeśli istnieje rosnący ciąg indeksów hi1, . . . , iki, taki że dla każdego j = 1 . . . k zachodzi xi = z
j
j .
Z jest wspólnym podci ˛
agiem X i Y jeśli jest podciągiem X oraz jest podciągiem Y .
NWP – najdłuższy wspólny podciąg.
Prefix Xi = hx1 . . . xii.
M.Kik “AiSD 5” – p. 11
Z = hz1 . . . zki jest podciągiem ciągu X = hx1 . . . , xmi, jeśli istnieje rosnący ciąg indeksów hi1, . . . , iki, taki że dla każdego j = 1 . . . k zachodzi xi = z
j
j .
Z jest wspólnym podci ˛
agiem X i Y jeśli jest podciągiem X oraz jest podciągiem Y .
NWP – najdłuższy wspólny podciąg.
Prefix Xi = hx1 . . . xii.
Tw. (O optymalnej podstrukturze NWP) Niech X = hx1 . . . xmi i Y = hy1 . . . yni. Niech Z = hz1 . . . zki – NWP X i Y .
1. Jeśli xm = yn, to zk = xm = yn i Zk jest NWP
−1
Xm−1 i
Yn−1
2. Jeśli xm 6= yn i zk 6= xm, to Z jest NWP Xm−1 i Y .
3. Jeśli xm 6= yn i zk 6= yn, to Z jest NWP X i Yn−1.
M.Kik “AiSD 5” – p. 11
Dowód Tw. o opt. podstrukturze NWP
D-d
1. Jeśli zk 6= xm to możnaby dołączyć xm = yn do Z
uzyskując dłuższy wspólny podciąg X i Y .
2. zk 6= xm, czyli Z jest wspólnym podciągiem Xm−1 i Y .
Gdyby istniał dłuższy wspólny podciąg W ciągów Xm−1
i Y , to W byłby też wspólnym podciągiem X i Y
dłuższym niż Z.
3. Analogicznie do poprzedniego przypadku.
¤
M.Kik “AiSD 5” – p. 12
Zależność rekurencyjna i algorytm c[i, j] – długość NWP prefiksów Xi i Yj.
0,
jeśli i = 0 lub j = 0
c[i, j] =
c[i − 1, j − 1] + 1
jeśli i, j > 0 i xi = yj
max(c[i, j − 1], c[i − 1, j])
jeśli i, j > 0 i xi 6= yj
LCS-Length(X,Y )
1 m ← length[X]
2 n ← length[Y ]
3 for i ← 1 to m do
4
c[i, 0] = 0
5 for j ← 1 to n do
6
c[0, j] = 0
...
M.Kik “AiSD 5” – p. 13
...
7 for i ← 1 to m do
8
for j ← 1 to n do
9
if xi = yj then
10
c[i, j] ← c[i − 1, j − 1] + 1
11
b[i, j] ← “ -00
else
12
if c[i − 1, j] > c[i, j − 1] then
13
c[i, j] ← c[i − 1, j]
14
b[i, j] ← “ ↑00
else
15
c[i, j] ← c[i, j − 1]
16
b[i, j] ← “ ←00
17 return c i b
Czas: Θ(nm), pamięć: Θ(nm).
M.Kik “AiSD 5” – p. 14
Print-LCS(b, X,i,j)
1 if i = 0 or j = 0 then
2
return
3 if b[i, j] =00-00 then
4
Print-LCS(b, X,i − 1,j − 1)
5
wypisz xi
else
6 if b[i, j] =00↑00 then
7
Print-LCS(b, X,i − 1,j)
8 else Print-LCS(b, X,i,j − 1)
Wywołanie: Print-Lcs(b,X, length[X], length[Y ]) Czas: O(m + n).
M.Kik “AiSD 5” – p. 15
triangulacja wielokąta wypukłego v0
v
v
1
6
v
v
2
5
v3
v4
Waga trójkąta: w(4vivjvk)
(n.p. w(4vivjvk) = |vivj| + |vjvk| + |vkvi|
Koszt triangulacji = suma wag jej trójkątów.
M.Kik “AiSD 5” – p. 16
Matrix-Chain-Order można przerobić aby rozwiązywał
problem triangulacji: zamiast p = hp0, . . . , pni – parametr v = hv0, . . . , vni, oraz wiersz 9 zast ępujemy: 9
q ← m[i, k] + m[k + 1, j] + w(4vivjvk)
związek z problemem nawiasowania
v
A
0
v
1
v
1
6
A
A
6
2
v
v
2
5
A3
A5
((A
v
1 (A2 A3)) (A4 (A5 A6)))
3 A
v
4
4
Jeśli Ai ma wymiary pi−1 × pi, to problem nawiasowania ciągu mnożeń A1 . . . An redukujemy do problemu triangulacji przyjmując: w(4vivjvk) = pipjpk.
M.Kik “AiSD 5” – p. 17
związek z problemem nawiasowania v
A
0
v
1
v
1
6
A
A
6
2
v
v
2
5
A3
A5
((A
v
1 (A2 A3)) (A4 (A5 A6)))
3 A
v
4
4
Jeśli Ai ma wymiary pi−1 × pi, to problem nawiasowania ciągu mnożeń A1 . . . An redukujemy do problemu triangulacji przyjmując: w(4vivjvk) = pipjpk. Algorytm Matrix-Chain-Order można przerobić aby rozwiązywał
problem triangulacji: zamiast p = hp0, . . . , pni – parametr v = hv0, . . . , vni, oraz wiersz 9 zast ępujemy: 9
q ← m[i, k] + m[k + 1, j] + w(4vivjvk)
M.Kik “AiSD 5” – p. 17
Niech T – optymalna triangulacja wielokąta wypukłego o wierzchołkach hv0 . . . vni, zawierająca 4v0vkvn. Waga T =
suma w(4v0vkvn) oraz wag trangulacji dwu wielokątów hv0 . . . vki i hvk . . . vni. Obie muszą być optymalne.
Równanie rekurencyjne:
Niech t[i, j] koszt optymalnej triangulacji hvi−1 . . . vji.
0
dla i = j
t[i, j] =
mini≤k≤j−1 {t[i, k] + t[k + 1, j]+
+w(4vi−1vkvj)}
dla i < j
Poza funkcją wagi – wzór identyczny ze wzorem na m[i, j].
Wniosek. Optymalną triangulację można wyznaczyć w czasie Θ(n3) i pamięci Θ(n2).
M.Kik “AiSD 5” – p. 18
Document Outline
- Programowanie dynamiczne
- Mno¿enie ci±gu macierzy
- liczba mo¿liwych nawiasowañ
- Struktura optymalnego nawiasowania
- Matrix-Chain-Order
- Wykonanie optymalnego mno¿enia
- Recursive-Matrix-Chain
- Oszacowanie $T(n)$
- Spamiêtywanie
- Lookup-Chain
- Najd³u¿szy Wspólny Podci±g
- Dowód Tw. o opt. podstrukturze NWP
- Zale¿no¶æ rekurencyjna i algorytm
- LCS-Length (c.d.)
- Print-LCS
- triangulacja wielok±ta wypuk³ego
- zwi±zek z problemem nawiasowania
- uzasadnienie
Wyszukiwarka
Podobne podstrony:
aisd5-1
aisd5 1
aisd5 2
aisd5
więcej podobnych podstron