|
|
|
CAPITOLUL I. NOTIUNI TEORETICE
In cautarea unor principii fundamentale ale elaborarii algoritmilor, backtraking este una dintre cele mai generale tehnici. Multe probleme care necesita cautarea unui set de solutii sau o solutie optima care sa satisfaca anumite restrictii pot fi rezolvate utilizand aceasta metoda. Denumirea backtraking (cautarea cu revenire) a fost utilizata pentru prima oara in anii '50 de catre D. H. Lehmer. Cei care au studiat procesul inaintea sa au fost: R. J. Walker (care i-a dat o interpretare algoritmica in 1960), S. Golomb si L. Bammert (care au prezentat o descriere generala a metodei, precum si varietatea de aplicabilitate a acesteia).
1. Prezentarea metodei
Aceasta metoda se aplica problemelor a caror solutie poate fi pusa sub forma unui vector x1, x2, . , xn in care x1A1, ., xn An sunt multimi finite si nevide si ale caror elemente se afla intr-o relatie de ordine bine stabilita. De multe ori multimile A1, ., An coincid.
Metoda backtraking construieste solutia problemei progresiv, obtinand pe rand elementele x1, x2, . , xn, netrecand la componenta xk pana cand nu s-au stabilit celelate componente, x1, . , xk-1.
Presupunem ca am generat deja elementele x1, . , xk. Urmatorul pas este generarea lui xk+1Ak+1. In acest scop se cauta in multimea Ak+1 urmatorul element disponibil. Exista doua posibilitati:
1. Sa nu existe un astfel de element in multimea Ak+1. In aceasta situatie se renunta
la ultimul xk ales, deci s-a facut un pas inapoi si in continuare se cauta generarea unui alt element xk din multimea Ak
2. Exista un xk+1 disponibil in multimea Ak+1. In aceasta situatie se verifica daca
acest element indeplineste conditiile ( conditii de continuare) cerute de enuntul problemei de a face parte din solutie.
Apar alte posibilitati.
Daca xk+1 ales indeplineste conditiile de continuare si poate face parte din solutie, atunci apar alte doua situatii:
2.1. Sa se fi ajuns la solutia finala a problemei si aceasta trebuie tiparita;
2.2. Sa nu se fi ajuns la solutia finala si atunci se considera generat xk+1, facand un
pas inainte la xk+2Ak+2.
Daca xk+1 nu indeplineste conditiile de continuare atunci se cauta urmatorul element disponibil in multimea Ak. Daca si ea se epuizeaza se face un pas inapoi renunzandu-se la xk
Observatie Problema se termina, cu tiparirea tuturor solutiilor, cand a fost epuizata multimea A1
Pentru a implementa aceasta metoda intr-un limbaj de programare, respectiv in C++ , se foloseste o structura de date de tip special (LIFO - last in first out), numita stiva, caracterizata prin faptul ca operatiile permise asupra ei se pot realiza la un singur capat numit varful stivei. Stiva se asimileaza cu un vector pe verticala si in ea se construieste solutia problemei.
Aceasta structura are nevoie de o variabila k care precizeaza in permanenta nivelul stivei.
Daca k = 0 se spune ca stiva este vida.
Daca k = n se spune ca stiva este plina.
Orice adaugare a unui element in stiva presupune cresterea nivelului stivei: k=k+1.
Orice eliminare a unui element din stiva presupune scaderea nivelului stivei :
k = k - 1.
Stiva pe care o folosim este o stiva simpla, avand capacitatea de a memora pe un anumit nivel o litera sau o cifra.
Metoda de programare backtracking admite atat o implementare interativa cat si una recursiva, folosind o serie de subprograme cu rol bine determinat, corpul lor de instructiuni depinzand de natura si complexitatea problemei.
2. Strategia generala backtraking in varianta iterativa
Se folosesc urmatoarele functii:
►Functia init (), de tip void - cu rolul de a initializa fiecare nivel k al stivei, cu o valoare neutra, care nu face parte din solutie, dar care permite, pentru fiecare componenta a solutiei, trecerea la primul element al domeniului sau de valori, ca si in cazul celorlalte, conform relatiei de ordine in care acestea se afla.
►Functia succesor (), de tip int - cu rolul de a gasi un succesor, adica de a cauta un nou element disponibil in multimea de valori a unei componete din solutie. Aceata functie va returna valoarea 1 daca exista succesor si valoarea 0 in caz contrar.
► Functiavalid (), de tip int - cu rolul de a verifica daca succesorul ales indeplineste conditiile de continuare. Aceata functie va returna valoarea 1 daca succesorul este valid ( respecta conditiile de continuare) si valoarea 0 in caz contrar.
► Functia tipar(), de tip void - cu rolul de a tipari o solutie determinata.
► Functia solutie(), de tip int - cu rolul de a verifica, la nivelul k al stivei, daca s-a ajuns la solutie sau nu, returnand, in mod corespunzator valoarea 1 sau 0.
Strategia generala backtraking se implementeaza in C, intr-o functie de tip void, in felul urmator:
void back()
if (as)
if solutie( ) tipar();
else
else k:=k-1;
}
}
Se folosesc variabilele intregi as si ev, cu semnificatia "am succesor", respectiv "este valid".
3. Recursivitatea
Recursivitatea este una din notiunile fundamentale ale informaticii. Utilizarea frecventa a recursivitatii s-a facut dupa anii '80. Multe din limbajele de programare evoluate si mult utilizate nu permiteau scrierea programelor recursive. In linii mari, recursivitatea este un mecanism general de elaborare a programelor. Ea a aparut din necesitati practice (transcrierea directa a formulelor matematice recursive) si reprezinta acel mecanism prin care un subprogram se autoapeleaza.
Un algoritm recursiv are la baza un mecanism de gandire diferit de cel cu care ne-am obisnuit deja. Atunci cand scriem un algoritm recursiv este suficient sa gandim ce se intampla la un anumit nivel pentru ca la orice nivel se intampla exact acelasi lucru.
Un algoritm recursiv corect trebuie sa se termine, contrar programul se va termina cu eroare si nu vom primi rezultatul asteptat. Conditia de terminare va fi pusa de programator.
Un rezultat matematic de exceptie afirma ca pentru orice algoritm iterativ exista si unul recursiv echivalent (rezolva aceasi problema) si invers, pentru orice algoritm recursiv exista si unul iterativ echivalent.
In continuare, raspundem la intrebarea: care este mecanismul intern al limbajului care permite ca un algoritm recursiv sa poata fi implementat? Pentru a putea implementa recursivitatea, se foloseste structura de date numita stiva.
Mecanismul unui astfel de program poate fi generalizat cu usurinta pentru obtinerea recursivitatii. Atunci cand o functie se autoapeleaza se depun in stiva:
● valorile parametrilor transmisi prin valoare;
● adresele parametrilor transmisi prin referinta;
● valorile tuturor variabilelor locale (declarate la nivelul functiei);
adresa de revenire la instructinea imediat urmatoare autoapelului.
4. Strategia generala backtraking in varianta recursiva
Metoda de programare backtraking are si o varianta recursiva. Prelucrarile care se fac pentru elementul k al solutiei se fac si pentru elementul k+1 al solutiei si aceste prelucrari se pot face prin apel recursiv. In algoritmul backtracking implementat iterativ, revenirea la nivelul k-1 trebuie sa se faca atunci cand pe nivelul k nu se gaseste o valoare care sa indeplineasca conditiile interne. In cazul implementarii recursive, conditia de baza este ca pe nivelul k sa nu se gaseasca o valoare care sa indeplineasca conditiile interne. Cand se ajunge la conditia de baza, inceteaza apelul recursiv si se revine la subprogramul apelant, adica la la subprogramul care prelucreaza elementul k-1 al solutieie, iar in stiva se vor regasi valorile prelucrate anterior in acest subprogram.
Intreaga rutina care implementeaza algoritmul backtracking recursiv se va transforma intr-o functie de tip void (procedurala) ce se va apela din programul principal prin back(1), avand ca parametru nivelul k al stivei; aceasta se va autoapela pe nivelele urmatoare ale stivei.
void back (int k)
Aceasta procedura functioneaza in felul urmator:
- se testeaza daca s-a ajuns la solutie; daca da, aceasta se tipareste si se revine la nivelul anterior;
-in caz contrar, se initiaza nivelul stivei si se cauta un succesor;
3 daca am gasit un succesor, se verifica daca este valid si daca da se autoapeleaza procedura pentru (k+1); in caz contrar, se continua cautarea succesorului;
4 daca nu exista succesor se revine la nivelul anterior (k+1) prin iesirea din procedura back.
O problema clasica este plasarea a n dame pe o tabla de sah astfel incat sa nu se atace reciproc, altfel spus, sa nu se afle doua dame pe aceeasi linie, pe aceeasi coloana sau diagonala.
Se numeroteaza liniile si coloanele de pe tabla de sah de la 1 la n. De asemenea, damele se numeroteaza de la 1 la n. Daca fiecare dama trebuie sa se afle pe randuri diferite, putem plasa dama k pe linia k, deci toate solutiile problemei pot fi reprezentate ca vectori (x1,x2,.,xn), unde xk este coloana unde este plasata dama k.
Rezulta ca domeniul solutiilor este format din nn vectori. Restrictiile problemei impun ca toate elementele xk sa fie diferite intre ele (toate damele sa se afle pe coloane diferite) si nici o dama sa nu fie pe aceeasi diagonala cu o alta dama. Prima din aceste doua restrictii presupune ca toate solutiile sunt permutari ale vectorului (1,2,3,.,n). Acest lucru reduce domeniul solutiilor de la nn la n! posibilitati.
A doua restrictie: pentru ca dama de pe linia i coloana xi sa fie pe aceeasi diagonala cu dama de pe linia k si coloana xk, triunghiul care se formeaza ar trebui sa aiba unghiurile de 450 , deci sa fie isoscel. Prin urmare catetele de lungimi i-k ,respectiv x1 - xk trebuie sa fie egale; conditia i - k ≠ xi - xk exprima faptul ca doua dame nu pot fi plasate pe aceeasi diagonala. Faptul ca nu pot fi plasate doua dame pe aceeasi coloana poate fi exprimat prin conditia x1≠ xk.
D
D
D
D
D
D
D
D
#incluse<iostream.h>
#include<math.h>
typedef int stiva[100];
int n,k,ev,as;
stiva st;
void init ()
int succesor ()
else
return 0;
int valid ()
int solutie ()
void tipar ()
Observatie: Problemele rezolvate prin aceasta metoda necesita un timp indelungat. Din acest motiv, este bine sa utilizam metoda numai atunci cand nu avem la dispozitie un alt algoritm mai eficient. Cu toate ca exista probleme pentru care nu se pot elabora alti algoritmi mai eficienti, tehnica backtracking trebuie aplicata numai in ultima instanta.
Fiind data o tabla de sah, de dimensiune n, xn, se cer toate solutiile de aranjare a n dame, astfel incat sa nu se afle doua dame pe aceeasi linie, coloana sau diagonala (damele sa nu se atace reciproc).
Exemplu: Presupunand ca dispunem de o tabla de dimensiune 4x4, o solutie ar fi urmatoarea:
D
D
D
D
Observam ca o dama trebuie sa fie plasata singura pe linie. Plasam prima dama pe linia 1, coloana 1.
D
A doua dama nu poate fi asezata decat in coloana 3.
D
D
Observam ca a treia dama nu poate fi plasata in linia 3. Incercam atunci plasarea celei de-a doua dame in coloana 4.
D
D
A treia dama nu poate fi plasata decat in coloana 2.
D
D
D
In aceasta situatie dama a patra nu mai poate fi asezata.
Incercand sa avansam cu dama a treia, observam ca nu este posibil sa o plasam nici in coloana 3, nici in coloana 4, deci o vom scoate de pe tabla. Dama a doua nu mai poate avansa, deci si ea este scoasa de pe tabla. Avansam cu prima dama in coloana 2.
D
A doua dama nu poate fi asezata decat in coloana 4.
D
D
Dama a treia se aseaza in prima coloana.
D
D
D
Acum este posibil sa plasam a patra dama in coloana 3 si astfel am obtinut o solutie a problemei.
D
D
D
D
Algoritmul continua in acest mod pana cand trebuie scoasa de pe tabla prima dama.
Pentru reprezentarea unei solutii putem folosi un vector cu n componente (avand in vedere ca pe fiecare linie se gaseste o singura dama).
Exemplu pentru solutia gasita avem vectorul ST ce poate fi asimilat unei stive.
Doua dame se gasesc pe aceeasi diagonala daca si numai daca este indeplinita conditia: |st(i)-st(j)|=|i-j| ( diferenta, in modul, intre linii si coloane este aceeasi).
ST(4)
ST(3) In general ST(i)=k semnifica faptul ca pe linia i dama ocupa pozitia k. ST(2)
ST(1)
Exemplu: in tabla 4 x4 avem situatia:
D
D
D
D
st(1)= 1 i = 1
st(3)= 3 j = 3
|st(1) - st(3)| = |1 - 3| = 2
|i - j| = |1 - 3| = 2
sau situatia:
D
D
D
D
st(1) = 3 i = 1
st(3) = 1 j = 3
|st(i) - st(j)| = |3 - 1| = 2
|i - j| = |1 - 3| = 2
Intrucat doua dame nu se pot gasi in aceeasi coloana, rezulta ca o solutie este sub forma de permutare. O prima idee ne conduce la generarea tuturor permutarilor si la extragerea solutiilor pentru problema ca doua dame sa nu fie plasate in aceeasi diagonala. A proceda astfel, inseamna ca lucram conform strategiei backtracking. Aceasta presupune ca imediat ce am gasit doua dame care se ataca, sa reluam cautarea.
lata algoritmul, conform strategiei generate de backtracking
- In prima pozitie a stivei se incarca valoarea 1, cu semnificatia ca in linia unu se aseaza prima dama in coloana.
- Linia 2 se incearca asezarea damei in coloana 1, acest lucru nefiind posibil intrucat avem doua dame pe aceeasi coloana.
- In linia 2 se incearca asezarea damei in coloana 2 , insa acest lucru nu este posibil, pentru ca damele se gasesc pe aceiasi diagonala (|st(1)-st(2)|=|1-2|);
- Asezarea damei 2 in coloana 3 este posibila.
- Nu se poate plasa dama 3 in coloana 1, intrucat in liniile 1-3 damele ocupa acelasi coloana.
Si aceasta incercare esueaza intrucat damele de pe 2 si 3 sunt pe aceeasi diagonala.
- Damele de pe 2-3 se gasesc pe aceeasi coloana.
- Damele de pe 2-3 se gasesc pe aceeasi diagonala.
- Am coborat in stiva mutand dama de pe linia 2 si coloana 3 in coloana 4.
Algoritmul se incheie atunci cand stiva este vida. Semnificatia procedurilor utilizate este urmatoarea:
INIT - nivelul k al stivei este initializat cu 0;
SUCCESOR - mareste cu 1 valoarea aflata pe nivelul k al stivei in situatia in care aceasta este mai mica decat n si atribuie variabilei EV valoarea TRUE, in caz contrar, atribuie variabilei EV valoarea FALSE;
VALID - valideaza valoarea pusa pe nivelul k al stivei, verificand daca nu avem doua dame pe aceeasi linie (st(k)=st(i)), sau daca nu avem doua dame pe aceeasi diagonala (st(k)-st(i)=|k-i|)caz in care variabilei EV i se atribuie FALSE; in caz contrar, variabilei EV i se atribuie TRUE;
SOLUTIE - verifica daca stiva a fost completata pana la nivelul n inclusiv;
TIPAR - tipareste o solutie.
Se considera n piese de domino, memorate ca n perechi de numere naturale in fisierul text domino1.txt. Primul numar al perechii reprzinta valoarea jumatatii superioare a pisei, iar al doilea numar reprezinta valoarea jumatatii inferioare.
Se cere sa se afiseze, in fisierul text domino2.txt, toate solutiile de asezare a acestor piese intr-un lant domino de lungime a, fara a roti piesele.
Un lant domino se alcatuieste din pise domino astfel incat o piesa este urmata de o alta a carei prima jumatate coincide cu a doua jumatate a piesei curente.
Programul C++ corespunzator este:
#include<iostream.h>
struct piese
piese domino[20];
int st[20],n,sol,k,as,ev,a,i;
void init()
int succesor()
else return 0;
int valid()
return 1;
int solutie()
void tipar ()
cout<<endl;
void lant()
if (as)
if(solutie())
tipar();
else
else k--;
}
void main()
cout<<'dati lungimea lantului de piese:';
cin>>a;
lant();
cout<<sol;
Pentru urmatorul set de date de intrare:
n=4;
piesa 1: 1 2
piesa 2: 2 3
piesa 3: 3 1
piesa 4: 1 3
a=3
pe ecran vor fi afisate urmatoarele solutii:
Lant domino, nr.1
1 22 33 1
Lant domino, nr.2
2 33 11 2
Lant domino, nr.3
2 33 11 3
Lant domino, nr.4
3 11 22 3
Lant domino, nr.5
1 33 11 2
5 solutii
Pentru comoditatea folosirii programului si pentru teste diverse ale datelor, se pot folosi fisierele text atat pentru citirea datelr de intrare cat si pentru afisarea rezultatelor.
In programul urmator se foloseste ca fisier de intrare domino1.txt, cu urmatorul continut:
4
1 2
2 3
3 1
1 3
3
unde pe primul rand se afla n, numarul total de piese, pe urmatoarele n randuri se afla perechile de numere ce alcatuies pisele, separate prin spatiu, iar pe ultimul rand se afla a, lunimea lanturilor cerute.
#include<iostream.h>
#include<fstream.h>
struct piese
piese domino[20];
int st[20],n,sol,k,as,ev,a,i;
ifstream f('domino1.txt');
ofstream g('domino2.txt');
void init()
int succesor()
else return 0;
int valid()
return 1;
int solutie()
void tipar ()
g<<endl;
void lant()
if (as)
if(solutie())
tipar();
else
else k--;
}
void main()
f>>a;
lant();
g<<sol<<'solutii';
f.close(); g.close();
In urma rularii acestui program se va crea fisierul text domino2.txt, cu urmatorul continut:
Lant domino, nr.1
1 22 33 1
Lant domino, nr.2
2 33 11 2
Lant domino, nr.3
2 33 11 3
Lant domino, nr.4
3 11 22 3
Lant domino, nr.5
1 33 11 2
5 solutii
Balanescu, T., Gavrila, S., Georgescu, H., Gheorghe, M., Sofonea, L., Vaduva, I., Limbajul C++. Concepte fundamentale-volumul I, Editura Tehnica, Bucuresti, 1992;
Cristian Udrea, Informatica(Teorie si aplicatii)-Vol II (Clasa a X-a), Editura Arves, 2002;
Tudor, Sorin, Informatica (Tehnici de programare)- Manual pentru clasa a X- a,Varianta C++, Editura L&S Infomat, Bucuresti, 2002;
Tudor, Sorin, Informatica. Varianta C++ - Manual pentru clasa
a XI- a, Editura L&S Infomat, Bucuresti, 2002;
Stelian Niculescu, Emanuela Cerchez, Bacalaureat si atestat - Editura L&S Informat, 1999;
Doina Roncea, Limbajul C++, Editura Libris, 2004;
Atanasiu Adrian, Pintea Rodica, Culegere de probleme Pascal/C++, Editura Petrion, Bucuresti 2006.
