Sld 18.1. Zaawansowane

techniki

1.Algorytmy typu „dziel-i-

rządź”(“conquer and divide”)

2.Algorytmy „zachłanne“ (“żarłoczne”,

“greedy”)

3.Algorytmy dynamiczne

Sld 18.2. Algorytmy typu „dziel-i-

rządź“

Programowanie typu „dziel-i-rządź" polega na wykorzystaniu

podstawowej cechy rekurencji:

1. dekompozycji

problemu

na

pewną

skończoną

ilość

podproblemów tego samego typu,

2. rozwiązania podproblemów,
3. połączeniu częściowych rozwiązań w celu odnalezienia

rozwiązania globalnego.

 

Jeśli oznaczymy problem do rozwiązania przez Pb, a rozmiar danych

przez N, to zabieg wyżej opisany da się przedstawić za pomocą zapisu:

 

Pb(N) → Pb(N

1

) + Pb(N

2

) + ...+ Pb(N

k

) + KOMB(N).

 

Problem „rzędu" N został podzielony na k podproblemów.
Funkcja KOMB(N) nie jest rekurencyjna.

•

Technika „dziel-i-rządź" pozwala w wielu przypadkach na zmianę klasy

algorytmu (np. z O(n) do O(log

2

N) ).

•

Istnieje grupa zadań, dla których zastosowanie metody „dziel-i-rządź"

nie spowoduje przyspieszenia.

 

Sld 18.3. Algorytmy typu „dziel-i-

rządź“ - 2

Pb

0

Pb

1

Pb

i

Pb

n

Pb

1,1

Pb

1,k

Pb

i,1

Pb

i,l,

Pb

n,1

Pb

n,s

Pb

i,1,t

Pb

i,1,1

.

°°°

°°°

°°°

°°°

°°°

°°°

° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° °

° ° ° ° ° ° ° ° °

Sld 18.4. Quicksort

Złożoność O(n

log

2

n)

Sld 18.5. Przeszukiwanie binarne

Złożoność O(n log

2

n)

Binarne przeszukiwanie elementu

27

w liście



2 4 7 8 8 9 10 11 14 15 17 20 21 25 27 37 41 57 69 73 92 94



2 4 7 8 8 9 10 11 14 15 17

20 21 25 27 37 41 57 69 73 92 94



2 4 7 8 8 9 10 11 14 15 17

20 21 25 27 37

41 57 69 73 92 94



2 4 7 8 8 9 10 11 14 15 17 20 21 25

27 37

41 57 69 73 92 94



2 4 7 8 8 9 10 11 14 15 17 20 21 25

27

37 41 57 69 73 92 94

Sld 18.6. Znajdowanie zera

funkcji metodą

połowienia przedziału

a

b

x

3

x

4

x

2

x

1

y

x

1

= a+½(b - a); y >

0;
x

2

= a+½(x

1

- a); y <

0;
x

3

= x

2

+½(x

1

- x

2

); y >

0;
x

4

= x

2

+½(x

3

- x

2

); y >

0;
. . . . . . . . . . . . . . . . . .
. . .

x

Ilość iteracji i = log

2

