Descrierea metodei
Backtracking este numele unui algoritm general de descoperire a tuturor soluțiilor unei probleme de calcul, algoritm ce se bazează pe construirea incrementală de soluții-candidat, abandonând fiecare candidat parțial imediat ce devine clar că acesta nu are șanse să devină o soluție validă.
Tehnica backtracking se poate aplica doar pentru probleme ce admit conceptul de „candidat parțial de soluție” și oferă un test relativ rapid asupra posibilității ca un astfel de candidat să fie completat către o soluție validă. Când se poate aplica, însă, backtrackingul este adesea mult mai rapid decât căutarea prin metoda forței brute prin toți candidații, întrucât este capabilă să elimine dintr-un singur test un mare număr de candidați.
Termenul „backtrack” a fost inventat de matematicianul american D. H. Lehmer în anii 1950.
Metoda Backtracking se utilizează pentru rezolvarea unor probleme în care:
* se obțin mai multe soluții;
* soluția este formată din unul sau mai multe elemente, fiind reprezentată printr-un tablou X=(
* tabloul X este o structură liniară de tip stivă;
* elementele depuse în tablou îndeplinesc anumite condiții impuse de enunțul fiecărei probleme.