Backtracking-Prezentare generala

Prezentare generală

Această metodă generală de programare se aplică problemelor în care soluţia se poate reprezenta sub forma unui vector X = (x1, ..., xn)ÎS unde S = S1 x ... x Sn , unde mulţimile S1, ...,Sn sunt mulţimi finite având |Si| = si elemente. Pentru fiecare problemă concretă sunt date anumite relaţii între componentele x1 , ... xn ale vectorului X, numite condiţii interne.

Mulţimea finită S = S1 x S2 x... x Sn se numeşte spaţiul soluţiilor posibile (este un produs cartezian). Soluţiile posibile care satisfac condiţiile interne se numesc soluţii rezultat. Ceea ce ne propunem este de a determina toate soluţiile rezultat, cu scopul de a le afişa sau de a alege dintre ele una care maximizează sau minimizează o eventuală funcţie obiectiv dată.

O metoda simplă de determinare a soluţiilor rezultat constă în a genera într-un mod oarecare toate soluţiile posibile şi de a verifica dacă ele satisfac condiţiile interne. Dezavantajul constă în faptul că timpul cerut de această investigare exhaustivă este foarte mare. Astfel, chiar pentru |Si| = 2, " i, timpul necesar este de ordinul 2n, deci exponenţial.

Metoda backtracking urmăreşte să evite generarea tuturor soluţiilor posibile. În acest scop, elementele vectorului X primesc pe rând valori în sensul că lui xk i se atribuie o valoare numai dacă au fost atribuite deja valori lui x1 ,... xk-1 . Mai mult, odată o valoare pentru xn stabilită, nu se trece direct la atribuirea de valori lui xk+1 , neîndeplinirea lor exprimând faptul că oricum am alege xk+1,...,xn nu vom putea ajunge la o soluţie rezultat, adică o condiţie pentru care condiţiile interne să fie satisfăcute. Evident că în cazul neîndeplinirii condiţiilor de continuare va trebui să facem o altă alegere pentru xk sau dacă Sk a fost epuizat să micşorăm pe k cu o unitate încercând să facem o nouă alegere pentru xk etc.; această micşorare a lui k dă numele metodei, ilustrând faptul că atunci când nu mai putem avansa, urmărim înapoi secvenţa curentă din soluţie. Este evident că între condiţiile de continuare şi condiţiile interne există o strânsă legătură. O bună alegere pentru condiţiile de continuare are ca efect o importantă reducere a numărului de calcule.

Metoda backtracking poate fi reprezentată uşor, pe un arbore construit astfel:

- nivelul 1 conţine rădăcina;

- din orice vârf de pe nivelul k pleacă sk muchii spre nivelul k+1 etichetaţi cu cele sk muchii ale lui Sk.

Nivelul n+1 va conţine s1 × s2 × ... × sn vârfuri. Pentru fiecare vârf de pe nivelul n+1, etichetele muchiilor conţinute pe drumul ce leagă rădăcina de acest vârf reprezintă o soluţie posibilă.

Exemplu - Să considerăm problema submulţimilor de sumă dată care constă în următoarele: Fie A = (a1, a2, ..., an) cu ai > 0, " i. Fie MÎR+. Se caută toate submulţimile B ale lui A pentru care suma elementelor este M.

Pentru a putea realiza problema prin metoda backtracking vom reprezenta soluţia sub forma x = (x1, ..., xn) unde xi = 1 dacă aiÎB şi xi = 0 în caz contrar. Sa ne situăm în ipoteza ca n=4. Arborele ataşat metodei backtracking este următorul:

Câştigul obţinut prin introducerea condiţiilor de continuare constă în faptul că, dacă într-un vârf ele nu mai sunt verificate, se va renunţa la parcurgerea subarborelui care are ca rădăcină acest vârf.

Acest exemplu permite prezentarea unei variante a metodei backtracking. Într-adevăr, să considerăm drept soluţie posibilă o valoare k £ n împreună cu k-uplul (x1, ..., xk) unde pentru i Î {1, ..., k}, xi reprezintă indicele elementului pe care îl introducem în B. Evident xi ¹ xj pentru i¹j. Pentru a nu se repeta soluţii, vom presupune x1<x2<...<xn .

Obţinem astfel următorul arbore în care fiecare vârf corespunde unei soluţii posibile.

Diferitele variante ale metodei backtracking nu schimbă esenţa ei care constă în faptul că este reprezentabilă pe un arbore care este parcurs "coborând" în arbore numai dacă există şanse de a ajunge la o soluţie rezultat.

În continuare, problemele care vor fi prezentate vor urma o schema generală şi anume:

- se va testa dacă am obţinut o soluţie, situaţie în care acesta se va reţine;

- dacă nu am obţinut soluţie se încearcă plasarea unui nou element în vectorul soluţie cu respectarea condiţiilor de continuare;

- dacă nu se reuşeşte plasarea unui nou element şi spaţiul valorilor posibile de plasat s-a epuizat, se revine la poziţia anterioară şi se încearcă să se plaseze pe ea un alt element.

