Definiția metodei Backtracking

Backtracking este o metodă sistematică de generare a tuturor soluțiilor posibile pentru o problemă, prin construirea incrementală a soluțiilor și verificarea la fiecare pas a validității parțiale. Algoritmul explorează toate combinațiile posibile, dar „se întoarce” (backtrack) imediat ce constată că o construcție parțială nu poate duce la o soluție validă completă. Metoda utilizează în general un vector st[] în care st[k] reprezintă valoarea aleasă pentru nivelul k. Pașii generali ai algoritmului sunt: init(k) – inițializează nivelul k, succesor(k) – generează următoarea valoare posibilă, valid(k) – verifică dacă valoarea aleasă respectă restricțiile, solutie(k) – verifică dacă s-a ajuns la o soluție completă, afis() – afișează soluția, back() – reia procesul de la ultimul nivel valid. Deși generează toate soluțiile, metoda nu este întotdeauna eficientă din punct de vedere al timpului, dar este extrem de utilă pentru probleme de tip combinatorial și pentru exerciții educative.

Coduri C++ iterative

Permutări

#include <iostream>
using namespace std;
int st[100], n;
void init(int k){ st[k]=0; }
int succesor(int k){ if(st[k]<n){ st[k]++; return 1;} return 0;}
int valid(int k){ for(int i=1;i<k;i++) if(st[i]==st[k]) return 0; return 1;}
int solutie(int k){ return k==n;}
void afis(){ for(int i=1;i<=n;i++) cout<<st[i]<<" "; cout<<endl;}
void back1(){
    int k=1, as; init(k);
    while(k>0){
        do as=succesor(k); while(as==1 && valid(k)==0);
        if(as==1)
            if(solutie(k)) afis();
            else{k++; init(k);}
        else k--;
    }
}
int main(){ cin>>n; back1(); return 0; }
    

Aranjamente

#include <iostream>
using namespace std;
int st[100], n, t;
void init(int k){ st[k]=0; }
int succesor(int k){ if(st[k]<n){ st[k]++; return 1;} return 0;}
int valid(int k){ for(int i=1;i<k;i++) if(st[i]==st[k]) return 0; return 1;}
int solutie(int k){ return k==t;}
void afis(){ for(int i=1;i<=t;i++) cout<<st[i]<<" "; cout<<endl;}
void back1(){ int k=1, as; init(k);
    while(k>0){
        do as=succesor(k); while(as==1 && valid(k)==0);
        if(as==1)
            if(solutie(k)) afis();
            else{k++; init(k);}
        else k--;
    }
}
int main(){ cin>>n>>t; back1(); return 0; }
    

Combinări

#include <iostream>
using namespace std;
int st[100], n, t;
void init(int k){ st[k]=0; }
int succesor(int k){ if(st[k]<n){ st[k]++; return 1;} return 0;}
int valid(int k){ if(k==1) return 1; return st[k]>st[k-1]; }
int solutie(int k){ return k==t; }
void afis(){ for(int i=1;i<=t;i++) cout<<st[i]<<" "; cout<<endl;}
void back1(){ int k=1, as; init(k);
    while(k>0){
        do as=succesor(k); while(as==1 && valid(k)==0);
        if(as==1)
            if(solutie(k)) afis();
            else{k++; init(k);}
        else k--;
    }
}
int main(){ cin>>n>>t; back1(); return 0; }
    

Numere de n cifre impare

#include <iostream>
using namespace std;
int st[100], n;
void init(int k){ st[k]=-1; }
int succesor(int k){ if(st[k]<9){ st[k]+=2; return 1;} return 0;}
int valid(int k){ return 1; }
int solutie(int k){ return k==n; }
void afis(){ for(int i=1;i<=n;i++) cout<<st[i]; cout<<" "; }
void back1(){ int k=1, as; init(k);
    while(k>0){
        do as=succesor(k); while(as==1 && valid(k)==0);
        if(as==1)
            if(solutie(k)) afis();
            else{k++; init(k);}
        else k--;
    }
}
int main(){ cin>>n; back1(); return 0; }
    

Exerciții propuse

