Metoda backtracking

Metoda backtracking se aplica problemelor in care solutia se poate prezenta sub forma unui vector x={x1,x2,…,xn} unde x1 apartine unei multimi S1, x2 apartine multimii S2 s.a.m.d.Si i=1…n sunt multimi finite. Cerinta problemei este, de obicei, gasirea tuturor solutiilor posibile sau gasirea numarului de solutii care satisfac anumite conditii specifice problemei. De multe ori metoda se foloseste si pentru gasirea unei singure solutii (dupa gasirea acesteia se intrerupe executia programului), a unei solutii maxime/minime insa, pentru astfel de cazuri recomandam gasirea unei alte solutii de rezolvare datorita faptului ca metoda Backtracking consuma resurse mari de memorie si timp.

Conditiile interne, numite si conditii de continuitate, sunt acele conditii care trebuie indeplinite de un element pentru a fi adaugat la solutie. Validitatea elementului se verifica in functie de elementele aflate in fata lui in vectorul solutie (vectorul x).

                Metoda evita generarea tuturor solutiilor posibile. Se va cauta obtinerea unei solutii prin alegerea succesiva de elemente din multimile S1, S2, S3,…,Sn. Astfel, la pasul k, se va alege un element xk din multimea Sk.  Inainte de a trece la pasul k+1, se verifica daca sunt satisfacute conditiile de continuitate. In cazul in care pentru o valoare xk aleasa, conditiile de continuare nu sunt satisfacute, se va alege o alta valoare din multimea Sk, pana cand fie se va gasi o valoare care sa satisfaca conditiile de continuitate, fie se epuizeaza toate elementele multimii Sk. In cazul in care se gaseşte un element xk convenabil avem doua cazuri: fie s-a ajuns la obtinerea unei solutii caz in care se afiseaza solutia, fie nu s-a ajuns la o solutie caz in care se trece la gasirea urmatorului element din vectorul solutie (cel de pe pozitia k+1). Exista şi cazul in care pozitia k din vectorul solutie nu s-a putut completa cu un element xk din Sk, adica nu s-a gasit un element care sa indeplineasca conditiile de continuitate. In acest caz se va reveni la pasul anterior (k-1). Se va renunta la valoarea x(k-1) aleasa şi se va cauta alegerea unei alte valori (urmatoarea valoare din multimea k-1).

                Ca orice algoritm in care sunt prezente instructiuni repetitive, algoritmul backtracking poate fi reprezentat intr-o maniera recursiva sau nerecursiva. Vom opta pentru varinata nerecursiva.

Algoritmul pentru metoda Backtracking

Subprgram back;

k=1;

x[k]=minimul elementelor din Ak-1

cat timp k>0 executa   {cat timp nu s-au generat toate solutiile}

{

  valid=false; {valoarea x[k] nu este buna}

  cat timp (valid=false si x[k]<maximul elementelor din Ak) {cat timp x[k] nu este bun si mai sunt elemente x[k] netestate in Ak}

      x[k]=x[k]+1; {alegem urmatorul element din multimea Ak}

     Posibil(k,valid); {verificam daca x[k] indeplineste conditiile de continuitate pentru a-l adauga la solutie}

Sfarsit cat timp

  Daca valid=false

atunci k=k-1 {daca nu s-au gasit elemente x[k] in Ak care sa indeplineasca conditiile de continuitate}

               Altfel

                     Daca solutie(k) atunci scrie(k) {daca s-a ajuns la o solutie cu k elemente le afisam}

                                               Altfel {trecem la initializarea urmatorului element in vectorul solutie}

                                                    k=k+1;

                                                    x[k]=minimul elementelor din Ak;

                                Sfarsit daca

  Sfarsit daca

Sfarsit cat timp

Sfarsit subprogram back

Subprogram posibil(k, var valid) {k-parametru de intrare – pozitia elementului curent in vectorul solutie; valid – paramentru de iesire. Are valoarea false daca x[k] nu poate face parte din solutie si true daca poate face parte din solutie}

valid=true; {presupunem ca x[k] indeplineste conditiile de continuitate pentru a face parte din solutie}

{Verificam daca x[k] nu indeplineste conditiile de continuite => valid=false}

Subprogram solutie(k) : boolean

{Verificam daca cele k elemente indeplinesc conditiile pentru ca x sa fie solutie. Valoarea returnata de functie este de tip boolaean (true/false in Pascal, 0/1 in C++, True/False in C#)}

Subprogram scrie(k)

{afisam vectorul solutie cu k elemente}