Referat Tehnica BackTracking

Mai jos puteti citi fragmente din Referat Tehnica BackTracking si de asemenea puteti face Download Referat Tehnica BackTracking

Citeste fragmente din Referat Tehnica BackTracking

T E H N I C A B A C K T R A C K I N G PREZENTAREA TEHNICII BACKTRACKING: Aceasta tehnica se foloseste in rezolvarea problemelor care indeplinesc simultan urmatoarele conditii: Solutia lor poate fi pusa sub forma unui vector S=x1x2,……..,xn cu x1( A1, x2 ( A2, …….., xn ( An ; Multimile A1, A2, …….., An sunt multimi finite, iar elementele lor se considera ca se afla intr-o relatie de ordine bine stabilita; Nu se dispune de o alta metoda de rezolvare, mai rapida; Aceasta tehnica presupune trei functii: Functia de citire a valorile cunoscute; Functia de tiparire a solutiilor; Functia backtracking. Schema generala a procedurii backtracking: Void back (int k) Int I, cont; { if (k=n+1) tipar ( ); else for (i=1; i=n; i++) { a[k]=i; cont=1; pentru cazul prost CONT ia valoarea FALS: cont=0; if (cont = = 1) back (k+1); } } Programele prezentate mai jos, in pseudocod, sunt: Paranteze; Comis-voiajor; Dame; Submultimi; Magazin; Permutari. PROGRAME IN PSEUDOCOD Paranteze: se da un numar natural par n. Sa se determine toate sirurile de n paranteze care se inchid corect. procedura tipar j nr natural pentru p < - 1,n executa // afisarea solutiilor daca a[p]<-1 atunci scrie “)” // conditie pt afisarea parantezelor inchise // de la daca altfel scrie “(” // de la pentru procedura back (k nr natural) cont, i, d, j nr naturale daca k=n+1 // conditie pentru afisare atunci tipar // de la daca altfel pentru i <-0,1 executa a[k]<-1 cont <-1 daca k=1 atunci daca a[k]=1 atunci cont <- 0 // conditie pentru panateza ( // de la daca a[k]=1 // de la daca k=1 daca k=n atunci daca a[k]=n atunci cont <- 1 // conditie pentru paranteza ) // de la daca a[k]=n // de la daca k=n d<-0 // numara cate paranteze inchise sunt pentru j <-1,k executa // de la 1 pana la pozitia la care s-a ajuns executa daca a[j]=0 atunci d <- d+1 // daca gaseste o paranteza inchisa atunci d creste // de la daca // de la pentru (j) daca d>n/2 atunci cont <- 0 // conditie pt ca nr. de paranteze inchise sa nu fie mai mare de n/2 // de la daca daca k-d>d atunci cont <- 0 // conditie pt ca diferenta dintre pozitia la care s-a ajuns (k) si nr. de paranteze inchise sa nu fie mai mare de numarul de paranteze inchise // de la daca daca cont=1 atunci back (k+1) // apelarea recursiva a procedurii back (cu parametru ) //de la daca //de la pentru (i) programul principal se citeste n ( n nr natural ) back (1) // apelarea procedurii back pentru k=1 exemplu: date de intrare: n=6 date de iesire : ( ( ( ) ) ), ( ( ) ( ) ), ( ) ( ) ( ), ( ) ( ( ) ), ( ( ) ) ( ) Un comis voiajor porneste din orasul 1 si trebuie sa treaca prin toate cele n-1 orase ramase astfel incat sa nu treaca de 2 ori prin acelasi oras si sa se intoarca in orasul 1. Se citesc legaturile dintre cele n orase cu ajutorul unui matrice de adiacenta cu n linii si n coloane. procedura tipar j nr natural pentru j <- 1,n executa // tiparirea solutiilor scrie a[j] // de la pentru procedura back (k nr intreg) i,t,cont nr intregi daca k=n+1 // conditie pt tiparirea solutiilor atunci tipar // de la daca altfel pentru i <- 1,n executa a[k] <- i cont <-1 daca k>1 pentru t <-1,k-1 daca a[k]=a[t] // conditie pt orase distincte atunci cont <- 0 // de la daca // de la pentru (t) daca a[m[k-1][k]] =0 // conditie pt ca intre 2 orase sa existe drum atunci cont <- 0 // de la daca daca a[m[n][1]]=0 // conditie pt ca intre ultimul si primul oras sa existe drum atunci cont <- 0 // de la daca // de la daca (k>1) daca cont=1 atunci back(k+1) // apelarea recursiva a procedurii back (cu parametru ) // de la daca // de la pentru (i) program principal citeste n (n nr natural) pentru b<-1,n (b nr natural) // citirea matricei de adiacenta pentru c<- 1,n (c nr natural) scrie m[b][c] (valori naturale) // de la pentru (c<-1,n) // de la pentru (b<-1,n) back(1) // apelarea procedurii back (pt k=1) exemplu : date de intrare : 4 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 date de iesire : 1 2 3 4 1 3 2 4 Se dau n dame si se cere sa fie asezate pe o tabla de sah (n x n ) astfel incat ele sa nu se atace. procedura tipar i nr natural pentru i <- 1,n executa // tiparirea solutiilor scrie a[i] // de la pentru procedura back (k nr intreg) t, i, cont nr intregi daca k=n+1 // conditie pt tiparirea solutiilor atunci tipar // de la daca altfel pentru i <-1,n executa a[k]<-i cont<-1 daca k>1 pentru t <-1,k-1 executa daca a[k]=a[t] sau ( a[k]-a[t] ( = ( k-t ( // conditii pt ca damele sa nu se atace atunci cont <-0 // de la daca // de la pentru (t) // de la daca (k>1) daca cont <-1 atunci back(k+1) // apelarea recursiva a procedurii back ( cu parametru ) // de la daca // de la pentru (i) program principal citeste n (nr natural) back (1) // apelarea procedurii back (pt k=1) exemplu : date de intrare : 4 date de iesire : 2 4 1 3 3 1 4 2 Aflati toate submultimile care sunt incluse intr-o multime data. Se citesc nr de elemente ale multimii si elementele sale. procedura tipar j nr natural pentru j <- 1,n executa daca a[j]=1 // conditie pt tiparirea solutiilor scrie m[j] // tiparirea solutiilor // de la daca // de la pentru procedura back (k nr natural) cont, i nr naturale daca k=n+1 // conditie pt tiparirea solutiilor atunci tipar // de la daca altfel pentru i <- 0,1 executa a[k] <-i cont <-1 daca cont =1 // nu sunt conditii de continuare atunci back (k+1) // apelarea recursiva a procedurii back ( cu paremetru ) // de la daca // de la pentru programul principal citeste n ( nr natural ) pentru x <-2,n (x nr natural) citeste m[x] ( valori naturale) // de la pentru back(1) // apelarea procedurii back (pt k=1) exemplu : date de intrare : 3 1 4 7 date de iesire : 7, 4, 4 7, 1, 1 7, 1 4, 1 4 7 Un copil intra intr-un magazin de jucarii. El are o suma s de bani si doreste sa-si cumpere cat mai multe jucarii. Sa se cate produse diferite poate cumpara copilul stiind ca in magazin se afla n produse, fiecare avand cate un pret dat. procedura tipar (k nr natural) pentru i <- 1,k-1 executa scrie a[i] // tiparirea solutiilor // de la pentru procedura back(k nr natural, suma nr intreg) t, i, cont nr naturale daca s=suma // conditia pt tiparirea solutiilor atunci tipar(k) // apelarea procedurii tipar (cu parametru ) // de la daca altfel pentru i <- 1,n executa a[k]<-i cont<-1 daca k>1 pentru t <-1, k-1 daca a[k]<=a[t] // conditie pt a nu se repeta produsele in cadrul aceleiasi solutii atunci cont <-0 // de la daca // de la pentru (t) // de la daca (k>1) daca suma>s // conditie pt ca preturile produselor (suma) < suma disponibila (s) atunci cont <-0 // de la daca daca cont=1 atunci back(k+1, suma+p[a[k]]) // apelarea recursiva a procedurii back // suma+p[a[k]] reprezinta suma anterioara + pretul produsului a[k] // de la daca // de la pentru (i) programul principal citesc s (nr intreg) citesc n (nr natural) pentru j <- 1,n executa citesc p[j] (valori intregi) // se citesc preturile produselor // de la pentru back (1,0) // apelarea procedurii back (pt k=1 si suma=0) exemplu : date de intrare : 100, 5 5, 80, 15, 20, 85 date de iesire : 1 2 3 2 4 3 5 PAGE 1 PAGE 7 쥁`