Bektreking

Bektreking (engl. Backtracking) algoritam ili metod obrnute pretrage predstalja pristup grube sile u traženju rešenja gde se isprobavaju sve moguće kombinacije. Postepeno se grade kandidati za rešenje a odbacuju se svi kandidati za koje se ispostavi da ne vode do tačnog rešenja. Zbog složenosti nekih problema, algoritam se često sporo izvršava pa se koriste algoritmi prolagođeniji za dati problem, osim ako za problem postoji dobra heuristika (intuitivnan način nalaženja koji često daje samo približno rešenje). Algoritam prolazeći kroz sve moguće situacije daje prvo rešenje, sva moguća rešenja, pa i samim tim i optimalno rešenje.

Klasični primer korišćenja bektrekinga je problem osam dama, kod ovog problema traga se za rasporedom osam dama na standardnoj šahovskoj tabli, tako da nijedna dama ne napada bilo koju drugu. Pri rešavanju problema koristi se bektreking pristup da su parcijalni kandidati za rešenja svi rasporedi kod kojih je k dama postavljeno u prvih k redova na tabli, a svih k u različitim redovima i kolonama. Bilo koje ovako generisano rešenje koje sadrži dve dame koje se međusobno napadaju bivaju izostavljena, budući da ne mogu biti deo konačnog rešenja.

Bektreking može biti od koristi samo u problemima kod kojih možemo primeniti koncept "odabira odgovarajućih kandidata" i kod kojih relativno brzo možemo ispitati da li određen kandidat može biti validni deo rešenja. Kada je primenljiv bektreking je često mnogo brži od klasičnog nabrajanja rešenja grubom silom, najčešće zbog toga što eliminiše veliki broj kandidata u svakom koraku.

Bektreking je važna tehnika za rešavanje problema zadovoljivosti, i slagalica kao što su ukrštene reči, sudoku, i mnoge druge. Često ova strategija je najzgodnija pri parsiranju teksta (ponekad i najefikasnija), kao i pri rešavanju problema ranca i kombinatornim optimizacijama nekih problema. Takođe bektreking je baza za takozvane logičke programske jezike kao što su ajkon, planer i prolog.

Bektreking zavisi od funcija koje su tipa "crne kutije" koje definišu problem koji treba rešiti, prirodu kandidata koje uzimamo u obzir, i to kako ovi kandidati postaju deo rešenja. Važno je napomenuti da je bektreking više heuristika nego tačno određeni algoritam, ipak, za razliku od ostalih heuristika, on garantuje pronalaženje svih rešenja za neki konačan problem, u određenom vremenskom roku.

Termin "bektreking" uveo je američki matematičar D. H. Lemer 50-ih godina 20. veka. Jedan od pionira jezika za obradu nizova karaktera SNOBOL (iz 1962. godine) bio je prvi koji je primenio ugrađene mehanizme zasnovane na bektrekingu.

Opis metoda uredi

Bektreking algoritmi generišu skup parcijalnih kandidata, koji mogu biti kompletirani na različite načine tako da dobijemo sva moguća rešenja datog problema. Kompletiranje rešenja se vrši postepeno, kroz niz koraka proširenja.

Konceptualno, parcijalni kandidati su čvorovi drvoidne strukture koja se naziva "stablo pretrage potencijalnih kandidata“. Svaki parcijalni kandidat je roditelj svih kandidata koji proizilaze iz njega upotrebom jednog koraka proširenja; listovi su oni čvorovi, koji predstavljaju kandidate koji se više ne mogu proširiti.

Bektreking algoritmi prelaze stablo rekurzivno, od korena ka listovima. Za svaki čvor, algoritam proverava može li on biti deo validnog rešenja, ukoliko ne celo podstablo počevši od ovog čvora se preskače (odseca). U suprotnom algoritam proverava da li je sam čvor celokupno rešenje, i ukoliko jeste javlja se korisniku, i štampaju se svi njegovi potomci rekurzivno. Ova dva upita kao i potomci svakog čvora se definišu od strane korisnika. Tako da je stvarno drvo pretrage koje se koristi prilikom izvršavanja algoritma u stvari samo deo celokupnog stabla pretrage potencijalnih kandidata. Složenost algoritma je broj čvorova koji se ispita pomnožen sa cenom provere i prolaska kroz svaki čvor. Ovo je činjenica koju treba uzeti u obzir prilikom određivanja stabla pretrage i implementacije upita za odsecanje grana.