1. Generează toate numerele de 5 cifre folosind doar 3,5,7 în ordine crescătoare. Care sunt ultimele 3 soluții generate?
2. Generează toate numerele de 5 cifre cu cifre strict crescătoare, în ordine descrescătoare. Care sunt ultimele 3 soluții generate?
3. Generează toate șirurile binare de 5 cifre în ordine lexicografică. Care sunt ultimele 3 soluții generate?
4. Numere de 5 cifre cu cifre distincte, fără două cifre pare alăturate, în ordine crescătoare. Precizați următoarele 3 soluții după primele 5 date.
5. Numere de 5 cifre cu cifre strict crescătoare, fără două cifre pare alăturate, în ordine descrescătoare. Precizați următoarele 3 soluții după primele 5 date.
6. Se compară elemente reale din mulțimea M={x1,..,xn} (1000<n≤10000). Care dintre următoarele poate fi generat cu backtracking: a. sortarea elementelor b. generarea produsului cartezian MxM c. determinarea minimului d. generarea tuturor permutărilor
7. Permutarea mulțimii {1..n} prin backtracking, xk este valid dacă a. xk ∉ {x1..xk-1} … etc. Precizați condiția corectă.
8. Generarea numerelor de 5 cifre cu cifre strict crescătoare echivalent cu: a. submulțimi b. produs cartezian c. aranjamente d. combinări
9. Generarea șirurilor de max 3 caractere din {A,B,C,D,E} în ordine lexicografică. Care șir urmează după BAE?
10. Generarea combinațiilor de n cifre cu primele și ultimele cifre 0 și diferența alăturată 1. Care este următoarea combinație?
11. Generarea numerelor de n cifre din {0,2,9}. Care număr urmează după 2009?
12. Generarea numerelor de n cifre din {0,2,8} divizibile cu 100. Câte sunt?
13. Generarea tuturor cuvintelor de 3 litere mici din alfabetul englez. Echivalentul algoritmic?
14. Generează numere impare de max 3 cifre din {0,1,2,3}. Care este a 12-a soluție?
15. Generarea grupelor de accesorii tenis cu sumă exact 500. Care este a 5-a soluție?
16. Formarea șiragurilor de 4 pietre prețioase cu restricții alăturare. Care este ultimul șirag?
17. Pregătirea clătitelor cu 3 tipuri ingrediente aluat, 3 tipuri umplutură și 3 tipuri ornare, respectând restricții. Care este a 7-a soluție?
18. Pregătirea ținutei cu 6 articole și restricții ordonare. Care este a 6-a soluție?
19. Generarea tuturor permutărilor pentru n=4. Precizați prima și ultima soluție.
20. Generează toate aranjamentele de 3 elemente din {1,2,3,4,5}. Precizați prima și ultima soluție.
21. Numere de 4 cifre cu cifre distincte, fără cifre pare consecutive. Precizați toate soluțiile.
22. Numere de 3 cifre formate din {1,3,5,7}, fără cifre consecutive egale. Precizați toate soluțiile.
23. Șiruri binare de lungime 4 cu exact două 1. Care sunt toate soluțiile?
24. Numere de 4 cifre formate din {2,4,6}, fără două cifre pare consecutive. Precizați soluțiile.
25. Generează toate permutările {A,B,C,D} cu A înainte de B și C înainte de D. Care este ordinea completă a soluțiilor?
26. Formarea combinațiilor de 3 elemente din {1,2,3,4,5,6} cu suma = 10. Care sunt toate combinațiile posibile?

Rezolvări Backtracking - Exerciții 1-26

1. Numere de 5 cifre cu {3,5,7} în ordine crescătoare

Enunț: Generați toate numerele de 5 cifre folosind doar cifrele 3,5,7 în ordine crescătoare. Care sunt ultimele 3 soluții generate?

Rezolvare:

Generarea se face crescător, de la cea mai mică combinație la cea mai mare:

Primele combinații: 33333, 33335, 33337, 33353, 33355, ...
Ultimele combinații:
77733 → 77773 → 77775 → 77777

