C2142 Návrh algoritmů pro přírodovědce
10. Přístupy k řešení problémů I.
Tomáš Raček
Jaro 2019
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 + ?