Fie problema P, care poate fi rezolvată, în principiu, pe mai multe
căi. Fie P1, P2, ..., Pn subproblemele
corespunzătoare fiecăreia din aceste căi. Important este că, pentru a
obține soluția problemei P este suficient să se rezolve numai una
din subproblemele P1, P2, ..., Pn, dar nu
se știe dinainte care din ele.
Trebuie, deci, să se ia o decizie, pe care din aceste căi să se meargă, fără
ca în momentul luării deciziei să existe informația necesară în acest
scop. În consecință, problema este nedeterministă.
Cazul determinist este cel al structurii de
decizie if <condiție> then <acțiune 1> else <acțiune 2> în care se consideră ca expresia <condiție> poate fi evaluată înainte de a se executa acțiunea 1 sau 2. În cazul nedeterminist discutat aici, se consideră că la luarea deciziei nu există informația necesară pentru a determina cu siguranță pe ce cale trebuie să se continuie executarea programului. Remarcăm că, în cazul problemelor deterministe soluția este unică, în timp ce problemele nedeterministe pot avea mai multe soluții, sau niciuna. |
Aplicând tehnica backtracking, rezolvarea problemei P menționate mai sus se face astfel:
Tehnica backtracking poate fi privită și ca o tehnică de
căutare în spațiul stărilor. Numim stare a sistemului ansamblul
valorilor tuturor variabilelor sistemului la un moment dat. La
efectuarea fiecărei operații are loc o modificare a stării sistemului.
În consecință, putem să ne imaginam un graf orientat al stărilor, în
care fiecare vârf este o stare, iar fiecare arc este o operație.
Este evident că acest graf nu este el însuși o structură de date din memoria calculatorului, ci doar o reprezentare abstractă. În majoritatea cazurilor, la executarea programului nu se vor parcurge toate vârfurile acestui graf (toate stările posibile), ci numai unele dintre ele. La executarea programului se parcurge numai o singură cale în acest graf al stărilor, depinzând de datele de intrare. |
La aplicarea tehnicii backtracking, se consideră că problema care se rezolvă este de așa natură, încât nu este posibil să se ajungă în aceeași stare pe două căi diferite. Se consideră, deci, că spațiul stărilor are o structură arborescentă (întrucât nici un nod al arborelui nu poate avea doi părinți). Implicit, aceasta înseamnă că la executarea programului nu pot exista cicluri. În plus, se consideră că înălțimea acestui arbore al stărilor este finită. Aceasta înseamnă că, la parcurgerea în adâncime, după un anumit număr de pași (posibil mare), se va ajunge la o stare fără succesor (la o "frunză" a arborelui stărilor), ceeace face posibil ca, dacă nu s-a găsit soluția, să se revină la o stare anterioară și să se continue căutarea pe altă cale. Dacă înălțimea arborelui ar fi infinită, s-ar merge mereu în adâncime pe o singură cale, iar revenirea nu ar mai fi posibilă.
Având în vedere cele expuse mai sus, la fel ca la parcurgerea
arborilor în adâncime, pentru realizarea căutării cu revenire
(backtracking) se folosește o stivă. În fiecare punct de ramificație
(din care pornesc mai multe căi posibile), starea curentă se pune în
stivă pentru a se putea reveni la ea ulterior, dacă pe calea aleasă nu
s-a gasit soluția sau dacă se caută și alte soluții.
În fișierul Backtracking.java
este definită clasa abstractă Backtracking, care oferă o
implementare a algoritmului cu același nume descris mai sus. Ca stivă se
folosește o instanță a clasei ArrayList. Ca vârf al stivei se folosește
ultimul element al listei. Avantajul folosirii drept stivă a unei liste
este că aceasta poate fi examinată la validarea succesorilor.
Elementele stivei sunt instanțe ale clasei interioare ElemStiva și
conțin două câmpuri: Object element - conține elementul de informație (succesorul elementului precedent din stivă) pus în vârful stivei; Object ultimSuccesorVizitat - conține o referință la ultimul succesor al acestui element care a fost deja vizitat. Când elementul se pune prima data în stivă, aceasta referință este nulă. Algoritmul folosește următoarele metode abstracte: Aceste metode abstracte trebuie definite în clasele derivate,
corespunzător cu problema rezolvată. Algoritmul de backtracking este
realizat aici prin următoarele două metode: public Object solutiaUrmatoare() - iterează succesorii valizi pană când se ajunge în situaîia ca stiva conține o soluție și întoarce această soluție. Pentru a verifica dacă stiva conține o soluție și a construi această soluție, se folosește metoda solutie. Metoda actionează, deci, ca un iterator de soluții. Este singurul iterator public. Pentru a elabora o clasă care rezolvă o problemă concretă prin metoda backtracking, programatorul creeaza o clasă derivată din cea descrisa aici, în care: * există un constructor care inițializeaza stiva folosită
în clasa abstractă Backtracking; în constructor se pot inițializa și
eventuale câmpuri de date specifice conținute în clasa derivată; |