Explicație: Ultimul număr 77777 este maxim, toate cifrele fiind cele mai mari disponibile. Pentru a obține ultimele trei soluții, analizăm cum cresc combinațiile în ordine lexicografică, incrementând de la dreapta la stânga. Astfel, înainte de 77777 avem 77775 și 77773.

2. Numere de 5 cifre strict crescătoare, în ordine descrescătoare

Enunț: Generați toate numerele de 5 cifre cu cifre strict crescătoare, în ordine descrescătoare. Care sunt ultimele 3 soluții?

Rezolvare:

Primele 5: 56789, 46789, 45789, 45689, 45679
Ultimele 3: 12345, 12346, 12347

Explicație: În ordine descrescătoare, începem cu numărul maximal 56789 și continuăm până la numărul minim 12345. Ultimele 3 soluții sunt cele mai mici combinații posibile respectând regulă cifrelor strict crescătoare.

3. Șiruri binare de 5 cifre în ordine lexicografică

Enunț: Generați toate șirurile binare de 5 cifre (0 și 1) în ordine lexicografică. Care sunt ultimele 3 soluții?

Rezolvare:

Ultimele 3 soluții: 11101, 11110, 11111

Explicație: În lexicografic, 00000 este primul, 11111 este ultimul. Ultimele trei se obțin incrementând ultima cifră și, la nevoie, penultima, respectând ordinea binară.

4. Numere de 5 cifre cu cifre distincte, fără două cifre pare alăturate, în ordine crescătoare

Enunț: Primele cinci soluții: 10325, 10327, 10329, 10345, 10347. Precizați următoarele 3 soluții generate.

Rezolvare:

Următoarele 3 soluții: 10349, 10352, 10354

Explicație: Algoritmul generează combinațiile crescător respectând restricția: nici două cifre pare consecutive. Se verifică fiecare candidatul de la dreapta la stânga, pentru a respecta regula.

5. Numere de 5 cifre cu cifre strict crescătoare, fără două cifre pare alăturate, în ordine descrescătoare

Enunț: Primele cinci soluții: 56789, 45789, 45679, 45678, 36789. Precizați următoarele 3 soluții generate.

Rezolvare:

Următoarele 3 soluții: 35789, 35679, 35678

Explicație: În ordine descrescătoare, se ia primul număr valid maximal și se generează următoarele combinații respectând regula cifrelor strict crescătoare și restricția de cifre pare.

6. Compararea elementelor reale din mulțimea M = {x1,..,xn} (1000 < n ≤ 10000)

Enunț: Care dintre următoarele poate fi generat cu backtracking: a. sortarea elementelor b. generarea produsului cartezian MxM c. determinarea minimului d. generarea tuturor permutărilor?

Rezolvare:

Varianta corectă: d. generarea tuturor permutărilor

Explicație: Algoritmul backtracking generează toate posibilitățile sistematic, pas cu pas, deci poate genera toate permutările. Sortarea sau determinarea minimului nu necesită backtracking, ci algoritmi direcți. Generarea produsului cartezian poate fi făcută mai simplu iterativ, nu neapărat cu backtracking.

7. Permutarea mulțimii {1..n} prin backtracking

Enunț: În tabloul unidimensional x, xk este valid dacă … Precizați condiția corectă.

Rezolvare: xk ∉ {x1, x2, …, xk-1}.

Explicație: Pentru a evita duplicarea elementelor în permutări, fiecare element plasat la pasul k trebuie să fie diferit de toate elementele plasate anterior.

8. Generarea numerelor de 5 cifre cu cifre strict crescătoare

Rezolvare: Echivalent cu generarea aranjamentelor de 9 elemente luate câte 5.

Explicație: Alegerea cifrelor distincte în ordine strict crescătoare corespunde exact unui aranjament fără repetiție, ordonat.

9. Șiruri de maximum 3 caractere din {A,B,C,D,E}

Enunț: Care șir urmează după BAE?

Rezolvare: BC

Explicație: În ordinea lexicografică, după BAE, trebuie să verificăm următorul șir valid cu primul caracter B și să respectăm ordinea lexicografică.

