Lekce 5 - Backtracking - Prořezávání
V předchozí lekci, Backtracking - Úvod, jsme si vysvětlili základní pojmy týkající se backtrackingu a prohledávání stavového prostoru.
V dnešním tutoriálu o rekurzivních algoritmech si vysvětlíme techniku prořezávání, která umožňuje zásadně snížit časové nároky rekurzivních algoritmů.
Motivace
Jak už víme, úlohy řešené pomocí backtrackingu bývají obvykle extrémně časově náročné. Stavové prostory reálných problémů jsou velice rozsáhlé a prohledat je trvá velmi dlouho. V dnešním tutoriálu si představíme prořezávání, což je jedna z technik, kterými lze časové nároky algoritmu dramaticky snížit. Princip prořezávání si pak předvedeme na velmi známém problému – ukážeme si, jak nám umožní naprogramovat luštič Sudoku.
Princip prořezávání
Jak jsme si ukázali v kapitole Backtracking lekce Backtracking - Úvod, backtracking spočívá v postupném prohledávání stromu stavového prostoru tak, že vždy postupujeme směrem dolů k listům. Opět si vše nejlépe ukážeme na obrázku. Představme si, že jsme právě v kořeni stromu (zelený uzel) a chystáme se prozkoumat jeho pravý podstrom, jehož vrchol je označen červeně:
Pokud do podstromu vstoupíme, čeká nás hodně práce. Budeme muset prozkoumat všechny jeho uzly označené oranžovou barvou. Základní otázkou, kterou bychom si v tuto chvíli měli položit, je, zda všechnu tuto práci opravdu musíme vykonat!
Detekce slepých uliček
V mnoha případech lze totiž už v tuto chvíli určit, že ani jedna z cest v daném podstromu nemůže vést k nalezení řešení. Obvykle proto, že jsme v červeném uzlu porušili nějakou základní podmínku nutnou k nalezení řešení. Toto porušení se dále propaguje do všech uzlů potomků. Pokud toto zjistíme, do podstromu vůbec nevstoupíme (takzvaně ho odřízneme):
...konec náhledu článku...
Pokračuj dál
Došel jsi až sem a to je super! Věříme, že ti první lekce ukázaly něco nového a užitečného.
Chceš v kurzu pokračovat? Přejdi do prémiové sekce.
Koupit tento kurz
Před koupí tohoto článku je třeba koupit předchozí díl
Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.
- Neomezený a trvalý přístup k jednotlivým lekcím.
- Kvalitní znalosti v oblasti IT.
- Dovednosti, které ti pomohou získat vysněnou a dobře placenou práci.
Popis článku
Požadovaný článek má následující obsah:
V tutoriálu o rekurzivních algoritmech si vysvětlíme techniku prořezávání, která umožňuje zásadně snížit časové nároky rekurzivních algoritmů.
Kredity získáš, když podpoříš naši síť. To můžeš udělat buď zasláním symbolické částky na podporu provozu nebo přidáním obsahu na síť.
