...etoda BacktrackingMetoda Backtracking se aplica problemelor in care solutia poate fi reprezentata sub forma unui vector x x1, x2, x3, xk, xn S, unde S este multimea solutiilor problemei si S S1 x S2 x x Sn, si Si sunt multimi finite avand s elemente si xi si , i 1..n.Pentru fiecare problema se dau relatii intre componentele vectorului x, care sunt numite conditii interne solutiile posibile care satisfac conditiile interne se numesc solutii rezultat. Metoda de generare a tuturor solutiilor posibile si apoi de determinare a solutiilor rezultat prin verificarea indeplinirii conditiilor interne necesita foarte mult timp.Metoda backtracking evita aceasta generare si este mai eficienta. Elementele vectorului x, primesc pe rand valori in ordinea crescatoare a indicilor, xiks va primi o valoare numai daca au fost atribuite valori elementelor x1.. xik-1s. La atribuirea valorii lui xiks se verifica indeplinirea unor conditii de continuare referitoare la x1 xik-1s. Daca aceste conditii nu sunt indeplinite, la pasul k, acest lucru inseamna ca orice valori i-am atribui lui xik1s, xik1s, .. xins nu se va ajunge la o solutie rezultat.Metoda backtracking construieste un vector solutie in mod progresiv incepand cu prima componenta a vectorului si mergand spre ultima cu eventuale reveniri asupra atribuirilor anterioare.Metoda se aplica astfel 1se alege prima valoare sin S1 si I se atribuie lui x1 2se presupun generate elementele x1 xik-1s, cu valori din S1..Sik-1s pentru generarea lui xiks se alege primul element din Siks disponibil si pentru valoarea aleasa se testeaza indeplinirea conditiilor de continuare.Pot aparea urmatoarele situatii axiks indeplineste conditiile de continuare. Daca s-a ajuns la solutia finala k n atunci se afiseaza solutia obtinuta. Daca nu s-a ajuns la solutia finala se trece la generarea elementului urmator x ik-1sbxiks nu indeplineste conditiile de continuare. Se incearca urmatoarea valoare disponibila din Siks. Daca nu se gaseste nici o valoare in Siks care sa indeplineasca conditiile de continuare, se revine la elementul xik-1s si se reia algoritmul pentru o noua valoare a acestuia. Algoritmul se incheie cand au fost luate in considerare toate elementele lui S1. Problemele rezolvate prin aceasta metoda necesita timp mare de executie, de aceea este indicat sa se foloseasca metoda numai daca nu avem alt algoritm de rezolvare.Daca multimile S1,S2, Sn au acelasi numar k de elemente, timpul necesar de executie al algoritmului este k la n. Daca multimile S1, S2.. Sn nu au acelasi numar de elemente, atunci se noteaza cu m minimul cardinalelor multimilor S1 Sn si cu M , maximul. Timpul de executie este situat in intervalul im la n .. M la ns. Metoda backtracking are complexitatea exponentiala, in cele mai multe cazuri fiind ineficienta. Ea insa nu poate fi inlocuita cu alte variante de rezolvare mai rapide in situatia in care se cere determinarea tuturor solutiilor unei probleme.APLICAbII REZOLVATEExempleGenerarea permutarilor. Se citeste un numar natural n. Sa se genereze toate permutarile multimii I1, 2, 3, ,nS.Generarea permutarilor se va face tinand cont ca orice permutare va fi alcatuita din elemente distincte ale multimii A. Din acest motiv, la generarea unei permutari, vom urmari ca numerele sa fie distincte.Prezentam algoritmul corespunzator cazului n312312222111111123333311111221231111233222222se incarca in stiva pe nivelul 1 valoarea 1incarcarea valorii 1 pe nivelul al 2-lea nu este posibila, intrucat aceasta valoare se gaseste si pe nivelul 1 al stiveiincarcarea valorii 2 pe nivelul al 2-lea este posibila, deoarece aceasta valoare nu mai este intalnitavaloarea 1 din nivelul al 3-lea se regaseste pe nivelul 1valoarea 2 din nivelul al 3-lea se regaseste pe nivelul al 2-leavaloarea 3 pe nivelul al 3-lea nu e intalnita pe n...
Download