Faptul că după plasarea unui element în vectorul soluţie algoritmul presupune plasarea unui element pe poziţia imediat următoare, adică de fapt reluarea algoritmului, conduce posibilitatea abordării recursive a algoritmilor de tip backtracking. Acest lucru permite o scriere mult mai scurtă şi mai simplă a algoritmilor şi apoi a programelor care îi implementează. Astfel, general, un algoritm backtracking poate fi prezentat astfel:

Subalgoritm back (k)

pentru fiecare valoare i din multimea Sk execută

xk←i

dacă X respectă condiţiile interne atunci

dacă X este solutie atunci

afisează X

altfel

apelează back(k+1)

sfdacă

sfdacă

sfpentru

În funcţie de problema concretă, în algoritmul descris mai sus se vor modifica doar instrucţiunea pentru, condiţiile interne şi cele de soluţie, structura algoritmului păstrându-se.

Probleme de generare. Oportunitatea utilizării metodei backtracking

Problemele care se rezolvă prin metoda backtracking pot fi împărţite în mai multe grupuri de probleme cu rezolvări asemănătoare, in funcţie de modificările pe care le vom face în algoritm. Principalele grupuri de probleme sunt:

a) probleme în care vectorul soluţie are lungime fixă şi fiecare element apare o singură dată în soluţie;

b) probleme în care vectorul soluţie are lungime variabilă şi fiecare element poate să apară de mai multe ori în soluţie;

c) probleme în plan, atunci când spaţiul în care ne deplasăm este un tablou bidimensional.

Vom prezenta în cele ce urmează câteva probleme care pac parte din primul grup. Cele mai cunoscute sunt:

• • generarea permutărilor unei mulţimi

  • generarea aranjamentelor unei mulţimi

  • generarea submulţimilor unei mulţimi

  • generarea submulţimilor cu m elemente ale unei mulţimi (combinări)

  • generarea produsului cartezian a n mulţimi

  • generarea tuturor secvenţelor de n (par) paranteze care se închid corect.

  • colorarea ţărilor de pe o hartă astfel încât oricare două ţări vecine să aibă culori diferite

  • aranjarea a n regine pe o tablă de şah de dimensiune n fără ca ele să se atace.

Toate problemele din acest grup au particularitatea că soluţia se obţine atunci când vectorul soluţie ajunge să conţină un anumit număr de elemente.

Restructurare:

Aceasta tehnica se foloseste in rezolvarea problemelor care indeplinesc simultan urmatoarele conditii:

• solutia lor poate fi pusa sub forma unui vector S=(x₁,x₂, ...,x_n)

• fiecare element al solutiei x_i poate sa ia valori intr-o multime A_i

• multimile A1, A2 .. An sunt multimi finite, iar elementele lor se considera ca se afla intr-o relatie de ordine bine stabilita;

• A1, A2,..., An pot coincide.

• nu se dispune de o alta metoda de rezolvare, mai rapida

Este o tehnica de programare aplicabila algoritmilor care ofera mai multe solutii si are ca rezultat obtinerea tuturor solutiilor problemei. Fiecare solutie se memoreaza intr-o structura de date de tip stiva implementata cu ajutorul unui vector. Deci fiecare solutie poate fi pusa sub forma unui vector.

Intr-un algoritm backtracking ne intereseaza toate solutiile posibile. Pentru a obtine fiecare solutie finala se completeaza stiva nivel cu nivel trecand astfel prin niste solutii partiale. Astfel solutiile finale cat si cele partiale pentru a fi luate in considerare trebuie sa indeplineasca anumite conditii numite conditii de validare. O solutie care indeplineste o astfel de conditie se numeste solutie valida. Toate configuratiile stivei ce reprezinta solutii finale sunt alcatuite din elementele aceleiasi multimi bine definite pe care o numim multimea solutiilor.

Fiecare noua solutie partiala se obtine prin completarea solutiei partiale precedente cu inca o nivel pe stiva. La fiecare nivel se pun valori din multimea solutiilor care nu au fost incercate pana cand se obtine o solutie valida. In acest moment se trece la nivelul urmator in stiva pentru a completa mai departe solutia reluand incercarile pe noul nivel. La un moment dat pe un anumit nivel nu mai exista nici o valoare neincercata din multimea valorilor problemei.In acest caz se face un pas inapoi in stiva la nivelul anterior si se reia cautarea cu valorile ramase neincercate pe acest nivel anterior. Respectivul nivel a mai fost vizitat dar l-am abandonat dupa ce am pus o valoare care a generat o solutie valida. Deci este posibil sa fi ramas aici valori neincercate. Daca nici pe acest nivel nu mai avem valori neincercate mai facem un pas inapoi in stiva. Mecanismul revenirilor a determinat denumirea de metoda backtracking. Plecand de la nivelul 1 si repetand algoritmul pana cand pe toate nivelele au fost incercate toate valorile din multimea valorilor se obtin solutii finale care se tiparesc.

Pentru a descrie formatul general al metodei vom utiliza o functie. Consideram ca vectorul x este variabila globala. Vom presupune ca fiecare x[i] poate lua ca valori numerele din intervalul [a,b]. Functia Valid va testa daca solutia construita pana la un pas reprezinta o solutie partiala valida.Functia SolutieFinala va testa daca s-a obtinut o solutie finala.