Backtracking

Metoda backtracking se aplică problemelor în care soluția este o submulțime a datelor de intrare, ea determinând toate soluțiile posibile ale problemei.

  În anumite situații, poate fi asemănată cu elementele de combinatorică de la matematică, putând să semene cu generarea de combinări, aranjamente, permutări etc.

Înțelegerea procedeului

Enunț: Utilizând metoda backtracking, să se genereze numerele întregi formate din 4 cifre impare și distincte.

  Din mulțimea cifrelor impare, {1,3,5,7,9} se vor lua primele elemente care respectă proprietatea, astfel că prima soluție generată va fi : 1357. La următorul pas se încearcă, începând de la dreapta la stânga, să se introducă alte valori, iar în cazul nostru se generează valoarea 1359.

    Propun observarea generării pe etape:
  1. Se generează deci prima soluție: 1357;
  2. Se ia ultima soluție generată și se încearcă alte valori de la dreapta la stânga; în loc de 7 se va pune cifra 9 și se afișează astfel a doua soluție;
  3. După generarea lui 1359 nu mai există altă valoare de pus la unități și se trece la zeci. Următoarea valoare după 5 este 7. În cifra unităților se pune prima cifră care nu există încă, 5. Se afișează soluția: 1375;
  4. Se reia verificarea și se afișează următoarea dată: 1379;
  5. Nu se mai poate pune nimic la unități, cifra zezilor devine 9: 1395;
  6. Se mai generează apoi 1397.
  7. Nu se mai poate pune nicio cifră la zeci, se trece la sute, prima soluție este: 1537 (se iau primele variante disponibile din mulțimea valorilor);
  8. ...
  9. Ultima soluție pentru cifra miilor 1 va fi: 1975;
  10. Se va trece la înlocuirea cifrei 1 cu următoarea valoare, adică 3; se generează: 3157.
  11. ...
  12. Ultima soluție este 9753;

  Această parte poate părea confusing și lungă, dar am încercat să explic detaliat modul său de funcționare.
  Prin urmare, din mulțimea valorilor din care extragem posibile valori vom începe cu verificarea primelor elemente, de la dreapta la stânga elementelor generate anterior.