METODY
TWORZENIA ALGORYTMÓW
M.Skowrońska, WMiI UMK
METODY
TWORZENIA ALGORYTMÓW
M.Skowrońska, WMiI UMK
METODA PRZYROSTOWA
M.Skowrońska, WMiI UMK
{Sortuje tablicę A[1..n] liczb rzeczywistych :
≤
}
1. for j := 2 to n do
begin
2. pom := A[j] ;
{ wstaw A[j] w posortowany ciąg A[1 .. j-1] }
3. i:= j-1;
4. while (i>0) and (A[i]>pom) do
4. while (i>0) and (A[i]>pom) do
begin
5. A[i+1]:= A[i];
6. i:= i-1;
end;
7. A[i+1]:= pom;
end;
M.Skowrońska, WMiI UMK
"DZIEL I ZWYCIĘśAJ"
3 ETAPY :
1. DZIEL
2. ZWYCIĘśAJ
2. ZWYCIĘśAJ
3. POŁĄCZ
M.Skowrońska, WMiI UMK
SORTOWANIE PRZEZ SCALANIE
5 2 4 6
1 3 2 6
5 2
4 6
1 3
2 6
5 2 4 6 1 3 2 6
5 2 4 6 1 3 2 6
2 5
4 6
2 6
1 3
2 4 5 6
1 2 3 6
1 2 2 3 4 5 6 6
M.Skowrońska, WMiI UMK
MERGE-SORT ( A, p, k);
{ Sortuje elementy w podtablicy A[p..k];
jeśli p >= k to podtablica jest juŜ posortowana;
jeśli p < k to dzieli A[p..k] na dwie podtablice , sortuje kaŜdą z nich
i łączy w posortowaną podtablicę A[p..k];}
begin
if p < k then
begin
q := (p+k)/2 ;
ZłoŜoność : T(n) =
Θ
Θ
Θ
Θ
(nlgn)
q := (p+k)/2 ;
MERGE-SORT ( A, p, q );
MERGE-SORT ( A, q+1, k );
MERGE (A, p, q, k);
end
end;
MERGE-SORT( A, 1, n )
{ s
ortuje tablicę A[1..n] }
M.Skowrońska, WMiI UMK
ZAD. Napisz pseudokod procedury MERGE (A, p, q, k);
M.Skowrońska, WMiI UMK
ALGORYTMY ZACHŁANNE
(GREEDY ALGORITHMS)
M.Skowrońska, WMiI UMK
DANE : Z = {1, 2, ... n } - zbiór n zajęć , n>0
[ p
i
, k
i
) p
i
- czas rozpoczęcia zajęcia i
k
i
- czas zakończenia zajęcia i p
i
< k
i
PLANOWANIE ZAJĘĆ
WYNIK: Największy podzbiór PZ zbioru Z, który zawiera zajęcia zgodne,
tzn.: i, j
∈
PZ , to [ p
i
, k
i
)
∩
∩
∩
∩
[ p
j
, k
j
) =
∅
∅
∅
∅
M.Skowrońska, WMiI UMK
GREEDY-ACTIVITY-SELECTOR ( p, k, n);
{ p- tablica początków zajęć, k- tablica końców zajęć;
zakładamy, Ŝe k [1]
≤
k [2]
≤
...
≤
k [n] }
begin
PZ := {1};
for i := 2 to n do
if p [i]
≥
k [j] then
begin
PZ := PZ
∪
{i};
PZ := {1};
j := 1;
PZ := PZ
∪
{i};
j := i
end;
return PZ;
{ PZ - największy podzbiór zajęć
parami zgodnych }
end;
M.Skowrońska, WMiI UMK
B
C
A
E
3
5
2
1
6
D
1
5
10
M.Skowrońska, WMiI UMK
PROGRAMOWANIE DYNAMICZNE
RozwiąŜ "małe" problemy.
Scharakteryzuj strukturę optymalnego rozwiązania
Zapamiętaj rozwiązania.
UŜyj tych rozwiązań do rozwiązania "duŜych" problemów
M.Skowrońska, WMiI UMK
MnoŜenie ciągu macierzy
DANE
:
n
∈
N
,
p
0
, p
1
, ... , p
n
∈
N
A
1
, ... , A
n
- macierze prostokątne o elementach rzeczywistych,
A
i
ma rozmiar p
i-1
* p
i
.
WYNIK : A
1
* ... * A
n
obliczony w sposób optymalny, tzn.:
liczba wykonanych mnoŜeń elementów macierzy
jest najmniejsza
"Optymalne nawiasowanie"
M.Skowrońska, WMiI UMK
DANE : A
1
- 10x100 A
2
- 100x5 A
3
- 5x50
WYNIK : A
1
A
2
A
3
- optymalnie
(A
1
A
2
)A
3
A
1
A
2
10x100x5
= 5000 => A
1
A
2
(10x5)
(A
1
A
2
)A
3
10x5x50
= 2500
Przykład :
A
1
(A
2
A
3
)
1
2
3
ΣΣΣΣ
7500
A
2
A
3
100x5x50
= 25000 => A
2
A
3
(100x50)
A
1
(A
2
A
3
) 10x100x50
= 50000
ΣΣΣΣ
75000
M.Skowrońska, WMiI UMK
MATRIX-MULTIPLY ( A, B );
{ Oblicza iloczyn : C = A * B }
begin
if kol(A) <> rows(B) then error
else for i := 1 to rows (A) do
for j := 1 to kol (B) do
begin
begin
C [i,j ] := 0;
for k := 1 to kol (A) do
C [i,j ] := C [i,j] + A [i,k] * B [k,j] ;
end;
return C;
end;
M.Skowrońska, WMiI UMK
Struktura optymalnego nawiasowania :
m [i,j] = minimalna liczba mnoŜeń potrzebna do obliczenia iloczynu A
i
*...*A
j
0 dla i = j
m [i,j] =
m [i,j] =
min { m [i,k] + m [k+1, j ] + p
i-1
* p
k
* p
j;
} dla i < j
i
≤
k < j
M.Skowrońska, WMiI UMK
MATRIX-CHAIN-ORDER ( p );
{ p[0..n] – tablica rozmiarów macierzy A
1
, ... , A
n
,
tzn .: A
i
ma rozmiar p[i-1] * p[i] }
begin
n := length (p) - 1;
for i := 1 to n do
m [i,i] := 0;
for r := 2 to n do
for i := 1 to n-r+1 do
begin
j := i + r – 1;
m [i,j] :=
∞
;
for k := i to j–1 do
for k := i to j–1 do
begin
q := m [i,k] + m [k+1, j ] + p
i-1
* p
k
* p
j;
if q < m [i,j ] then begin
m [i,j ] := q ;
s [i,j] := k
end end end
return m and s
end ;
M.Skowrońska, WMiI UMK
M.Skowrońska, WMiI UMK
MATRIX-CHAIN-MULTIPLY ( A, s, i, j);
{Oblicza optymalnie iloczyn A
i
* A
i+1
* ... * A
j
}
begin
if j > i then
begin
X := MARTIX-CHAIN-MULTIPLY(A, s, i,s[i,j]);
Y := MARTIX-CHAIN-MULTIPLY(A, s, s[i,j ] +1, j);
Z := MATRIX-MULTIPLY ( X, Y );
Z := MATRIX-MULTIPLY ( X, Y );
return Z
end
else return A
i
end;
MATRIX-CHAIN-MULTIPLY( A, s, 1, n);
M.Skowrońska, WMiI UMK
REKURENCJA
Liczby Fibonacciego
DANE : n
∈
N; n>=0
WYNIK : n - ta liczba Fibonacciego
fib( n: integer) : integer;
fib( n: integer) : integer;
begin
if ( (n =0) or (n= 1)) then fib := 1;
else
fib := fib(n-1) + fib(n-2)
end;
złoŜoność O(c
n
)
c = ((1+
√√√√
5)/2
M.Skowrońska, WMiI UMK
f8
f6
f7
f4 f5 f5 f6
f2
f3
f3
f4
f3
f4 f4 f5
fib(8)
f2
f3
f3
f4
f3
f4 f4 f5
f0 f1 f1
f2
f1
f2
f2
f3
f1
f2
f2
f3
f2
f3
f3
f4
f0 f1 f0 f1 f0 f1 f1
f2
f0 f1 f0 f1 f1
f2
f0 f1 f1
f2
f1
f2
f2
f3
f0 f1 f0 f1 f0 f1 f0 f1 f0 f1 f1
f2
f0 f1
M.Skowrońska, WMiI UMK
metoda dynamiczna -
złoŜoność O(n)
fib ( n: integer ) : integer;
f1, f2, f, k : integer;
begin
if ( n = 0 )or( n=1 )then fib := 1
else
begin
f1: = f2: = 1;
f1: = f2: = 1;
for k:= 2 to k := n-1 do
begin
f := f1 + f2;
f1 := f2;
f2 := f;
end;
end
end;
M.Skowrońska, WMiI UMK
PROBLEM PLECAKOWY
• Dyskretny problem plecakowy
DANE : n
∈
N
,
W
∈
Z
≥
0
P = {p
1
, ... , p
n
}, p
i
∈
N
c
1
, ... , c
n
∈
Z
≥
0
, w
1
, ... , w
n
∈
Z
≥
0
WYNIK : { p
i1
, ... , p
ik
} : {p
i1
, ... , p
ik
}
⊆
P , k
≤
n, w
i1
+ ... + w
ik
≤
W,
c
i1
+ ... + c
ik
= max { c
j1
+ ... + c
jr
: r
≤
n, {p
j1
, ... , p
jr
}
⊆
P, w
j1
+ ... + w
jk
≤
W }
M.Skowrońska, WMiI UMK
• Ciągły problem plecakowy
DANE : n
∈
N
,
W
∈
Z
≥
0
P= {p
1
, ... , p
n
} p
i
∈
N , i=1,...,n
c
1
, ... , c
n
∈
Z
≥
0
, w
1
, ... , w
n
∈
Z
≥
0
WYNIK : { p
i1
, ... , p
ik
} , { b
i1
, ... , b
ik
} : {p
i1
, ... , p
ik
}
⊆
P , b
ir
≤
w
ir
,
WYNIK : { p
i1
, ... , p
ik
} , { b
i1
, ... , b
ik
} : {p
i1
, ... , p
ik
}
⊆
P , b
ir
≤
w
ir
,
b
i1
+ ... + b
ik
≤
W, r=1,...,k, k
≤
n,
(c
i1
/w
i1
)b
i1
+ ... + (c
ik
/w
ik
)b
ik
=
max {(c
j1
/w
j1
)b
j1
+ ... + (c
jr
/w
jr
)b
jr
: r
≤
n, {p
j1
, ... , p
jr
}
⊆
P, w
j1
+ ... + w
jr
≤
W }
M.Skowrońska, WMiI UMK
10
kg
20
kg
30
kg
60 zł 100 zł 120 zł
P1
P2
P3
50
kg
20
30
Rozw. optymalne dla
problemu dyskretnego 1.
Plecak
P3
P2
60 zł 100 zł 120 zł
problemu dyskretnego 1.
120 + 100 =220 zł
Plecak
2. Wybór zachłanny - według ceny jednostkowej
P1 : 6 zł/kg
P2 : 5 zł/kg
P3 : 4 zł/kg
Problem dyskretny : nie daje rozwiązania optymalnego 10*6 + 20 *5 = 160
Problem ciągły : otrzymamy rozwiązanie optymalne 10*6 + 20*5 *+20*4 = 240
1.
Problem dyskretny : wybór zachłanny - według ceny produktu