10. Combinații de n cifre cu primele și ultimele cifre 0 și diferență alăturată 1

Rezolvare: Imediat după 0101210 → 0121210

Explicație: Algoritmul generează toate combinațiile crescător, verificând diferența 1 între cifrele alăturate. După 0101210, următorul număr valid în ordine lexicografică este 0121210.

11. Numere n cifre din {0,2,9}, după 2009

Rezolvare: 2002

Explicație: În ordine crescătoare, se parcurge fiecare poziție de la stânga la dreapta. După 2009, următorul număr conform restricției este 2002.

12. Numere n cifre din {0,2,8} divizibile cu 100

Rezolvare: Sunt 8 numere.

Explicație: Numerele divizibile cu 100 trebuie să se termine cu 00, 20, 40, … respectând setul {0,2,8}. Se numără toate combinațiile posibile.

13. Generarea tuturor cuvintelor de 3 litere mici din alfabetul englez

Rezolvare: Echivalent cu produsul cartezian al mulțimii alfabetului cu ea însăși de 3 ori.

Explicație: Fiecare poziție poate fi ocupată de oricare literă, fără restricții, deci generarea tuturor combinațiilor cu repetiție corespunde exact unui produs cartezian.

14. Numere impare de max 3 cifre din {0,1,2,3}

Rezolvare: A 12-a soluție: 201

Explicație: Numerele se generează crescător, verificând ca ultima cifră să fie impară. Se numără soluțiile până la a 12-a, rezultând 201.

15. Grupuri accesorii tenis

Rezolvare: A cincea soluție: (bentiță, rachetă, șapcă)

Explicație: Se generează toate combinațiile distincte ale accesoriilor, cu suma exactă de 500. A cincea soluție se determină prin ordinea de generare crescătoare conform backtracking.

16. Șiraguri pietre prețioase

Rezolvare: Ultimul șirag: (topaz, smarald, topaz, topaz)

Explicație: Se verifică restricția: nu două pietre din {rubin,safir,topaz} alăturate. Ultimul șirag apare când pozițiile disponibile sunt completate respectând regula.

17. Pregătirea clătitelor

Rezolvare: A șaptea soluție: (ouă, lapte, făină, urdă, mărar)

Explicație: Se generează toate permutările ingredientelor, respectând restricțiile de combinații. A șaptea soluție este determinată de ordinea lexicografică conform backtracking.

18. Pregătirea ținutei

Rezolvare: A șasea soluție: (cămașă, cravată, șosete, pantaloni, sacou, pantofi)

Explicație: Algoritmul generează toate permutările articolelor cu restricții ordinale. A șasea soluție respectă ordinea backtracking.

19. Permutările pentru n=4

Rezolvare: Prima: 1234, Ultima: 4321

Explicație: Toate permutările unui set cu 4 elemente în ordine lexicografică, de la 1234 la 4321.

20. Aranjamente de 3 elemente din {1,2,3,4,5}

Rezolvare: Prima: 123, Ultima: 543

Explicație: Se generează toate aranjamentele de 3 elemente, respectând ordinea lexicografică.

21. Numere de 4 cifre fără cifre pare consecutive

Rezolvare: Se generează toate combinațiile posibile care respectă regula.

22. Numere de 3 cifre din {1,3,5,7} fără cifre consecutive egale

Rezolvare: Se afișează toate combinațiile valide, de exemplu 135, 137, 153, etc.

23. Șiruri binare de lungime 4 cu exact două 1

Rezolvare: 0011, 0101, 0110, 1001, 1010, 1100

24. Numere de 4 cifre din {2,4,6} fără două cifre pare consecutive

Rezolvare: Nu există soluții, deoarece toate cifrele sunt pare.

25. Permutările {A,B,C,D} cu A înainte de B și C înainte de D

Rezolvare: Ordinea completă a soluțiilor: ABCD, ACBD, ACDB, CABD, CADB, CDAB

26. Combinații de 3 elemente din {1,2,3,4,5,6} cu suma = 10

Rezolvare: 1,3,6; 1,4,5; 2,3,5; 2,4,4; 3,2,5 (după ordine lexicografică)