C2142 Návrh algoritmů pro přírodovědce
10. Přístupy k řešení problémů I.
Tomáš Raček
Jaro 2017
Hrubá síla
Hrubá síla (brute force) představuje přímočarý přístup založený na
definici problému.
Vlastnosti
• obecně výpočetně nejnáročnější postup → použitelné pouze
pro velmi malé instance problémů
• v případě optimalizačních úloh se jedná o zkoušení všech
potenciálních řešení
• pro některé typu problémů jediná možnost
Příklady
• Selection sort
• naivní násobení matic
• jednoduché hledání podřetězce v textu
Rekurzivní algoritmy
Myšlenka rekurzivních algoritmů spočívá v znovupoužití algoritmu
na problém menší velikosti. Speciální (triviální) případy řešíme
přímo.
def fact_recursive(n):
return n * fact_recursive(n - 1) if n > 0 else 1
def fact_iterative(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
Poznámka. Volání funkce je ve srovnání s iterací cyklu drahá
operace. Vysoká úroveň rekurzivního zanoření navíc může narazit
na limity velikosti zásobníku.
Hanoiské věže
Hanoiské věže jsou hlavolam, v rámci kterého je potřeba přemístit
všechny disky z jednoho kolíku na jiný za dodržení dalších pravidel.
Poznámka. Existuje velmi jednoduché rekurzivní řešení.
Složitost řešení problému Hanoiských věží je exponenciální vůči
počtu disků (přesně 2n − 1 operací).
Rozděl a panuj
Rozděl a panuj (divide and conquer, D & C) je přístup vycházející
z rekurzivních algoritmů založený na dělení problému na menší,
snadněji zvládnutelné, podproblémy.
Princip
1. Rozděl problém na menší podproblémy
• stejného typu
• nepřekrývající se
2. Rekurzivně vyřeš každý podproblém
3. Zkombinuj řešení podproblémů v řešení původního problému
Příklady
• Mergesort
• Quicksort
Master theorem
Master theorem je nástroj pro určování složitosti algoritmů
založených na přístupu rozděl a panuj. Pokud je velikost
podproblémů shodná, lze využít následujícího vztahu:
T(n) = aT(n/b) + O(nd
)
• T(n) – počet kroků nutných pro vyřešení problému o velikosti n
• a – počet podproblémů
• b – faktor určující velikost podproblémů
• d – množství práce nutné ke sloučení řešení jednotlivých
podproblémů
T(n) =



O(nd) pro d > logb a
O(nd log n) pro d = logb a
O(nlogb a) pro d < logb a
Master theorem – Mergesort
Složitost Mergestortu. Každé pole je rozděleno na dvě části
o poloviční velikosti (a = b = 2), slévání seřazených podposloupností
je lineární operace (d = 1). Platí d = logb a → T(n) = O(nd log n).
T(n) = 2T(n/2) + O(n) → T(n) = O(n log n)
Násobení matic
Úkol. Popište algoritmus pro násobení dvou matic (Z = XY)
o rozměrech n × n.
Naivní násobení matic představuje učebnicový způsob řešení se
složitostí O(n3).
∀(i, j) ∈ {1..n} × {1..n} : Zi,j =
n∑
k=1
Xi,kYk,j
Blokové násobení matic je přístup, kdy každou z matic rozdělíme na
menší a násobíme dle následujícího schématu:
X =
(
A B
C D
)
Y =
(
E F
G H
)
Z = XY =
(
A B
C D
)
·
(
E F
G H
)
=
(
AE + BG AF + BH
CE + DG CF + DH
)
Násobení matic
Složitost blokového násobení matic je však zřejmě stále shodná
s naivním přístupem, tedy O(n3).
Poznámka. V reálném běhu je dekompozice na bloky výrazně
rychlejší řešení díky lepšímu využití vyrovnávací paměti.
Rekurzivní algoritmus násobení matic
Z = XY =
(
A B
C D
)
·
(
E F
G H
)
=
(
AE + BG AF + BH
CE + DG CF + DH
)
• aplikujme stejný (D & C) přístup pro výpočet součinů AE, BG, . . .
• aplikací MT získáváme
T(n) = 8T(n/2) + O(n2
) → T(n) = O(n3
)
Strassenův algoritmus
Myšlenka. Využijeme rekurzivní algoritmus pro násobení matic,
avšak pomocí algebraických transformací snížíme počet nutných
násobení. Počet sčítání není příliš významný.
P1 = A(F − H)
P2 = (A + B)H
P3 = (C + D)E
P4 = D(G − E)
P5 = (A + D)(E + H)
P6 = (B − D)(G + H)
P7 = (A − C)(E + F)
Z = XY =
(
P5 + P4 − P2 + P6 P1 + P2
P3 + P4 P1 + P5 − P3 − P7
)
Složitost Strassenova algoritmu
T(n) = 7T(n/2) + O(n2
) → T(n) = O(nlog2 7
) ≈ O(n2,81
)
Hladové algoritmy
Hladový algoritmus (greedy algorithm) v každém kroce výpočtu
výbírá aktuálně nejlepší možnost, přičemž spoléhá, že tato
posloupnost voleb vede ke globálně nejlepšímu řešení.
Vlastnosti
• ne vždy lze s úspěchem použít – pouze některé problémy mají
tuto strukturu
• časově efektivní
Příklady
• Kruskalův a Primův algoritmus
• Dijkstrův algoritmus
Minimální počet mincí
Problém. Vyplaťte zadanou částku pomocí minimálního počtu mincí.
Příklad. Částka 79, hodnoty mincí 1, 2, 5, 10,…
• hladový přístup – volím vždy minci nejvyšší hodnoty menší než
zbývající částka
• 79 = 50 + 20 + 5 + 2 + 2
Příklad. Částka 6, hodnoty mincí 1, 3 a 4.
• hladový přístup – 6 = 4 + 1 + 1
• optimální řešení – 6 = 3 + 3
Příklad. Částka 14, hodnoty mincí 3, 7 a 10.
• optimální řešení – 14 = 7 + 7
• hladový přístup – 14 = 10 + ?