AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 1
Techniki budowania algorytmów
Co w ramach wykładu?
1. Rekurencja
2. Dziel i zwyciężaj
3. Programowanie dynamiczne
4. Metoda zachłanna
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 1
Techniki budowania algorytmów
Co w ramach wykładu?
1. Rekurencja
2. Dziel i zwyciężaj
3. Programowanie dynamiczne
4. Metoda zachłanna
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 2
Dziel i zwyciężaj
Schemat ogólny
Trzy zasadnicze kroki:
1.transformacja danych x na dane x
1
, . . . , x
k
o mniejszym rozmiarze;
2.rozwiązanie problemu dla danych x
i
(i = 1, . . . , k);
3.obliczenie rozwiązania dla danych x na podstawie wyników otrzymanych
w punkcie 2.
W naturalny sposób implementowane są jako procedury rekurencyjne:
function DiZ(x)
if x jest małe lub proste then return AdHoc(x)
przekształć x na x
1
, . . . , x
k
o mniejszym rozmiarze
niż x
for i ← 1 to k do y
i
← DiZ(x
i
)
na podstawie y
1
. . . y
k
oblicz rozwiązanie y dla x
return y
Bitwa pod Austerlitz, 2 grudnia 1805 r. – zwycięstwo wojsk Napoleona nad
liczniejszymi
o około 15 000 żołnierzy połączonymi armiami Austrii i Rosji.
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 3
Przykład 1 – Wyszukiwanie binarne
Wyszukiwanie binarne
Problem: czy klucz x znajduje się w posortowanej tablicy S,
zawierającej n kluczy?
Dane wejściowe: całkowita liczba dodatnia n, tablica kluczy S
indeksowana od 1 do n oraz klucz x.
Dane wyjściowe: location – lokalizacja klucza x w tablicy S (0, jeśli x
nie występuje w S)
Algorytm wyszukiwania binarnego
Jeżeli x jest równe elementowi środkowemu, kończymy. W przeciwnym
przypadku:
1.Dzielimy tablicę na dwie podtablice o rozmiarze mniej więcej dwa razy
mniejszym od oryginalnej. Jeżeli x jest mniejsze od elementu
środkowego, wybieramy lewą podtablicę. Jeśli x jest większe od
elementu środkowego, wybieramy prawą podtablicę.
2.Zwyciężamy (rozwiązujemy) podtablicę poprzez określenie, czy x do
niej należy. O ile podtablica nie posiada dostatecznie małych rozmiarów,
należy wykorzystać rekurencję.
3.Otrzymujemy rozwiązanie problemu tablicy na podstawie rozwiązania
problemu podtablicy.
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 4
Wyszukiwanie binarne c.d.
int location(int low, int high)
{
int mid;
if (low > high)
return 0;
else {
mid = (low+high)/2;
if (x == S[mid])
return mid;
else if (x < S[mid])
return location(low, mid-1);
else
return location(mid+1, high);
}
}
Operacja podstawowa:
porównanie x z S[mid]
Rozmiar danych wejściowych:
liczba n elementów
tablicy S
Złożoność czasowa w
najgorszym przypadku:
W(n) = W(n/2) + 1 , W(1) = 1
W(n) = lgn + 1
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 5
Przykład 2 – Sortowanie przez scalanie
Sortowanie przez scalanie
Problem: posortować n kluczy w ciąg niemalejący
Dane wejściowe: całkowita liczba dodatnia n, tablica kluczy S
indeksowana od 1 do n.
Dane wyjściowe: tablica S, zawierająca klucze w porządku
niemalejącym
Algorytm sortowania przez scalanie
1.Dzielimy tablicę na dwie podtablice o rozmiarze mniej więcej dwa razy
mniejszym od oryginalnej.
2.Zwyciężamy (rozwiązujemy) każdą podtablicę, sortując ją. O ile
podtablica nie posiada dostatecznie małych rozmiarów, należy
wykorzystać rekurencję.
3.Łączymy rozwiązania podtablic poprzez scalenie ich w jedną
posortowaną tablicę.
MERGE-SORT(A, p, r)
if p < r
then q ← (p + r)/2
MERGE-SORT(A, p, q)
MERGE-SORT(A, q+1, r)
MERGE (A, p, q, r)
Jak scalić dwie posortowane tablice w
jedną posortowaną tablicę w czasie
(n)?
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 6
Sortowanie przez scalanie c.d.
void merge(Item c[], Item a[], int n, Item b[], int m)
{
for (int i = 0, j = 0, k = 0; k < n + m; k++)
{
if (i == n) { c[k] = b[j++]; continue; }
if (j == m) { c[k] = a[i++]; continue; }
c[k] = (a[i] < b[j]) ? a[i++] : b[j++];
}
}
Funkcja scalająca dwie uporządkowane tablice a i b w jedną
uporządkowaną tablicę c.
Koszt
Dziel
–
znalezienie środka przedziału zajmuje czas stały:
(1)
Zwyciężaj
–
rekurencyjne rozwiązanie dwóch podproblemów o
rozmiarze n/2, co daje czas 2T(n/2)
Połącz –
merge działa w czasie (n)
)
log
(
1
,
)
(
)
2
/
(
2
1
,
)
1
(
)
(
n
n
n
n
n
T
n
n
T
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 7
Przykład 3 – Sortowanie szybkie
Algorytm szybkiego sortowania QS (Quick-sort )
W każdym kroku algorytmu, elementy sortowanego ciągu e
l
, ..., e
r
są
rozdzielane, względem wybranego elementu v, na podzbiór elementów
mniejszych i podzbiór elementów większych od v (element v nazywa się
medianą).
{e
l
, ..., e
j-1
} < v <= {e
j+1
, ..., e
r
}.
W ten sposób znana jest ostateczna pozycja elementu v w końcowym
uporządkowaniu : element v będzie umieszczony na pozycji j-tej.
Następnie każdy z podzbiorów {e
l
, ..., e
j-1
} oraz {e
j+1
, ..., e
r
} jest sortowany
osobno według tego samego algorytmu.
Przykład rozdzielania zbioru - podstawowy krok
algorytmu QS
Dla ciągu, który chcemy uporządkować niemalejąco:
10, 5, 7, 8, 14, 12, 3, 5, 1
przyjmijmy, że v jest pierwszym elementem ciągu: v = 10. Podzbiór
elementów mniejszych od v to {5,7,8,3,5,1}, a podzbiór elementów
większych lub równych v to {14,12}:
{5,7,8,3,5,1} < 10 <= {14,12}.
Niech v = 5 dla lewego podzbioru. Element 5 jest większy od 3 i 1, a
niewiększy od 5, 7, 8:
{3,1} < 5 <= {5,7,8}
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 8
Sortowanie szybkie c.d.
Algorytm
QuickSort(l, r);
if l < r then
j := Partition(l, r);
(*algorytm rozdzielania*)
QuickSort(l, j-1);
(*sortowanie elementów mniejszych
od v*)
QuickSort(j+1, r)
(*sortowanie elementów
niemniejszych niż v*)
int Partition(l, r)
e := c[l];
//element dzielący
while (l < r)
while ((l < r) (c[r] >= e)) r r – 1
while ((l < r) (c[l] < e)) l l + 1
if (l < r) then c[l] c[r]
return l;
Algorytm rozdzielania
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 9
Sortowanie szybkie c.d.
Czas działania algorytmu quicksort
1. Przypadek najgorszy – procedura dzieląca tworzy jeden obszar
złożony z n – 1 elementów, a drugi tylko z 1 elementu.
W(n) = W(n – 1) + (n)
(koszt podziału wynosi (n))
Ponadto W(1) = (1), zatem
2. Przypadek najlepszy – podział na obszary o rozmiarach (około) n/2
B(n) = 2B(n/2) + (n)
co daje zależność B(n) = (n lgn)
3. Przypadek średni
skąd A(n) = (n lgn)
n
k
n
k
n
k
k
n
n
W
n
W
1
2
1
)
(
)
(
)
(
)
1
(
)
(
1
)
(
)
1
(
1
)
(
1
n
p
n
A
p
A
n
n
A
n
p
Średni czas sortowania
podtablic,
kiedy pivotpoint to p
Czas podziału
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 10
Przykład 4 – Jeszcze raz algorytm rozdzielania
Problem:
znaleźć k-ty największy element tablicy S
Dane wejściowe:
całkowita liczba dodatnia n, tablica liczb S
indeksowana od 1 do n oraz k takie, że 1 k n.
Dane wyjściowe:
element select tablicy S taki, że dokładnie k-1
elementów tablicy S jest większych od select.
1.
Prosty algorytm – k-krotne wyszukiwanie maksimum
ogólnie złożoność (n
2
)
2.
Posortowanie tablicy i odczytanie k-tego elementu j.w.
2. Idea algorytmu Hoare:
i.
Rozdzielić elementy tablicy na mniejsze i większe względem
pewnego elementu m, np. względem pierwszego lub ostatniego
elementu tablicy. Niech x będzie liczbą elementów większych od m.
ii. Jeżeli x > k-1, to elementu k-tego szukamy wśród elementów
większych od m, stosując to samo postępowanie.
iii. Jeżeli x = k-1, to m jest szukanym, k-tym co do wielkości
elementem tablicy.
iv. Jeżeli x < k-1, to wśród elementów mniejszych od m szukamy (tą
samą metodą) elementu (k-x-1)-tego co do wielkości.
Wyznaczanie k-tego największego elementu w ciągu
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 11
Algorytm Hoare
Przykład
Szukamy 6-tego elementu w ciągu:
c = (6, 4, 1, 8, 7, 3, 2, 5, 9, 0).
Jako element rozdzielający przyjmujemy pierwszy wyraz ciągu. Po pierwszym
podziale:
4, 1, 3, 2, 5, 0,
6
, 8, 7, 9
Zgodnie z punktem iv. algorytmu, szukamy teraz elementu drugiego co do
wielkości
(k – x – 1 = 6 – 3 – 1 = 2) w ciągu elementów mniejszych od 6, czyli w ciągu
4, 1, 3, 2, 5, 0.
Po rozdzieleniu tego ciągu względem 4 otrzymamy
1, 2, 3, 0,
4
, 5
bo tylko jeden element jest większy od 4. Na mocy punktu iii. algorytmu
Hoare, 4 jest szukanym, szóstym co do wielkości elementem danego ciągu c.
Jak przebiegną poszukiwania, gdy jako element rozdzielający przyjmiemy
ostatni wyraz ciągu?
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 12
Algorytm Hoare
elem Hoare (e: ciąg, l, p, k: int)
{
j := Partition(l,p);
// j jest pozycją elementu rozdzielającego:
na
// prawo elementy większe, na lewo
elementy
// niewiększe
if (p-j = k-1) then result := e[j]
// e[j] jest mniejsze od dokładnie k-1
elementów
else
if (p-j>k-1) then
// jest co najmniej k elementów większych
od e[j]
result:=Hoare(e, j+1, p, k);
// e[result] jest k-tym co do wielkości
elementem
// ciągu e[j+1],...,e[p]
else result:=Hoare(e, l, j-1, k-(p-j+1);
// e[result] jest k-(p-j+1)-tym
co do wielkości
// elementem
ciągu e[l],e[l+1],...,e[j-1]
return e[result]
// e[result] jest k-tym co do wielkości
elementem
// ciągu e
}
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 13
Koszt algorytmu Partition
Liczba porównań wykonanych w procesie rozdzielania zależy od liczby
elementów znajdujących się w rozważanej części ciągu. W każdej iteracji
pętli "while" wykonujemy tylko jedno porównanie. Pętla "while" jest
wykonywana dokładnie r - l razy. Zatem dla ciągu n elementowego koszt
algorytmu Partition wynosi:
T(n) = (n).
Koszt algorytmu Hoare
W najgorszym przypadku algorytm Hoare może działać tak źle, jak
algorytm naiwny. Jeżeli dany ciąg jest uporządkowany rosnąco, to w każdym
rekurencyjnym wywołaniu funkcji Partition, liczba elementów mniejszych od
rozdzielającego jest zbiorem pustym. Zatem, o ile trzeba kontynuować
poszukiwania k-tego co do wielkości elementu, kontynuuje się je w ciągu
elementów o jeden krótszym. Biorąc pod uwagę koszt Partition,
otrzymujemy
(n-1) + (n-2) + ... +(n-k) = kn - k(k+1)/2
porównań w przypadku pesymistycznym.
Na szczęście koszt średni algorytmu Hoare jest zdumiewająco dobry.
Udowodniono, że średni koszt algorytmu Hoare jest liniowy O(n).
Algorytm Hoare - złożoność czasowa
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 14
Przykład 5 – Mnożenie (bardzo) dużych liczb
Dane wejściowe: liczy naturalne a i b (długie)
Wynik: iloczyn a·b
Dla prostoty zakładamy, że a i b mają tą samą długość n bitów.
Pomysł:
1.Dzielimy n-bitowe czynniki na części n/2 - bitowe.
a = a
1
·2
s
+a
0
i b = b
1
·2
s
+b
0
,
gdzie s = n/2 i 0 a
1
, a
0
, b
1
, b
0
2
s
.
2.Zwyciężamy mnożąc przez siebie otrzymane części
c
2
= a
1
·b
1
, c
1
= a
1
·b
0
+ a
0
·b
1
, c
0
= a
0
·b
0
3.Łączymy wyniki i uzyskujemy końcowy wynik
a·b = c
2
·2
2s
+ c
1
·2
s
+ c
0
Podsumowanie:
Mnożenie dwóch liczb n-bitowych zastępujemy
czterema mnożeniami liczb n/2-bitowych, dwoma mnożeniami przez
potęgę 2 (czas liniowy)
i trzema dodawaniami (czas liniowy) . Czyli T(n) = 4T(n/2) + (n)
Stąd: T(n) = (n
2
) , czyli… żaden zysk
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 15
Mnożenie dużych liczb c.d.
Zyskamy, jeśli zamiast czterech mnożeń liczb n/2-bitowych wystarczą trzy.
c
1
= (a
1
+ a
0
)(b
1
+ b
0
) – c
0
– c
2
multiply(a, b)
n max(|a|, |b|) //|x| oznacza długość liczby n
If n jest małe then pomnóż a i b klasycznym algorytmem
return obliczony iloczyn
s n/2
a
1
a/2
s
; a
0
a mod 2
s
b
1
b/2
s
; b
0
b mod 2
s
z multiply(a
0
, b
0
)
y multiply(a
1
+a
0
, b
1
+b
0
)
x multiply(a
1
, b
1
)
return 2
2s
x + 2
s
(y – x – z) + z
Tym razem:
co daje ostatecznie T(n) = O(n
log3
) ≈ O(n
1,585
)
1
dla
)
(
)
2
/
(
3
1
dla
)
(
n
n
n
T
n
k
n
T
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 16
Przykład 6 – Mnożenie macierzy
Problem:
wyznaczyć iloczyn dwóch macierzy o wymiarach nn
Dane wejściowe:
dodatnia liczba całkowita n, dwuwymiarowe
tablice liczb A i B z wierszami i kolumnami indeksowanymi
od 1 do n.
Dane wyjściowe:
dwuwymiarowa tablica liczb C (wiersze i kolumny
indeksowane od
1 do n), zawierająca iloczyn macierzy A i B.
Algorytm działający według definicji mnożenia macierzy
MATRIX-MULTIPLY(A, B, n)
for i 1 to n
for j 1 to n
c
ij
0
for k 1 to n
c
ij
c
ij
+ a
ik
·b
kj
return C
Operacja podstawowa – mnożenie elementów macierzy
Złożoność czasowa: T(n) = (n
3
)
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 17
Mnożenie macierzy c.d.
Metoda Strassena
22
21
12
11
22
21
12
11
22
21
12
11
b
b
b
b
a
a
a
a
c
c
c
c
n/2
n/2
M
1
= (A
11
+ A
22
)(B
11
+ B
22
)
M
2
= (A
21
+ A
22
)B
11
M
3
= A
11
(B
12
- B
22
)
M
4
= A
22
(B
21
– B
11
)
M
5
= (A
11
+ A
12
)B
22
M
6
= (A
21
– A
11
)(B
11
+ B
12
)
M
7
= (A
12
- A
22
)(B
21
+ B
22
)
C
11
= M
1
+ M
4
– M
5
+ M
7
C
12
= M
3
+ M
5
C
21
= M
2
+ M
4
C
22
= M
1
+ M
3
– M
2
+ M
6
Złożoność czasowa w każdym przypadku (dla n będącego potęgą 2):
T(n) = 7T(n/2) dla n>1
(nie uwzględniamy 18 dodawań i odejmowań
T(1) = 1
Rozwiązanie rekurencji daje: T(n) = (n
log7
) ≈ (n
2,81
)
czyli składnika18(n/2)
2
)
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 18
Mnożenie macierzy – który algorytm wybrać?
Porównanie algorytmów mnożenia macierzy o wymiarach nn
Algorytm
standardowy
Algorytm
Strassena
Mnożenia
n
3
n
2,81
Dodawania i
odejmowania
n
3
– n
2
6n
2,81
– 6n
2
Inne (lepsze?) wyniki:
1.Samuel Winograd (1988) – metoda wymagająca 15 operacji dodawania
i odejmowania, co daje złożoność czasową operacji dodawania i
odejmowania 6n
2,81
– 6n
2
2.Coppersmith i Winograd (1987) – algorytm o złożoności operacji
mnożenia O(n
2,38
),
ale o dużej stałej
Mnożenie macierzy wymaga algorytmu o złożoności co najmniej
kwadratowej. Nikt jeszcze takiego nie znalazł ani nie udowodnił, że
takiego nie ma.
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 19
Dziel i zwyciężaj – Znajdowanie pary najmniej
odległych punktów
Problem
Dane: Zbior P = {(x
1
, y
1
), . . . , (x
n
, y
n
)} współrzędnych punktów
na płaszczyźnie.
Zadanie:
Znaleźć dwa najbliżej położone względem siebie
punkty w P, tj. znaleźć
i,j takie, że d(x
i
, y
i
, x
j
, y
j
) = min{d(x
k
, y
k
, x
l
, y
l
) | 1 k < l n},
gdzie
Siłowe rozwiązanie, polegające na wyliczeniu i porównaniu
odległości między każdą parą punktów, wymaga czasu
2
2
)
(
)
(
)
,
,
,
(
l
k
l
k
l
l
k
k
y
y
x
x
y
x
y
x
d
)
(
2
)
(
2
n
n
n
T
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 20
Strategia Dziel i Zwyciężaj
1.
(a) Sortujemy punkty z P według współrzędnych x i
zapamiętujemy je w tablicy X;
(b) Sortujemy punkty z P według współrzędnych y i zapamiętujemy je w
tablicy Y ;
(c) Znajdujemy prostą l dzielącą P na dwa równoliczne (z dokładnością do
1) podzbiory:
• P
L
- podzbiór punktów leżących na lewo od l,
• P
R
- podzbiór punktów leżących na prawo od l.
Punkty znajdujące się na prostej l (o ile są takie) kwalifikujemy do tych
podzbiorów
w dowolny sposób.
2. { rekurencyjnie }
(i
1
, j
1
) para punktów z P
L
o najmniejszej odległości;
(i
2
, j
2
) para punktów z P
R
o najmniejszej odległości.
3.
Niech (i′, j′) będzie tą parą punktów znalezioną w kroku 2, dla
której odległość (oznaczmy ją przez d) jest mniejsza.
Sprawdzamy czy istnieje para punktów (t, s) odległych o mniej niż d
takich, że t P
L
i s P
R
. Jeśli istnieje, przekazujemy ją jako wynik procedury, w
przeciwnym razie jako wynik przekazujemy parę (i′, j′).
Znajdowanie pary najmniej odległych punktów c.d.
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 21
Znajdowanie pary najmniej odległych punktów c.d.
Realizacja kroku 3
Oznaczmy przez P
C
zbiór tych punktów z P, które leżą w odległości nie
większej niż d od prostej l. Niech Y′ oznacza tablicę Y, z której usunięto
wszystkie punkty spoza P
C
.
Wtedy:
Jeśli (t, s) jest parą punktów odległych o mniej niż d taką, że t P
L
i s
P
R
, to t i s należą do P
C
. Ponadto w tablicy Y‘ pomiędzy t a s leży nie
więcej niż 6 punktów.
W kroku 3 pary (t, s) należy szukać tylko w zaznaczonym pasie
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 22
Jeśli p ma być jednym z punktów pary (t, s), to drugi punkt musi
znajdować się w kwadracie B. Ponadto wszystkie punkty z Y ′ leżące
między t a s muszą leżeć w A lub w B.
W części A leżą tylko punkty z P
L
. Ponieważ każde dwa z nich odległe są
od siebie o co najmniej d, więc może ich tam znajdować się co najwyżej 4.
Z analogicznego powodu w części B może znajdować się nie więcej niż 4
punkty z P
R
. Tak więc w całym prostokącie znajduje się nie więcej niż 8
punktów.
Krok 3 sprowadza się więc do utworzenia tablicy Y ′, a następnie do
obliczenia odległości każdego punktu z Y ′ do co najwyżej siedmiu
punktów następujących po nim w tej tablicy.
Znajdowanie pary najmniej odległych punktów c.d.
AiSD - Wykład 4 – Dziel i zwyciężaj
Slajd 23
Złożoność czasowa
Krok 1:
– Sortowanie - (n log n).
– Znalezienie prostej l i podział P na podzbiory - koszt
stały.
Krok 2:
– 2T(n/2)
Krok 3:
– Utworzenie Y ′ - (n).
– Szukanie pary (t, s) - (n).
Znajdowanie pary najmniej odległych punktów -
koszt
Zauważywszy, że sortowanie punktów w każdym wywołaniu
rekurencyjnym jest zbyteczne otrzymuje się złożoność:
T(n) = (n log n)