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 4 - Backtracking - Úvod

V předchozím článku, Stromová rekurze – Obecné stromy, jsme se naučili psát metody, ve kterých schéma rekurzivních volání tvoří obecné stromy.

V dnešním tutoriálu o rekurzivních algoritmech si vysvětlíme pojmy týkající se backtrackingu a algoritmů pro prohledávání stavového prostoru. Začneme se tedy zabývat tím, jak lépe prakticky využít znalosti, které jsme získali v předchozích lekcích.

Zatím jsme se naučili, jak využít rekurzi k vygenerování všech možností při řešení nějaké úlohy. To se někdy hodí samo o sobě. V praxi ale často nechceme generovat všechny možnosti, ale zajímá nás nějaká jedna konkrétní, ke které se chceme dobrat.

Backtracking

Backtracking je rekurzivní algoritmus, jehož cílem je nalézt řešení zadané úlohy postupným prohledáváním různých možností. Nejprve si ale pojďme představit potřebné pojmy, abychom vše mohli zasadit do kontextu.

Stavový prostor

Pojmem stavový prostor označujeme všechny možné stavy nějakého procesu, problému nebo děje. Velice jednoduchým příkladem je třeba semafor, jehož kompletní stavový prostor obsahuje čtyři stavy, které jsou na následujícím obrázku:

stavový prostor semaforu

Naopak velmi komplikovaným stavovým prostorem se může pochlubit např. hra šachy. Její stavový prostor obsahuje veškeré možné varianty rozestavení figur, které mohou během hry na šachovnici nastat. Varianta, kterou vidíme na obrázku, nastala během legendární hry Garryho Kasparova s počítačem Deep Blue:


 

...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.

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 pojmy ohledně backtrackingu a algoritmů pro prohledávání stavového prostoru.

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