Fie problema P, care poate fi rezolvata, in principiu, pe mai multe
cai. Fie P1, P2, ..., Pn subproblemele
corespunzatoare fiecareia din aceste cai. Important este ca, pentru a obtine
solutia problemei P este suficient sa se rezolve numai una din subproblemele
P1, P2, ..., Pn, dar nu se stie dinainte
care din ele.
Trebuie, deci, sa se ia o decizie, pe care din aceste cai sa se mearga,
fara ca in momentul luarii deciziei sa existe informatia necesara in acest
scop. In consecinta, problema este nedeterminista.
Cazul determinist este cel al structurii de decizie
if <conditie> then <actiune 1> else <actiune 2> in care se considera ca expresia <conditie> poate fi evaluata inainte de a se executa actiunea 1 sau 2. In cazul nedeterminist discutat aici, se considera ca la luarea deciziei nu exista informatia necesara pentru a determina cu siguranta pe ce cale trebuie sa se continuie executarea programului. |
Aplicand tehnica backtracking, rezolvarea problemei P mentionate mai sus se face astfel:
In fisierul Backtracking.java este
definita clasa abstracta Backtracking, care ofera o implementare
a algoritmului cu acelasi nume descris mai sus. Ca stiva se foloseste o
instanta a clasei ArrayList. Ca varf al stivei se foloseste ultimul element
al listei. Avantajul folosirii drept stiva a unei liste este ca aceasta
poate fi examinata la validarea succesorilor. Elementele stivei sunt instante
ale clasei interioare ElemStiva si contin doua campuri:
Object element - contine elementul de informatie (succesorul elementului precedent din stiva) pus in varful stivei; Object ultimSuccesorVizitat - contine o referinta la ultimul succesor al acestui element care a fost deja vizitat. Cand elementul se pune prima data in stiva, aceasta referinta este nula. Algoritmul foloseste urmatoarele metode abstracte:
Aceste metode abstracte trebuie definite in clasele derivate, corespunzator cu problema rezolvata. Algoritmul de backtracking este realizat aici prin doua metode: protected Object succesorValid() - cauta un succesor valid al elementului din varful stivei, care sa urmeze ultimului succesor deja vizitat, si intoarce acest succesor, aplicand algoritmul de backtracking. Daca nu exista succesor valid al elementului din varful stivei, acest element este eliminat din stiva si se continua cautarea succesorului pentru elementul precedent al stivei; cautarea se opreste cand se gaseste un succesor valid, sau cand stiva devine goala. In ultimul caz, metoda intoarce null. Aceasta metoda foloseste metodele succesor si esteValid pentru a obtine un nou succesor al starii curente si pentru a verifica daca acest succesor este valid. Remarcam ca metoda succesorValid actioneaza ca un iterator: la fiecare invocare ea intoarce un nou succesor valid, care poate fi pus in stiva. Este folosita numai in subclase. public Object solutiaUrmatoare() - itereaza succesorii valizi pana cand se ajunge in situatia ca stiva contine o solutie si intoarce aceasta solutie. Pentru a verifica daca stiva contine o solutie si a construi aceasta solutie se foloseste metoda solutie. Metoda actioneaza, deci, ca un iterator de solutii. Este singurul iterator public. Pentru a elabora o clasa care rezolva o problema concreta prin metoda backtracking, programatorul creeaza o clasa derivata din cea descrisa aici, in care: * exista un constructor care initializeaza stiva folosita
in clasa abstracta Backtracking; in constructor se pot initializa si eventuale
campuri de date specifice continute in clasa derivata;
|