Metoda backtracking se aplica problemelor in care solutia se poate prezenta sub forma unui vector x={x1,x2,…,xn} unde x1 apartine unei multimi S1, x2 apartine multimii S2 s.a.m.d.Si i=1…n sunt multimi finite. Cerinta problemei este, de obicei, gasirea tuturor solutiilor posibile sau gasirea numarului de solutii care satisfac anumite conditii specifice problemei. De multe ori metoda se foloseste si pentru gasirea unei singure solutii (dupa gasirea acesteia se intrerupe executia programului), a unei solutii maxime/minime insa, pentru astfel de cazuri recomandam gasirea unei alte solutii de rezolvare datorita faptului ca metoda Backtracking consuma resurse mari de memorie si timp.
Conditiile interne, numite si conditii de continuitate, sunt acele conditii care trebuie indeplinite de un element pentru a fi adaugat la solutie. Validitatea elementului se verifica in functie de elementele aflate in fata lui in vectorul solutie (vectorul x).
Metoda evita generarea tuturor solutiilor posibile. Se va cauta obtinerea unei solutii prin alegerea succesiva de elemente din multimile S1, S2, S3,…,Sn. Astfel, la pasul k, se va alege un element xk din multimea Sk. Inainte de a trece la pasul k+1, se verifica daca sunt satisfacute conditiile de continuitate. In cazul in care pentru o valoare xk aleasa, conditiile de continuare nu sunt satisfacute, se va alege o alta valoare din multimea Sk, pana cand fie se va gasi o valoare care sa satisfaca conditiile de continuitate, fie se epuizeaza toate elementele multimii Sk. In cazul in care se gaseşte un element xk convenabil avem doua cazuri: fie s-a ajuns la obtinerea unei solutii caz in care se afiseaza solutia, fie nu s-a ajuns la o solutie caz in care se trece la gasirea urmatorului element din vectorul solutie (cel de pe pozitia k+1). Exista şi cazul in care pozitia k din vectorul solutie nu s-a putut completa cu un element xk din Sk, adica nu s-a gasit un element care sa indeplineasca conditiile de continuitate. In acest caz se va reveni la pasul anterior (k-1). Se va renunta la valoarea x(k-1) aleasa şi se va cauta alegerea unei alte valori (urmatoarea valoare din multimea k-1).
Ca orice algoritm in care sunt prezente instructiuni repetitive, algoritmul backtracking poate fi reprezentat intr-o maniera recursiva sau nerecursiva.
APLICATII
1. Dintr-un numar de 6 cursuri opţionale un elev trebuie să aleagă 3. Să se afişeze toate posibilităţile de alegere precum şi numarul lor.
2.Lui IRINEL îi plac nr. formate numai din cifre pare cifre aflate în ordine descrescătoare. Să se determine şi să se afişeze pe ecran toate nr. de n cifre (0
3.Problema celor n dame. Fiind dată o tablă de şah n´n se cer toate soluţiile de aranjare a n dame, astfel încât să nu se afle două dame pe aceeaşi linie, coloană sau diagonală (damele să nu se atace reciproc).
4..PROBLEMA COLORARII HARTILOR: Fiind dată o hartă cu n ţări, se cer toate soluţiile de colorare a hărţii, utilizând cel mult patru culori, astfel încât două ţări de frontieră comună să fie colorate diferit. Este demonstrat faptul că sunt suficiente numai patru culori pentru ca orice hartă să poată fi colorată.
5. PROBLEMA DRAPELELOR : Avem la dipoziţie 6 culori: alb, galben, roşu, verde, albastru, negru. Să se precizeze toate drapelele tricolore care se pot proiecta, ştiind că trebuie respectate regulile:
- orice drapel are culoarea din mijloc galben sau verde
- cele trei culori de pe drapel sunt distincte.
Observaţie: utilizaţi facilităţile unit-ului crt, în afişarea culorilor drapelelor generate
6.
Produsul cartezian a n mulţimi. Se dau mulţimile de mai jos şi se cere produsul cartezian al lor.
A1 = {1, 2, 3, …, k1}
A2 = {1, 2, 3, …, k2}
………………………
An = {1, 2, 3, …, kn}
7. TURNURI DE CUBURI Se dau n cuburi numerotate 1,2,…,n, de laturi Li si culori Ci, i=1,2,…,n (fiecare culoare este codificata printr-un caracter). Sa se afişeze toate turnurile care se pot forma luând k cuburi din cele n disponibile, astfel încât:
-laturile cuburilor din turn sa fie in ordine crescătoare;
-culorile a oricare doua cuburi alăturate din turn sa fie diferite.
8.
Problema comis-voiajorului. Un comis voiajor trebuie să viziteze un număr n de oraşe. Iniţial, el se află într-unul dintre ele, notat 1. Comis – voiajorul doreşte să nu treacă de două ori prin acelaşi oraş, iar la întoarcere să revină în oraşul 1. Cunoscând legăturile existente între oraşe, se cere să se tipărească toate drumurile posibile pe care le poate efectua comis – voiajorul.
9
Sa se genereze partitiile nr.natural n.partitii.cpp
ex.n=5
5=1+1+1+1+1
5=1+1+1+2
5=1+1+3
5=1+4
5=5.
10.
10. Se citeste de la tastatura un numar natural n par, n<30. Sa se genereze si sa se afiseze pe ecran toate combinatiile de n paranteze rotunde care se închid corect. De exemplu, pentru n=4 se obtin urmatoarele combinatii: ( ( ) ) si ( ) ( ) .PARANTEZE.CPP
|
11.Se citeste un numar natural n<30. Sa se afiseze toate modalitatile de a-l calcula prin adunari sau scaderi ale numerelor 1,2, ...n. Fiecare numar de la 1 la n va aparea o singura data în descompunerea lui n. Daca acest lucru nu este posibil, se va afisa mesajul „Imposibil”.
Exemplu:
5=1+2+3+4-5
5=1-2-3+4+5
5=-1+2+3-4+5
SUMA.CPP
LISTA PROBLEME
GRILE BACKTRACKING
grile backtracking.pdf