5. diel - Backtracking - Prerezávanie
V predchádzajúcej lekcii, Backtracking - Úvod , sme si vysvetlili základné pojmy týkajúce sa backtrackingu a prehľadávania stavového priestoru.
V dnešnom tutoriále o rekurzívnych algoritmoch si vysvetlíme techniku prerezávania, ktorá umožňuje zásadne znížiť časové nároky rekurzívnych algoritmov.
Motivácia
Ako už vieme, úlohy riešené pomocou backtrackingu bývajú obvykle extrémne časovo náročné. Stavové priestory reálnych problémov sú veľmi rozsiahle a prehľadať ich trvá veľmi dlho. V dnešnom tutoriále si predstavíme prerezávanie, čo je jedna z techník, ktorými možno časové nároky algoritmu dramaticky znížiť. Princíp prerezávania si potom predvedieme na veľmi známom probléme – ukážeme si, ako nám umožní naprogramovať lúštič Sudoku.
Princíp prerezávania
Ako sme si ukázali v kapitole Backtracking lekcie Backtracking - Úvod, backtracking spočíva v postupnom prehľadávaní stromu stavového priestoru tak, že vždy postupujeme smerom dole k listom. Opäť si všetko najlepšie ukážeme na obrázku. Predstavme si, že sme práve v koreni stromu (zelený uzol) a chystáme sa preskúmať jeho pravý podstrom, ktorého vrchol je označený červenou farbou:
Pokiaľ do podstromu vstúpime, čaká nás veľa práce. Budeme musieť preskúmať všetky jeho uzly označené oranžovou farbou. Základnou otázkou, ktorú by sme si v tejto chvíli mali položiť, je, či všetku túto prácu naozaj musíme vykonať!
Detekcia slepých uličiek
V mnohých prípadoch možno totiž už v tejto chvíli určiť, že ani jedna z ciest v danom podstrome nemôže viesť k nájdeniu riešenia. Zvyčajne preto, že sme v červenom uzle porušili nejakú základnú podmienku potrebnú na nájdenie riešenia. Toto porušenie sa ďalej propaguje do všetkých uzlov potomkov. Pokiaľ toto zistíme, do podstromu vôbec nevstúpime (takzvane ho odrežeme):
...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
Pred kúpou tohto článku je potrebné kúpiť predchádzajúci diel
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 techniku prerezávania, ktorá umožňuje zásadne znížiť časové nároky rekurzívnych algoritmov.
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ť.
