back standard

1

PAGE 13Informatica clasa a XI-a - Suport de curs

METODA BACKTRACKING STANDARD1. Mecanism generalApare frecvent situaia n care rezolvarea unei probleme conduce la determinarea unor vectori soluie de forma X=(x1, x2,,xn) n care :

fiecare component a vectorului soluie aparine unei mulimi finite de valori Vi exist anumite relaii care trebuie satisfcute de componentele vectorului, numite condiii interne, astfel nct X este soluie dac i numai dac componentele sale satisfac aceste condiii interne

Exemplu:

Fie dou mulimi de litere V1={A,B,C} i V2={M,N}. Se cere s se determine acele perechi (x1,x2) cu x1(V1 i x2(V2 cu proprietatea c dac x1({A,B} atunci x2(N.

Soluiile care satisfac condiia impus sunt : {A,M},{B,M},{C,M},{C,N}.

Produsul cartezian V1xV2x.Vn se numete spaiul soluiilor posibile. Soluiile problemei sunt acele soluii posibile care ndeplinesc condiiile interne. Exemplu:

Fie un joc Pronosport n care sunt n discuie doar 4 meciuri. O persoan dorete s joace, plecnd cu convingerea c n variantele ctigtoare nu pot exista mai mult de dou meciuri nule (pronostic 0), iar la ultimul meci gazdele nu ctig. Persoana dorete s gseasc toate variantele care ndeplinesc aceste condiii.

n acest problem V1=V2=V3=V4={0,1,2}. Exist mai muli vectori care ndeplinesc condiiile interne : (0,1,2,0),(1,2,1,2),.

O modalitate de rezolvare ar fi s se genereze pe rnd cele 34=81 soluii posibile i s se aleag cele care satisfac condiiile interne. Aceast metod este inacceptabil pentru c se consum prea mult timp. Metoda backtracking evit generarea tuturor soluiilor posibile, scurtnd timpul de lucru.

Componentele vectorului primesc valori n ordinea cresctoare a indicilor. Astfel, xk primete valori numai dup ce x1,x2,.xk-1 au primit valori care nu contrazic condiiile interne. n plus, valoarea lui xk trebuie aleas astfel nct, vectorul soluie parial x1,,xk s ndeplineasc i el anumite condiii, numite condiii de continuare, i care sunt derivate din condiiile interne. Astfel, pentru exemplul anterior, dac x1=x2=0 (meci nul), atunci x3 nu mai poate primi valoarea 0.

Nendeplinirea condiiilor de continuare exprim faptul c oricum am alege n continuare valori pentru componentele xk+1,..,xn, nu vom obine o soluie. Stabilirea condiiilor de continuare este foarte important, o alegere bun ducnd la o reducere considerabil a numrului de calcule.

Prin backtracking, orice vector soluie este construit progresiv, ncepnd cu prima component i mergnd ctre ultima, cu eventuale reveniri asupra valorilor atribuite anterior. Componentele x1,x2,.xn iau valori n mulimile V1,V2,.Vn. Prin atribuiri reuite sau ncercri de atribuiri euate din cauza nerespectrii condiiilor de continuare, anumite valori sunt consumate. Pentru o component xk din vectorul soluie, notm cu Ck(Vk mulimea valorilor consumate la momentul curent. Putem descrie metoda backtracking utiliznd o configuraie de forma :

x1 x2xnC1 C2Cn

n cursul aplicrii metodei backtracking, o configuraie poate fi obiectul a patru tipuri de modificri i anume :

a) Atribuie i avanseaz : are loc atunci cnd pentru xk mai sunt valori neconsumate (Ck(Vk) i valoarea aleas pentru xk (fie ea vk) satisface condiiile de continuare. n acest caz, xk primete valoarea respectiv care se adaug la mulimea valorilor consumate i se avanseaz la componenta xk+1 :

xk( vkCk( Ck ( {vk}

K(k+1

b) ncercare euat : are loc atunci cnd pentru xk mai sunt valori neconsumate, dar valoarea aleas (fie ea vk) nu satisface condiiile de continuare. n acest caz, valoarea respectiv se adaug la mulimea valorilor consumate Ck dar nu se avanseaz la componenta urmtoare :

Ck( Ck ( {vk}

c) Revenire : are loc atunci cnd toate valorile pentru xk au fost consumate (Ck=Vk) i nu s-a putut avansa la xk+1 pentru c nu sunt satisfcute condiiile de continuare. n acest caz, se anuleaz valorile consumate pentru componenta xk i se revine la componenta xk-1 n ncercarea de a-i atribui acesteia o alt valoare care s permit continuarea construirii vectorului soluie:

Ck((K(k-1

d) Revenire dup construirea unei soluii : are loc atunci cnd toate componentele vectorului au primit valori care satisfac condiiile interne, adic s-a construit o soluie. n acest caz se revine la ultima component (xk,k=n) ncercnd s-i atribuim o nou valoare (dac mai exist) pentru construirea altor soluii.

Condiia k=n+1 este utilizat n practic pentru a sesiza momentul n care s-a construit o soluie. Condiia k=0 (adic C1=V1,..,Cn=Vn) este utilizat n practic pentru a sesiza finalul procesului de construire a soluiilor, adic ncheierea algoritmului backtracking.

Algoritmul corespunztor metodei backtracking este urmtorul :

*iniializeaz mulimile de valori V1, V2,,Vn

k=1; Ci=( , (() i=1,..,n // configuraia iniial

ct_timp k>0 // configuraia nu este final dac k=n+1 // configuraie de tip soluie

atunci reine soluia X=(x1,,xn)

k=k-1 // revenire dup construirea unei soluii

altfel

dac Ck(Vk // mai sunt valori neconsumate

atunci alege o valoare vk din (Vk-Ck)

Ck=Ck({vk} //adauga vk la valorile consumate dac (x1,..,xk) satisfac cond. de continuare

atunci xk=vk // atribuie

k=k+1 // avanseaz altfel

// nimic; ncercare euat

sfrsit_dac

altfel

Ck=( // anulam valorile consumate

k=k-1 // revenire

sfrsit_dac

sfrsit_dac

sfrsit_ct_timp

2. Varianta iterativ standard a metodei backtracking

Programarea algoritmului backtracking se simplific mult dac mulimile n care pot lua valori componentele vectorului sunt identice cu mulimea finit S={1,2,.,s} adic cu primele s numere naturale. Majoritatea problememlor rezolvabile prin backtracking permit o codificare a datelor de intrare astfel nct acestea s concid cu primele s numere naturale (inclusiv 0). n acest caz, funcia care implementeaz mecanismul backtracking este :

void Back()

{

int k,i;

k=1;

while(k>0) // mai sunt solutii posibile

if(k==n+1) // am obtinut o solutie { Retsol(); k--;}

// revenire dupa constr. unei solutii

else

if(x[k]