Post on 04-Oct-2015
description
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]