Metoda Backtracking

Backtracking este o metodă de parcurgere sistematică a spațiului soluțiilor posibile al unei probleme.

Metoda este generală și poate fi adaptată pentru orice problemă pentru care dorim să obținem toate soluțiile posibile sau să selectăm o soluție optimă din mulțimea soluțiilor posibile.

Backtracking este una dintre cele mai costisitoare ca timp de execuție metode de programare.

În general, vom modela soluția problemei într-un tablou unidimensiunal st=[st1, st2, st3, … , stk, … , stn]

Fiecare element ”st[i]” aparține unei mulțimi finite și ordonate M i [m1, m2, … , mp]

Aplicație.

La fiecare pas k, pornim de la o soluție parțială st=[st[1], st[2], … , st[k-1]].

Pasul 1 – încercăm să extindem soluția adăugând un nou element la sfârșitul vectorului pe nivelul kPasul 2 – căutăm în mulțimea Mk un nou element.Pasul 3 – dacă există un element din mulțimea Mk neselectat, verificăm dacă acest element îndeplinește condițiile impuse de problemă, numite condiții de continuarePasul 4 – dacă sunt respectate conedițiile de continuare adăugăm elementul selectat la soluția parțialăPasul 5 – verificăm dacă am obținut o soluție completăDacă am obținut soluția completă, o afișăm și se reia apoi algoritmul de la pasul 1. Dacă nu am obținut soluția completă se crește nivelul din stivă, k=k+1, și se reia algoritmul de la pasul 1.Pasul 6 – dacă nu sunt respectate condițiile de continuare se reia algoritmul de la pasul 2Pasul 7 – dacă nu mai există niciun element neverificat în mulțimea Mk, înseamnă că în acest moment nu mai există nicio posibilitate de obținere a soluției astfel încât trebuie să modificăm alegerile făcute în prealabil mergând în stivă un nivel mai jos, reluând apoi pasul 1.

Revenirea în caz de insucces pentru generarea tuturor soluțiilor problemei a condus la denumirea ”Backtracking”.