((b – a)/ Δ;

Δ – dokładność obliczeń

Sld 18.7. Algorytmy „zachłanne“

(“żarłoczne“, ”greedy”)

• Cechą szczególną algorytmu „zachlannego" jest to, że w każdym

etapie poszukiwania rozwiązania wybiera on opcję lokalnie

optymalną. W zależności od tego doboru, rozwiązanie globalne

może być również optymalne, ale nie jest to gwarantowane.

y

x

Δ =
1,2,3,4,5,6

x

opt

y

min

y

min,loc

Sld 18.8. Ogólny problem

plecakowy

•Polega on na zapakowaniu do plecaka o ograniczonej pojemności możliwie

najbardziej wartościowych rzeczy. W innych zastosowaniach, może to dotyczyć

pakowania walizek, paczek, samochodu, samolotu itp.

• Dane:

   n rzeczy R

1

R

2

, ..., R

n

, każda w nieograniczonej ilości;

  rzecz R

i

waży w

i

i ma wartość p

i

.

   maksymalna pojemność plecaka, wynosząca W

max

.

• Wyniki:

Ilości n

i

, n

2

,..., n

n

, poszczególnych rzeczy (mogą być zerowe), których

całkowita waga W

nie przekracza W

max

i których sumaryczna wartość P jest

największa.

• W

= ∑ n

i

w

i

= n

1

w

1

+ n

2

w

2

+ ... +

n

n

w

n

≤ W

max

• P

= ∑ n

i

p

i

= n

1

p

1

+ n

2

p

2

+ … + n

n

p

i

→ max

 

Sld 18.9. Algorytm zachłanny dla

ogólnego problemu plecakowego

W decyzjach ścierają się ze sobą trzy kryteria

wyboru kolejnych rzeczy do zapakowania:

1.

wybierać najcenniejsze rzeczy, czyli w kolejności

nierosnących wartości p

t

;

2.

wybierać rzeczy zajmujące najmniej miejsca,

czyli w kolejności niemalejących wag w

i

3.

wybierać rzeczy najcenniejsze w stosunku do

swojej wagi, czyli w kolejności nierosnących

wartości ilorazu p

i

/w

i

.

Sld 18.10. Przyklad problemu

plecakowego

R

i

1

2

3

4

5

6

p

i

6

4

5

7

10

2

w

i

6

2

3

2

3

1

p

i

/w

i

6/6

4/2

5/3

7/2

10/3

2/1

Kryteria

n

1

p

1

n

1

w

1

n

2

p

2

n

2

w

2

n

3

p

3

n

3

w

3

n

4

p

4

n

4

w

4

n

5

p

5

n

5

w

5

n

6

p

6

n

6

w

6

? n

i

p

i

? n

i

w

i

1

0

0

0

1×7

1×2

7×10

7×3

0

77

23

2

0

0

0

0

0

23×2

23×1

46
23

3

0

0

0

11×7

11×2

0

1×2

1×1

79

23

W

max

= ∑ n

i

w

i

≤ 23

Sld 18.11. Programowanie

dynamiczne

1. koncepcja:
• dla danego problemu P stwórz rekurencyjny model

jego rozwiązania (wraz z jednoznacznym określeniem

przypadków elementarnych);

• stwórz tablicę, w której będzie można zapamiętywać

rozwiązania przypadków elementarnych i rozwiązania

podproblemów, które zostaną obliczone na ich

podstawie;

2. inicjacja:
• wpisz do tablicy wartości numeryczne, odpowiadające

przypadkom elementarnym;

3. progresja:
• na podstawie wartości numerycznych wpisanych do

tablicy używając formuły rekurencyjnej, oblicz

rozwiązanie problemu wyższego rzędu i wpisz je do

tablicy;

• postępuj w ten sposób do osiągnięcia pożądanej

wartości.

Sld 18.12.

Ciąg Fibonacciego

fib(4)=
5

fib(1)=
1

fib(1)=
1

fib(2) =
2

fib(1)=
1

fib(0)=
1

fib(3)=3

fib(2)=
2

fib(1)=
1

fib(5)=8

fib(1)=
1

fib(0)=1

fib(3)=3

fib(2)=2

fib(1)=
1

fib(0) = 1,

fib(1) = 1,

fib(n) = f(n - I) + fib(n - 2) gdzie n ≥ 2; N

f

= 1, 1, 2, 3, 5, 8, 13, 21, 34,

55, ...

Tablica dla zapamiętywania rozwiązania podproblemów:

Sld 18.13. Dwuwymiarowy wzór

rekurencyjny.

Do obliczenia wartości P(i, j) potrzebna jest znajomość

dwóch sąsiednich komórek: dolnej - P(ij-l) oraz tej

znajdującej się z lewej strony - P(i-l,j). Naturalnym

sposobem obliczania wartości P(i,j) będzie posuwanie się

„zygzakiem" zaznaczonym na rysunku.

Sld 18.14. Znajdowanie

najkrótszej drogi do wyjścia z

labiryntu

1.

Rozpowszechnianie fali od pola S.

2.

Zwinięcie fali od pola wyjścia C1.

Sld 18.23. Literatura

1. P.Wróblewski. Algorytmy.

Struktury danych i techniki

programowania. Helion. 2001.

2. K.A.Lambert, D.W.Nance, T.L.Naps.

Introduction to Computer Science

with C++. Books/Cole, 2000.

3. M.M. Syslo. Algorytmy. Warszawa,

WSP, 1997.