Pseudokod uredi

Da bi primenili bektreking na određenu klasu problema, moramo obezbediti podatke za problem R koji predstavlja jednu praktičnu instancu problema iz te klase, i procedure: root, reject, accept, first, next, i output. Ove procedure treba da uzimaju vrednosti parametara R i vraćaju sledeće vrednosti:

root(P) - vraća parcijalnog kandidata koji je koren stabla.
reject(P, c) - vraća bulovsku vrednost tačno ukoliko parcijalni kandidat s nije vredan proširenja.
accept(P, c) - vraća tačno ukoliko je kandidat s celokupno rešenje problema R, u suprotnom vraća netačno.
first(P, c) - generiše prvo proširenje kandidata c.
next(P, s) - generiše sledeće proširenje kandidata, posle proširenja s.
output(P, c) - koristi kandidata c kao prikladno rešenje.

Bektreking algoritam se onda svodi na poziv bt(root(P)), gde je bt() sledeća procedura:

procedure bt(c)
   if reject(P,c) then return
   if accept(P,c) then output(P,c)
   s ← first(P,c)
   while s ≠ Λ do
     bt(s)
     s ← next(P,s)

Razmatranja implementacije uredi

Funkcija reject treba da vraća tačno samo ukoliko je sigurno da nijedno proširenje kandidata s nije deo rešenja problema R. Ukoliko funkcija ne može ovo da zaključi treba da vrati vrednost netačno. Ukoliko funkcija nevalidno vrati vrednost tačno to može prouzrokovati da funkcija bt() ispusti neka rešenja. Funkcija može pretpostaviti da funkcija reject(P,t) vraća netačno za svakog predak t kandidata s u stablu.

Sa druge strane efikasnost algoritma zavisi da funkcija reject vraća vrednost tačno za kandidate što bliže korenu. Ukoliko ova funkcija stalno vraća netačno to rešenje bi bilo ekvivalentno upotrebi algoritma grube sile.

Funkcija accept(P,c) treba da vrati vrednost tačno ukoliko je s potpuno rešenje problema R, netačno u suprotnom. Može pretpostaviti da su kandidat s i svi njegovi preci u stablu prošli funkciju reject.

Primetimo da uopšteni pseudokod ne pretpostavlja da su rešenja uvek listovi u stablu pretrage. Drugim rečima potvrđuje da se rešenje za R može dalje proširiti da bi doprineli drugim rešenjima.

Funkcije first i next koriste bektreking algoritme da bi došli do naslednika kandidata s u stablu. Poziv first(P,c) treba da vrati prvog naslednika čvora s, a poziv next(P,s) sledećeg brata čvora s u stablu. Obe funkcije treba da vrate vrednost null, ovde predstavljen kao Λ, ukoliko ovi čvorovi ne postoje.

Funkcije root, first i next zajedno određuju skup parcijalnih kandidata stabla. One se trebaju izabrati tako da se svako rešenje problema nalazi negde u stablu, a da se nijedan kandidat ne pojavi dvaput. Takođe treba obezbediti što efikasniju reject funkciju.

Varijante sa ranim zaustavljanjem uredi

Gore prikazani algoritam možemo modifikovati tako da stane posle pronalaska prvog rešenja, određenog broja rešenja, određenog broja ispitanih kandidata ili utrošenog zadatog procesorskog vremena.

Primeri uredi

Tipični primeri su:

Slagalice kao problem osam dama, sudoku, ukrštene reči, peg soliter.
Kombinatorne optimizacije kao što su parsiranje i problem ranca.
Logički programski jezici koji koriste bektreking da bi generisali odgovore.
Bektreking se takođe primenjuje kod softvera za poređenje verzija za Mediaviki.

Ispod je prikazan problem zadovoljivosti.

