C2142 Návrh algoritmů pro přírodovědce
11. Přístupy k řešení problémů II.
Tomáš Raček
Jaro 2015
Sudoku
Úkol. Vyřešte následující zadání Sudoku.
Zamyšlení. Řešení je poměrně snadné pro člověka, ale jak jej
algoritmizovat?
Backtracking
Backtracking je rekurzivní přístup, v rámci něhož hledám řešení
následujícím způsobem:
1. Zkontroluji, zdali jsem nalezl řešení.
2. Pokud ne, zkusím pokračovat v hledání některou z možností,
kterou v danou chvíli mám a ještě jsem nevyzkoušel.
3. Pokud žádné možnosti nezbývají, vracím se do posledního
místa, kde jsem měl ještě na výběr.
Vlastnosti:
• garance nalezení nejlepšího/všech řešení
• potenciálně vysoká složitost
Známé příklady:
• DFS
• minimální počet mincí
Sudoku – jednoduché řešení
1. Pokud jsou obsazena všechna pole, vracím TRUE.
2. Najdu první prázdné pole.
3. Pro všechny přípustné číslice pro toto pole:
3.1 Zapíšu zvolenou číslici.
3.2 Celý algoritmus rekurzivně opakuji.
3.3 Pokud je výsledkem rekurzivního volání TRUE, vracím jej,
v opačném případě zkouším další číslici.
4. Všechny možnosti pro dané pole jsou neúspěšně vyčerpány,
vracím FALSE.
Zamyšlení. Uvedený postup lze vylepšit, pokud budou volná pole
vybírána v pořadí podle počtu možných číslic (od nejmenšího).
Branch and bound
Branch and bound je jednoduché vylepšení backtrackingu pro
optimalizační problémy, kdy si během výpočtu pamatuju aktuálně
nejlepší nalezené řešení (resp. jeho cenu).
• eliminuji cesty, které už nemohou vést k lepšímu řešení (= jejich
ohodnocení je větší než ohodnocení aktuálně nejlepšího
nalezeného řešení)
Vlastnosti:
• vede k omezení větvení → „prořezávání větví“
• nezaručuje, že se vyhneme exponenciální složitosti
• užitečné, pokud brzy najdeme dobré řešení
Branch and bound – příklad
Ukázka. Po nalezení řešení s ohodnocením 4 neprohledávám dále
neperspektivní cesty.
4
1 6 3
Dynamické programování
Dynamické programování je metoda podobná rozděj a panuj
použitelná pro optimalizační úlohy.
Princip
1. Rozděl problém na menší podproblémy.
• stejného typu
• musí se překrývat (optimální řešení problému v sobě zahrnuje
optimální řešení podproblému)
2. Vyřeš jednotlivé podproblémy v pořadí od nejmenších.
3. Zkombinuj řešení podproblémů na řešení původního problému.
Příklady
• Dijkstrův algoritmus
• Floyd-Warshallův algoritmus
Minimální počet mincí
Opakování. Pro správně zvolené hodnoty mincí je hladový přístup
optimální. V některých případech však nenalezne (nejlepší) řešení.
Optimální řešení lze nalézt pomocí dynamického programování.
• označme C[j] minimální počet mincí na zaplacení částky j
• pokud známe optimální řešení pro C[j] a použili jsme minci
hodnoty hi, pak máme:
C[j] = 1 + C[j − hi]
Příklad. Pokud je C[46] optimální a použili jsme minci hodnoty 20,
pak C[46] = 1 + C[26].
Minimální počet mincí
Zobecnění. Mějme k různých mincí hodnot hi, kde 1 ≤ i ≤ k. Pak
optimální řešení pro částku j je dáno:
C[j] =



∞ pro j < 0
0 pro j = 0
1 + min
1≤i≤k
{
C[j − hi]
}
pro j ≥ 1
Příklad pro částku 6 a hodnoty mincí 1, 3 a 4.
• postupujeme od nejnižších částek až po výslednou dle
předchozího výrazu
• zjevně C[0] = 0
Minimální počet mincí
C[1] = min



1 + C[1 − 4] = ∞
1 + C[1 − 3] = ∞
1 + C[1 − 1] = 1
C[2] = min



1 + C[2 − 4] = ∞
1 + C[2 − 3] = ∞
1 + C[2 − 1] = 2
C[3] = min



1 + C[3 − 4] = ∞
1 + C[3 − 3] = 1
1 + C[3 − 1] = 3
C[4] = min



1 + C[4 − 4] = 1
1 + C[4 − 3] = 2
1 + C[4 − 1] = 2
C[5] = min



1 + C[5 − 4] = 2
1 + C[5 − 3] = 3
1 + C[5 − 1] = 2
C[6] = min



1 + C[6 − 4] = 3
1 + C[6 − 3] = 2
1 + C[6 − 1] = 3
Optimální pořadí násobení matic
Problém. Chceme vynásobit A1 · · · An s nejmenším počtem operací.
Pozorování
• násobení matic je asociativní, tj. A(BC) = (AB)C
• vhodným uzávorkováním lze snížit množství nutných operací
Příklad s maticemi A10×30, B30×5, C5×60:
• (A10×30 · B30×5) · C5×60 = X10×5 · C5×60
• 10 · 30 · 5 + 10 · 5 · 60 = 4 500 operací
• A10×30 · (B30×5 · C5×60) = A10×30 · X30×60
• 30 · 5 · 60 + 10 · 30 · 60 = 27 000 operací
Závěr. Složitost řešení pomocí přístupu rozděl a panuj je O(3n),
užitím dynamického programování pak O(n3).
Heuristiky
Pozorování. Některé instance problémů mohou být z hlediska
složitosti exaktně velmi těžko řešitelné.
Myšlenka
• suboptimální řešení lze nalézt často výrazně rychleji
• často není potřeba určit všechna řešení
• heuristika – forma odhadu jak vypadá/co obsahuje řešení (př.
v 95 % případů platí…)
Příklad. Určete nejkratší vzdálenost mezi vrcholy s a t v grafu G.
• pro výpočet uvažujeme pouze hrany s ohodnocením ≤ k
• zřejmě nemusí vést k (nejlepšímu) řešení
Redukce
Redukce je metoda převodu jednoho problému na jiný. Využívá se
zejména v rámci teoretického porovnávání složitosti algoritmů.
Princip
1. Zadání problému A transformuji na zadání pro problém B.
2. Vyřeším zadání problému B.
3. Řešení problému B převedu zpátky na řešení původního
problému A.
Příklad. Nejkratší vzdálenost v neohodnoceném grafu.
• lze převést na nejkratší vzdálenost v ohodnoceném grafu
• ∀(u, v) ∈ E : we(u, v) = 1
• nejkratší cesta je v novém i původním grafu stejná