Definícia

Jeden zo spôsobov hľadania riešenia pre všeobecné problémy je metóda pokusov a omylov. Celý proces sa rozkladá na niekoľko čiastkových úloh, ktoré sa často vyjadrujú pomocou rekurzie a spočívajú v preskúmaní konečného počtu podúloh. Opakovaním pokusov (vyhľadávaní) sa postupne vybuduje a skúma (zmenšuje) strom podúloh.

Takéto algoritmické problémy sa dajú vyriešiť pomocou prehľadávania s návratom. Algoritmus funguje tak, že sa zoberú do úvahy všetky možnosti, ktoré môžu viesť k vyriešeniu problému. Potom sa postupne rekurzívne riešia jednotlivé podproblémy. Množina rekurzívnych volaní vytvára stromovú štruktúru, kde je postupne kontrolovaná každá podmnožina možností. Z toho vyplýva, že ak riešenie existuje, algoritmus ho určite časom nájde.

^ TOP

Vlastnosti

Backtracking je vo všeobecnosti neefektívny prístup, používajúci brute-force prístup. Pomocou rôznych optimalizačných techník sa dá zredukovať hĺbka stromu a aj počet podstromov. Technika sa volá prehľadávanie s návratom, pretože po každom navštívenom liste stromu sa algoritmus vráti do zásobníka. Tam má uložené miesta, odkiaľ sa vnoril. Vyberie ďalšiu vetvu a znova sa vnorí. Aby sa problém dal riešiť pomocou prehľadávania s návratom, jeho podproblémy sa musia určitým spôsobom podobať na pôvodný problém. Väčšina problémov sa dá na takýto tvar upraviť.

^ TOP

Použitie

Problém ôsmych dám

Je potrebné rozmiestniť osem dám na šachovnici tak, aby žiadna z nich neohrozovala niektorú z ostatných figúrok.

    procedure vyskusaj(tah:...);
    begin
      zapis_tah_do_sachovnice;
      if koniec then
        vypis
      else
        // vyskúšaj nasledujúci ťah – všetky možnosti
        vyskusaj(nasledujúci_ťah);
      vymaz_tah_zo_sachovnice;
    end;      
      

Problém šiestich tiav

Šesť tiav pôjde v karaváne 6 dní. Vedecky sa ukázalo, že ak ťava pozerá na dopravnú značku celý deň, tak sa ju naučí, preto namaľovali na zadky tiav 6 rôznych značiek. Úloha je navrhnúť rozloženie tiav do 6 karaván (pre každý deň iné) tak, aby sa každá naučila 5 rôznych značiek. Každý deň je jedna ťava vedúca a tá sa nič neučí.

Problém stabilného manželstva

Existuje množina A mužov a množina B žien. Každý muž a každá žena si stanovili rôzne požiadavky na svojich partnerov. Keď sa vyberie n takých dvojíc, v ktorých muž a žena nie sú spolu zosobášení, ale obaja by dali prednosť svojmu vybratému partnerovi pred svojím skutočným manželským partnerom, tak takéto priradenie partnerov sa volá nestabilné. Ak takéto dvojice neexistujú, hovoríme o stabilnom zväzku.