Metoda backtracking foloseşte la rezolvarea multor probleme. Pentru ca o problemă să poată să fie rezolvată cu metoda backtracking, ea trebuie să îndeplinească simultan următoarele condiţii:
- poate avea mai multe soluţii, acestea fiind puse sub formă de vector ca de exemplu S(x1,x2,x3,…xn), unde x1ЄA1, x2ЄA2,…, xnЄAn
- mulţimile A1, A2, A3, …, An sunt mulţimi finite, având elementele aflate într-o ordine bine stabilită, ele putând să fie chiar identice.
În acest caz, vectorul care conţine soluţii se numeşte stivă.
Se alege primul element x1 din A1. Se repetă într-o structură repetitivă până când nu mai există elemente netestate din mulţimea A1;
- se presupune că am ajuns la elementul xk din mulţimea Ak şi se doreşte găsirea unui element xk+1 din mulţimea Ak+1. Acesta trebuie să îndeplinească condiţiile de existenţă a unui astfel de element, impuse de problemă, iar dacă:
- îndeplineşte aceste condiţii atunci trebuie să îndeplinească alte condiţii impuse de problemă, prin care se determină dacă el ar putea face parte din soluţie. Dacă: (1)da, atunci se testează dacă şirul de elemente este o soluţie a problemei; dacă: (2) da, atunci se tipăreşte vectorul care conţine aceste soluţii; (2) nu, atunci se trece pe următorul nivel din şir (k:=k+1); (1) nu, nu îndeplineşte condiţiile de a face parte din soluţie, atunci se trece la următorul element netestat din mulţimea Ak; nu mai poate exista un element pe nivelul k, atunci se trece la nivelul anterior şi se încearcă aici găsirea unui element; repetiţia se termină când am ajuns pe nivelul 0.
Un exemplu de problemă ce foloseşte tehnica backtraking este Problema Labirintului
REPREZENTARE GRAFICA CEVA ? NU CREC INTELEGE OMUL DIN CAT ATI SCRIS :p