2. Metoda backtracking Clasificarea metodelor de programare
Definiie Exemple de probleme Problema celor N dame: Metoda
Implementarea
3. Scop indentificarea problemelor pentru care trebuie
enumerate toate soluiile ,fiecare soluie fiind format din n
elemente,care aparine unei mulimi finite A i care trebuie s
respecte anumite condiii interne. Acest metoda construieste
progresiv vectorul soluiei,pornind de la primul element si adaugnd
la vector urmatoarele elemente,cu revenire la elementul anterior
din vector,in caz de insucces.
4. Clasificarea metodelor de programare Algoritmi recursivi
simpli Algoritmi Backtracking Algoritmi Divide et Impera Algoritmi
de programare dinamic Algoritmi Greedy Algoritmi Branch and
bound
5. Backtracking - definiie S presupunem c trebuie s luai o
serie de decizii, avnd mai multe variante de ales, unde Nu avei
destule informaii pentru a ti ce alegei Fiecare decizie ne conduce
la un nou set de variante posibile Unele succesiuni de variante
(posibil mai multe dect una) poate fi soluia problemei tale
Backtracking este o metod ce ncearc diferite succesiuni de decizii,
nainte de a gsi una care merge
6. Rezolvarea unui labirint ntr-un labirint de dimensiune m*n,
gasii o cale de a l parcurge de la nceput la sfrit La fiecare
intersecie trebuie s decidei ntre 3 sau mai multe variante: S
mergei nainte S mergei la stnga S mergei la dreapta Nu avei destule
informaii pentru a alege corect Fiecare alegere duce la un nou set
de alegeri Una sau mai multe secvene de variante poate (sau nu) s
conduc la o soluie Multe tipuri de labirinturi se pot rezolva cu
backtracking
7. Colorarea hrii Dorii s colorai o hart n 4 culori: Rou,
galben, albastru i verde Oricare 2 ri vecine trebuie s fie colorate
n culori diferite Nu avei destule informaii pentru a ti ce culori
alegei Fiecare decizie ne conduce la un nou set de variante
posibile Una sau mai multe secvene de variante poate (sau nu) s
conduc la o soluie Multe tipuri de colorri de hri se pot rezolva cu
backtracking
8. Rezolvarea unui puzzle n acest puzzle toate gurile nafar de
una sunt colorate cu aceai culoare Poi sri doar de pe o gaur pe
alta Gurile pe care sari se elimin Obiectul este de a elimina toate
gurile inafar de una Nu avei destule informaii pentru a sri corect
Fiecare decizie ne conduce la un nou set de variante posibile Una
sau mai multe secvene de variante poate (sau nu) s conduc la o
soluie Multe tipuri de puzzle-uri se pot rezolva cu
backtracking
9. Implimentarea metoda backtracking Pentru implimentarea se
folosesc structuri de date si subprograme. Pentru a memora
elementele x ale soluiei se foloseste structura de date de tip
stiv. Aici mai putem folosi i variabile de memorie: as - este o
variabil logic care are valoare 1-true i 0-false; ev pentru a tii
dac succesorul gsit respect condiia de continuare i poate fii
elemnetul x al soluiei; n- pentru dimensiunea soluiei.
10. Subprograme Algoritmul va fii implimentat prin: un
subprogram - este acelai pentru toi algoritmii de rezolvare prin
metoda backtracking i care descrie strategia general backtracking i
subprogramele care au aceeai semnificaie pentru toi algoritmi,dar
al cror coninut difer de la o problem la alta,depinznd de condiiile
intrene ale soluiei; Subprogramul int ; Subprogramul succesor;
Subprogramul valid; Subprogramul soluie; Subprogramul tipar.
11. Subprogramul int se iniializeaz elementul din vrful stivei,
n acestest element se va inregistra urmtorul element al soluiei.
Subprogramul succesor - verific dac mai exist in mulimea A un
element pentru nivelul k al soluiei. Subprogramul valid - verific
dac valoarea atribuit elementului x al soluiei indeplineste
,condiia de contnuare,adic poate fii considerat ca face parte din
soluia problemei. int valid ( ) {for int (int i=1;i
12. Problemele rezolvabile prin metoda backtracking Metoda
backtracking este recomandat in cazul problemelelor care au
urmtoarele caracteristici: 1. Se cere gsirea tuturor soluiilor
posibile 2. Nu se cunoate un algoritm mai eficient