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