Zadovoljivost uredi

Opšti problem zadovoljivosti traga za nizom prirodnih brojeva x = (x[1],x[2], ..., x[n]), iz nekog intervala {1, 2, ..., m}, koji zadovoljavaju proizvoljnu bulovsku funkciju F.

Za ovu klasu problema, instancni podaci R biće m i n i predikat F. U tipičnom bektreking algoritmu definišemo listu parcijalnih kandidata kao listu prirodnih brojeva c = (c[1],c[2], ... c[k]), za bilo koje k između 0 i n, koji će biti dodeljeni prvim k promenljivama x[1],x[2], ..., x[k]. Koren stabla će biti prazan niz. Funkcije first i next će biti:

 function first(P,c)
   k ← length(c)
   if k = n
     then return Λ
     else return (c[1], c[2], ..., c[k], 1)

 function next(P,s)
   k ← length(s)
   if s[k] = m
     then return Λ
     else return (s[1], s[2], ..., s[k-1], 1 + s[k])

Gde je length(c) broj elemenata niza s. Poziv reject(P,c) bi trebalo da vrati tačno ukoliko funkcija F ne može biti zadovoljena bilo kojim nizom od n brojeva koji počinju sa k elemenata iz s. Da bi algoritam bio efikasan mora postojati način da detektujemo ovu situaciju, a bez nabrajanja svih m^n-k n-torki.

Na primer ukoliko je F konjunkcija nekoliko bulovskih promenljivih,F = F[1] $\wedge$ F[2] $\wedge$ $\cdots$ $\wedge$ F[p], i svaki F[i] zavisi samo od malog podskupa promenljivih x[1], ..., x[n], tada bi funkcija reject mogla prosto da proveri terme F[i] koji zavise samo od podskupa x[1], ..., x[k] i vrati tačno ukoliko bilo koji od ovih terma vrate nisu tačni. U stvari reject mora samo da proveri one terme koji zavise od x[k], budući da će termi koji zavise od x[1], ..., x[k-1] biti testirani dalje prilikom izvršavanja algoritma.

Ako pretpostavimo da je funkcija reject implementirana kao gore, onda accept(P,c) jedino treba da proveri da li je s komletan, to jest da li ima n elemenata.

Generalno uvek je bolje prvo sortirati niz kako bi počinjao sa najkritičnijim članovima.

Takođe moguće je dozvoliti funkciji next da odredi promenljivu koje će biti dodeljena prilikom proširenja kandidata, na osnovu vrednosti promenljivih koje su mu dodeljene.

Da bi obezbedili minimalne vrednosti pri povratku bektreking algoritmi koriste "trag promenljive", odnosno pamte poslednje promene podataka. Efikaskom implementacijom može se izbeći kreiranje nepotrebnih tragova kada za to nema potrebe.

Alternativa traga promanljive je korišćenje vremena poslednje promene. Ukoliko je vreme poslednje promene prilikom upita veće nije potrebno menjati vrednost promenljivoj prilikom vraćanja, zbog toga što je ažurirana pre nego što se upit pojavio.

^[1]^[2]^[3]

Vidi još uredi

Pretraga sa nehronološkim vraćanjem

Literatura uredi

Brassard, Gilles; Bratley, Paul (1995). Fundamentals of Algorithmics. Prentice-Hall.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald R.; Stein, Cliff (1990). Introduction to Algorithms. McGraw-Hill.
Gurari, Eitan (1999). „Backtracking algorithms”. CIS 680: DATA STRUCTURES. Arhivirano iz originala 08. 06. 2011. g. Pristupljeno 29. 10. 2012.
Knuth, Donald E. (1968). The Art of Computer Programming. Addison-Wesley.

Spoljašnje veze uredi

HBmeyer.de, Interactive animation of a backtracking algorithm
Sample Java Code, Sample code for backtracking of 8 Queens problem.

[FOOTNOTEKnuth1968-1] Knuth 1968.

[FOOTNOTECormenLeisersonRivestStein1990-2] Cormen et al. 1990.

[FOOTNOTEGurari1999-3] Gurari 1999.

[1]

[2]

[3]