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:
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
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
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 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íť.
