1. 1. Metoda backtracking
2. 2. Metoda backtracking Clasificarea metodelor de programare Definiie Exemple de probleme Problema celor N dame: Metoda Implementarea
3. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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