Această
tehnică se foloseşte în rezolvarea problemelor care îndeplinesc simultan
următoarele condiţii:
- soluţia lor
poate fi pusă sub forma unui vector S=(x1,x2, ...,xn)
- fiecare
element al soluţiei xi poate să ia valori intr-o
mulţime Ai
- mulţimile A1,
A2 .. An sunt mulţimi finite, iar elementele lor se consideră că se află
într-o relaţie de ordine bine stabilită;
- A1, A2,..., An pot coincide.
- nu se dispune
de o altă metodă de rezolvare, mai rapidă
Este o tehnică de programare aplicabilă algoritmilor care oferă mai multe soluţii si are ca rezultat obţinerea tuturor soluţiilor problemei. Fiecare soluţie se memorează într-o structură de date de tip stivă implementată cu ajutorul unui vector. Deci fiecare soluţie poate fi pusă sub forma unui vector.
Într-un algoritm backtracking ne interesează toate soluţiile posibile. Pentru a obţine fiecare soluţie finală se completează stiva nivel cu nivel trecând astfel prin nişte soluţii parţiale. Astfel soluţiile finale cât şi cele parţiale pentru a fi luate în considerare trebuie să îndeplinească anumite condiţii numite condiţii de validare. O soluţie care îndeplineşte o astfel de condiţie se numeşte soluţie validă. Toate configuraţiile stivei ce reprezintă soluţii finale sunt alcătuite din elementele aceleiaşi mulţimi bine definite pe care o numim mulţimea soluţiilor.
Fiecare nouă soluţie parţială se obţine prin completarea soluţiei parţiale precedente cu încă un nivel pe stivă. La fiecare nivel se pun valori din mulţimea soluţiilor care nu au fost încercate până când se obţine o soluţie validă. În acest moment se trece la nivelul următor în stiva pentru a completa mai departe soluţia reluând încercările pe noul nivel. La un moment dat pe un anumit nivel nu mai exista nici o valoare neîncercata 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.
Niciun comentariu:
Trimiteți un comentariu