Metoda Backtracking

Metoda Backtracking 



Metoda Backtracking se aplica in cadrul problemelor in care solutia este de forma X=x1+x2+x3+…+Xn. Tehnica Backtracking propune generarea soluţiilor prin completarea vectorului X in ordinea x1, x2, x3,…,xn . Astfel, daca avem combinaţia parţiala de forma v1, v2 , v3,…,vn-1, ne propunem sa alegem pentru x k o valoare vk astfel încât combinatia rezultata sa ne permită sa ajungem la o soluţie. Daca aceasta nu ne conduce la o soluţie se renunţa la acea valoare si se încearcă alta(dintre cele netestate).

Algoritmul metodei

Pentru evitarea generării combinărilor nefavorabile se procedează astfel: presupunem ca s-au găsit v1, v2, v3,.. vk -1 valori pentru x1, x2, x3,…, xk-1. Ne vom ocupa de xk.  Pas1: Pentru x1 nu s-a testat nici o valoare.  Pas2: Se verifica daca exista valori netestate pentru xk. Daca da, se trece la Pas3 nu, se reia aflarea valorilor pentru xk-1, reluând Pas2.  Pas3: Se alege prima valoare v dintre cele netestate inca pentru xk.  Pas4: Se verifica daca aceasta combinaţie parţiala ne conduce la un rezultat. Daca da, se trece la Pas5 nu, se reia Pas2 pentru k.  Pas5: Se verifica daca s-a obţinut o soluţie. Daca da, se tipareste si se ramane la componenta xk, reluându-se Pas2; nu, se reia algoritmul de la Pas1 pentru k+1.













Algoritmul începe prin stabilirea unei valori pentru componenta x2 si se încheie când pentru x1 am testat toate valorile posibile. Condiţiile interne sunt condiţiile fiecărei probleme in parte dintre componentele vectorului soluţie. Soluţiile rezultat sunt soluţiile posibile ce verifica condiţiile interne. Vectorul soluţie este vectorul ce are atâtea componente cate ne permit generarea unei soluţii. Condiţiile de continuitate sunt condiţiile pentru ca valoarea xk sa fie acceptata.

Metoda Backtracking oferă toate soluţiile.

Procedure BKTR; Begin K:=1; X[k]:=0; While k>0 do if x[k]
Probleme care se rezolva cu ajutorul metodei BKTR:

1. 2. 3. 4. 5. 6. 7. 8. 9.

generarea permutărilor generarea aranjamentelor generarea combinărilor generarea produsului cartezian generarea submulţimilor plata unei sume utilizând n tipuri de bancnote partiţiile unui număr colorarea harţilor problema numerelor

Generarea permutărilor Condiţia de continuitate este: Valoarea din x[k] este buna daca pentru orice i de la 1 la (k-1) => x[i]#x[k]. Orice permutare este alcătuita din toate elementele mulţimii, elemente ce sunt distincte, deci vom genera toate combinările posibile de n elemente astfel încât oricare doua grupe sa difere prin ordinea de aranjare a elementelor.

Generarea aranjamentelor Orice submulţime care are aceleaşi elemente cu o alta, dar in care elementele sunt aranjate este submulţime fata de cea de-a doua. Vectorul soluţie are p componente, daci generam o soluţie finala daca am completat toate componentele vectorului. Condiţia de continuitate : valoarea din x[k] este acceptata daca pentru orice i de la 1 la (k-1), x[k]#x[i].

Generarea combinărilor Doua mulţimi care au aceleaşi elemente dar aşezate in alta ordine se considera mulţimi egale. Trebuie impus ca elementele submulţimii generate sa fie aşezate in ordine crescătoare. Orice submulţime este alcătuita din elemente distincte si aşezate in ordine crescătoare. Vectorul soluţie are p componente, deci soluţia finala este completa daca am completat toate componentele vectorului (k=p). Condiţia de continuitate: componenta x[k] este acceptata daca pentru orice k>1 componentele din fata lui sunt in ordine crescătoare (x[k-1]>x[k]).