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 nn

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 nn

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)