1. Generalități
1.1. Metoda reluării presupune că soluția problemei pe care trebuie s-o rezolvăm poate fi reprezentată printr-un vector X, unde X=x1, x2 ..., xn.
1.1.1. Vectorul X apare ca un element al produsului cartezian S, unde S=S1*S2 ...*Sn.
1.1.1.1. Mulţimea finită S = S1*S2*... *Sn se numeşte spaţiul soluţiilor posibile.
1.1.1.2. 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ă (generalizează) sau minimizează o eventuală funcţie obiectiv dată.
1.1.1.3. Pentru fiecare problemă concretă sunt date anumite relaţii între componentele x1,... xn ale vectorului X, numite condiţii interne.
1.2. 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.
1.2.1. Odată o valoare pentru xk stabilită, nu se trece direct la atribuirea de valori lui xk=1, ci se verifică anumite condiții de continuare referitoarela x1, x2, ..., xk.
1.2.2. Dacă aceste condiții nu sînt satisfăcute va trebui să facem o altă alegere pentru xk.
1.2.3. 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.
1.3. Metoda backtracking poate fi reprezentată uşor, printr-un arbore.
1.3.1. 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.
2. Probleme
2.1. Probleme de generare
2.1.1. Problemă în care vectorul soluţie are lungime fixă şi fiecare element apare o singură dată în soluţie, exemple:
2.1.1.1. generarea permutărilor unei mulţimi
2.1.1.2. generarea aranjamentelor unei mulţimi
2.1.1.3. generarea submulţimilor unei mulţimi
2.1.1.4. generarea submulţimilor cu m elemente ale unei mulţimi (combinări)
2.1.1.5. generarea produsului cartezian a n mulţimi
2.1.1.6. generarea tuturor secvenţelor de n (par) paranteze care se închid corect.
2.1.1.7. colorarea ţărilor de pe o hartă astfel încât oricare două ţări vecine să aibă culori diferite
2.1.1.8. aranjarea a n regine pe o tablă de şah de dimensiune n fără ca ele să se atace.
2.1.1.8.1. Aranjarea reginelor
2.1.2. Probleme în care vectorul soluţie are lungime variabilă şi fiecare element poate să apară de mai multe ori în soluţie:
2.1.2.1. partiţiile unei mulţimi
2.1.2.2. plata unei sumei cu monede de valori date
2.1.2.3. Partiţiile unui număr natural
2.1.2.3.1. Fie n>0, natural. Să se scrie un program care să afişeze toate partiţiile unui număr natural n. Numim partiţie a unui număr natural nenul n o mulţime de numere naturale nenule {p1, p2, …, pk} care îndeplinesc condiţia p1+p2+ …+pk = n. Ex: pt n = 4 programul va afişa: 4 = 1+1+1+1; 4 = 1+1+2; 4 = 1+3; 4 = 2+2; 4 = 4; Observaţii: - lungimea vectorului soluţie cel mult n;
2.1.3. Problemele în plan necesită parcurgerea unui tablou unidimensional, iar cele mai cunoscute sunt:
2.1.3.1. Parcurgerea tablei de şah cu un cal, fără a trece de două ori prin aceeaşi poziţie
2.1.3.1.1. Săritura calului. Fiind dată o tablă de şah de dimensiunea nxn şi un cal în colţul stânga sus al acesteia, se cere să se afişeze toate posibilităţile de mutare a acestei piese de şah astfel încât să treacă o singură dată prin fiecare pătrat al tablei.
2.1.3.2. Găsirea ieşirii dintr-un labirint