4. diel - Backtracking - Úvod
V predchádzajúcom článku, Stromová rekurzia – Všeobecné stromy , sme sa naučili písať metódy, v ktorých schéma rekurzívnych volaní tvoria všeobecné stromy.
V dnešnom tutoriále o rekurzívnych algoritmoch si vysvetlíme pojmy k backtrackingu a algoritmom na prehľadávanie stavového priestoru.
Tiež sa začneme zaoberať tým, ako prakticky využiť znalosti, ktoré sme získali v predchádzajúcich lekciách. Zatiaľ sme sa naučili, ako využiť rekurziu na vygenerovanie všetkých možností pri riešení nejakej úlohy. To sa niekedy hodí samo o sebe, v praxi ale často nechceme generovať všetky možnosti, ale zaujíma nás nejaká jedna konkrétna, ku ktorej sa chceme dobrať.
Stavový priestor
Pojmom stavový priestor označujeme všetky možné stavy nejakého procesu, problému alebo deja. Veľmi jednoduchým príkladom je semafor, ktorého kompletný stavový priestor obsahuje štyri stavy, ktoré sú na nasledujúcom obrázku:
Naopak veľmi komplikovaným stavovým priestorom sa môže pochváliť napr. hra šach. Jej stavový priestor obsahuje všetky možné varianty rozostavenia figúr, ktoré môžu počas hry na šachovnici nastať. Variant, ktorý vidíme na obrázku, nastal počas legendárnej hry Garryho Kasparova s počítačom Deep Blue:
...koniec náhľadu článku...
Pokračuj ďalej
Minul si až sem a to je super! Veríme, že ti prvé lekcie ukázali niečo nového a užitočného.
Chceš v kurze pokračovať? Prejdi do prémiové sekcie.
Kúpiť tento kurz
Obsah článku spadá pod licenciu Premium, kúpou článku súhlasíš so zmluvnými podmienkami.
- Neobmedzený a trvalý prístup k jednotlivým lekciím.
- Kvalitné znalosti v oblasti IT.
- Zručnosti, ktoré ti pomôžu získať vysnívanú a dobre platenú prácu.
Popis článku
Požadovaný článok má nasledujúci obsah:
V tutoriále o rekurzívnych algoritmoch si vysvetlíme pojmy na backtracking a algoritmy na prehľadávanie stavového priestoru.
Kredity získaš, keď podporíš našu sieť. To môžeš urobiť buď zaslaním symbolickej sumy na podporu prevádzky alebo pridaním obsahu na sieť.
