Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

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ě:

strom stavového prostoru

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

Znalosti v hodnotě stovek tisíc získáš za pár korun

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

Koupit všechny aktuálně dostupné lekce s funkcí odevzdávání úloh za pouhých 200 Kč
Aktuální stav konta 0 Kč
Koupí tohoto balíčku získáš přístup ke všem 10 článkům (10 lekcí) tohoto kurzu.

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.

Co od nás v dalších lekcích dostaneš?
  • 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íť.

Článek pro vás napsal Jan Hnilica
Avatar
Autor se věnuje hlavně programování v C a v Pythonu
Aktivity