Metode si Tehnici de programare - limbajul C++
Adrian Runceanu
Capitolul 10 - METODA BACKTRACKING
A.Consideratii teoretice
Aceasta metoda se foloseste pentru rezolvarea problemelor in care solutia este scrisa sub forma unui vector.
Fie X solutia problemei X={x1, x2, …, xn}, unde x1 apartine lui A1, x2 apartine lui A2, …, xn apartine lui An. In unele situatii A1 = A2 = … = An = A.
Notam S = A = multimea solutiilor posibile, adica multimea de elemente de unde se obtin solutiile problemei date. Pentru a gasi solutiile problemei, algoritmul backtracking nu se bazeaza pe un set de reguli fixe, ci pe incercari repetate si reveniri in caz de nereusita. Astfel se obtin solutii partiale sau finale, care nu sunt satisfacatoare, si atunci se revine in cadrul procesului de calcul si se continua cautarea pana la gasirea solutiilor dorite, din aceasta cauza acest algoritm se mai numeate ai algoritm cu revenire (backtracking algorithm).
Metoda backtracking se poate implementa si recursiv, dar implementarea iterativa foloseste o stiva, iar principiul de lucrul este cel specific stivei - LIFO (Last In First Out) - Ultimul Intrat Primul Iesit.
Daca k=0 atunci stiva este vida, daca k=n atunci stiva este plina.
Schema generală a algoritmului în pseudocod este:
{programul principal este de fapt algoritmul cu revenire backtracking}
B.Exemple de programe
In continuare prezentam cateva probleme rezolvate in care folosirea metodei backtracking duce la obtinerea tuturor solutiilor dorite:
C.Exercitii si teme
1. Sa se afiseze toate posibilitatile de colorare a unui graf neorientat cu n varfuri folosind m culori astfel incat doua noduri vecine sa aiba culori diferite.
2. Sa se afiseze toate solutiile ecuatiei in multimea numerelor naturale: 3x+y+4xz=100.
3. Sa se afiseze toate posibilitatile de asezare a n ture pe o tabla de sah de n*n astfel incat sa nu se atace una pe celalalta.
4. Sa se determine toate cuvintele ce contin numai literele a,b,c de lungime 10 care contin exact 3 simboluri 'a'; 4 simboluri 'b' si 3 simboluri 'c'.
5. Sa se determine toate numerele in baza 8 de lungime 10 care contin cel mult 5 cifre de 7 si exact 3 cifre 0.
6. Avem la dispozitie 6 culori: alb, galben, rosu, verde, albastru si negru. Sa se precizeze toate drapelele tricolore care se pot proiecta, stiind ca trebuie respectate urmatoarele reguli:
- orice drapel are culoarea din mijloc galben sau verde;
- cele trei culori de pe drapel sunt distincte.
Exemple: "alb galben rosu", "rosu verde galben"
Indicatii: Folosim o stiva cu 3 nivele, reprezentand cele trei culori de pe drapel si codificam culorile prin numere:
1 - alb
2 - galben
3 - rosu
4 - verde
5 - albastru
6 - negru
7. Sa se descompuna un numar natural N, in toate modurile posibile, ca suma de P numere naturale (P<=N).
Indicatii: Folosim o stiva cu P nivele, unde fiecare nivel ia valoarea unui termen din suma. Variabila S retine suma primelor k nivele pentru a putea testa validitatea elementului asezat pe pozitia curenta fara a mai face o parcurgere suplimentara a stivei. Conditia de validitate devine: S+ST[k]
8. Se da un numar natural par N. Sa se afiseze toate sirurile de N paranteze care se inchid corect.
Indicatii: Un sir de N paranteze care se inchid corect, este un sir in care fiecarei paranteze deschise ii corespunde o paranteza inchisa la o pozitie ulterioara in sir.
Exemple de siruri corecte: (())() ; ((())) ; ()()()
Exemple de siruri incorecte: ())()) ; (((()) ; )()()(
Deducem din propozitia de mai sus o prima conditie necesara pentru ca un sir de paranteze sa se inchida corect si anume ca nu trebuie sa deschidem mai mult de N/2 paranteze. Dupa cum se vede insa din aceste exemple (incorecte), aceasta conditie nu este suficienta: (()))( ; )))((( ; )()()( .
A doua conditie este sa nu inchidem mai multe paranteze decat am deschis.
Pentru formalizarea conditiilor notam cu Nd(k) si Ni(k) numarul de paranteze deschise, respectiv inchise, pana la pozitia k a sirului, inclusiv. Cele doua conditii sunt:
1. Nd(k) <=> N/2, 1 <= k <= n
2. Nd(k) >= Ni(k), 1 <= k <= n
Pentru implementare folosim o stiva cu N nivele:
st[i] = 1, daca paranteza de pe pozitia i este deschisa
2, daca paranteza de pe pozitia i este inchisa.
In variabilele Nd si Ni avem numarul de paranteze de fiecare fel asezate in sir pana la pozitia curenta, k.
Pentru a aseza o paranteza deschisa pe pozitia curenta trebuie sa fi deschis mai putin de N/2 paranteze, adica Nd < N/2.
Pentru a aseza o paranteza inchisa pe pozitia curenta trebuie sa mai avem o paranteza pe care sa o inchidem, adica Nd > Ni.
La urcarea si coborarea in stiva se modifica Nd sau Ni in functie de tipul parantezei de pe nivelul respectiv.