TEHNICA BACKTRACKING

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=x₁x₂,....,x_n cu x₁I A₁, x₂ I A₂, ...., x_n I A_n ;

Multimile A₁, A₂, ...., A_n 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;

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

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

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