METODE DE ELABORARE A ALGORITMILOR. BACKTRACKING.

Metode de elaborare a algoritmilor. Backtracking.

Metoda Backtracking (cautare cu revenire) este o metoda generala de rezolvare a unei clase de probleme de optimizare bazata pe principiul construirii solutiilor, in mod treptat, prin alegeri succesive ale solutiilor partiale. Spre deosebire de metoda Greedy, bazata pe acelasi principiu, Backtracking ofera posibilitatea revenirii asupra unor decizii anterioare, fapt care conduce la obtinerea solutiilor optime globale in orice situatie. In plus, daca sunt mai multe solutii, metoda le determina pe toate.

Metoda cautarii cu revenire realizeaza o explorare sistematica a spatiului solutiilor posibile, construieste solutiile finale, fara a genera insa toate solutiilor posibile din care s-ar putea extrage doar acele solutii ce indeplinesc conditii specifice problemei. Un dezavantaj major al metodei este acela ca este o metoda relativ costisitoare in privinta timpului de executie.

Problemele rezolvabile cu metoda Backtracking sunt probleme in care solutia este reprezentata sub forma unui vector:

,

unde si sunt multimi finite nu neaparat distincte.

Cerinta problemei este determinarea tuturor solutiilor posibile, care satisfac anumite conditii specifice problemei (denumite conditii interne).

O abordare simplista ar genera toate solutiile posibile - elementele produsului cartezian , si ulterior s-ar verifica aceste solutii in vederea identificarii acelora care verifica conditiile interne. Abordarea aceasta este neeficienta. Generarea tuturor solutiilor implica memorie si timp suplimentar. Backtracking este o alternativa inspirata de rezolvare a problemelor de acest gen. Metoda evita generarea tuturor solutiilor posibile, solutiile finale se obtin prin alegerea succesiva de elemente din multimile , , ., cu posibilitatea revenirii asupra unei alegeri daca aceasta nu a condus la obtinerea unei solutii finale.

Algoritmii Backtracking pornesc cu o solutie initiala reprezentata de vectorul vid. Ulterior acesta va fi marit prin adaugarea elementelor din multimea corespunzatoare , treptat pentru k=1,2,.. Daca vectorul partial verifica anumite conditii de validare, deduse din conditiile interne, se va continua cu augmentarea vectorului curent prin adaugarea unui nou element din multimea corespunzatoare . Daca vectorul nu indeplineste conditiile de validare se incearca un nou element din multimea si se reverifica conditiile de validare. Exista posiblitatea ca sa nu mai contina alte elemente care au ramas neverificate, ceea ce produce o revenire la o decizie anterioara si incercarea unui alt element pe pozitia anterioara k-1 din vector.

Asupra vectorului solutie se actioneaza prin doar doua operatii: adaugare nou element dupa ultimul adaugat, respectiv, eliminare ultim element adaugat. Aceste operatii corespund unor operatii cunoscute: push si pop; astfel, vectorul solutie functioneaza pe principiul unei stive.

O problema se identifica ca o problema rezolvabila prin metoda Backtracking daca putem identifica urmatoarele aspecte din specificatiile sale:

spatiul solutiilor este un produs cartezian

solutia probleme poate fi reprezentata ca un vector

exista un set de conditii prin care putem decide daca o solutie partiala data de vectorul , este valida → conditiile de validitate

exista un set de conditii prin care putem decide daca o solutie partiala este finala → conditiile de finalitate

solutia (vectorul) se poate construi pas cu pas, astfel incat daca este valid, are sens completarea vectorului cu un element pe pozitia k+1.

Consideram solutia partiala reprezentata ca stiva in imaginile alaturate:

Cazul 1

Cazl 2.1

Cazul 2.2

Tratarea nivelului k se face diferentiat pentru cazurile urmatoare:

Cazul 1. verifica conditiiile de validitate: in acest caz se va trece la completarea nivelului urmator al stivei cu un element din . (operatie push). Daca vectorul partial verifica si conditiile de finalitate se va furniza solutia.

Cazul 2. NU verifica conditiile de validitate si:

Cazul 2.1. mai exista elemente din care nu au fost incercate, atunci:

- se alege alt element neincercat din si se reverifica conditiile de validitate.

Cazul 2.2 Nu mai exista elemente din ramase neincercate, atunci:

- se revine pe nivelul anterior k-1 (operatie pop).

Procesul este unul repetitiv, pentru fiecare nivel curent al stivei se va proceda similar. Descrierea algoritmului se poate face in doua variante: iterativ si recursiv, si in ambele situatii vom considera subalgoritmii de tip functie prin care se verifica conditiile de validitate respectiv de finalitate pentru o solutie partiala oarecare .

Functie Valid(k) este:

//verifica daca solutia partiala din stiva este valida sau nu

//intoarce Adevarat sau Fals in functie de rezultatul testului

SfFunctie

Functie Final(k) este:

//verifica daca solutia partiala este finala sau nu

//intoarce Adevarat sau Fals in functie de rezultatul testului

SfFunctie

Varianta Iterativa:

Algoritm BackTrackingIterativ este:

k=1 //initializarea nivelului stivei

Cattimp (k≥1)

Daca ( "neincercat" ) atunci

//operatia push

Daca Valid(k)=Adevarat atunci

Daca Final(k)=Adevarat atunci

Tipareste "Solutie:" Stiva

Altfel

k=k+1 //trece la alt nivel

SfDaca

SfDaca

Altfel

//operatia pop

k=k-1 //revine la nivelul precedent

SfDaca

SfCattimp

SfAlgoritm

Varianta recursiva:

Subalgoritm Backtracking( k) este: //trateaza nivelul k

Pentru fiecare

//operatia push

Daca Valid(k)=Adevarat atunci

Daca Final(k)=Adevarat atunci

Tipareste "Solutie:" Stiva

Altfel

Cheama Backtracking( k+1) //autoapel

SfDaca

SfDaca

SfPentru

SfSubalgoritm

Observatie: In varianta recursiva, operatiile pop (revenirea pe un nivel inferior al stivei solutie) se executa automat la revenirile din apelurile subalgoritmului.

Pentru furnizarea solutiilor, se va apela:

Cheama Backtracking (1).

Problema 1. Problema damelor. Se da o tabla de sah de n linii si n coloane. Avand n regine, se cer toate solutiile de aranjare a reginelor pe tabla de sah, astfel incat oricare doua piese de acest tip sa nu se atace.

Analiza problemei:

Pornind de la observatia ca doua dame se ataca in conditiile in care ambele se situeaza: fie pe aceiasi linie, fie pe aceiasi coloana, fie pe o diagonala a tablei de sah, putem deduce o varianta simplificata de reprezentare a unei solutii prin impiedicarea oricaror dame de a fi situate pe aceiasi coloana. Consideram astfel ca dama k este blocata sa ocupe coloana k a tablei de sah. Astfel, oricare doua dame sunt pozitionate pe coloane distincte si solutia finala poate fi reprezentata printr-un vector de n elemente astfel incat:

k- reprezinta indicele coloanei pe care se afla dama k

Stiva[k] - elementul din stiva este indicele liniei ocupate de dama k

Practic, pozitia in stiva: k - corespunde atat indicelui de coloana cat si identificatorului damei, iar valoare de pe nivelul k din stiva coincide cu numarul liniei ocupate de dama k.

Spatiul solutiilor posibile este produsul cartezian: , unde A=.

Solutia este reprezentata printr-un vector (stiva).

Conditiile ca o solutie partiala sa fie valida se reduc la a verifica daca a k-a dama nu ataca oricare din damele pozitionate pe primele k-1 coloane.

O solutie este finala daca s-a reusit pozitionarea tuturor damelor, respectiv, dimensiunea vectorului construit este n (s-a completat nivelul n al stivei)

Daca pe tabla de sah sunt dispuse k-1 dame astfel incat acestea nu se ataca (solutie partiala valida), se poate trece la pozitionarea celei de-a k-a piesa.

Pe baza consideratiilor 1-5 problema 1 se poate rezolva printr-un algoritm Backtracking. Algoritmul general descris anterior nu se modifica, in schimb vor fi detaliate functiile Valid si Final:

Functie Valid(k) este

//verifica daca a k-a dama ataca damele 1,2,.,k-1

Valid=Adevarat

Pentru i de la 1 la k-1

Daca () SAU ( (k-i)=() ) atunci

/ damele k si i sunt situate pe aceiasi linie sau pe aceiasi diagonala

Valid=Fals

SfDaca

SfPentru

SfFunctie

Functie Final(k) este:

Daca k=n atunci

// am ajuns la nivelul n al stivei - s-au pozitionat toate cele n regine

Final=Adevarat

Altfel

Final=Fals

SfDaca

SfFunctie

Rezolvare1: Programul C pentru rezolvarea problemei damelor (varianta nerecursiva)

#include <math.h>

int stiva[100]; //solutia se construieste in stiva

int nrsolutii;

int n;

int valid(int k)

int final(int k)

void tipareste()

void main()

}

if (gasit==0) //nu s-au mai gasit

else

if (final(k)==1)

else

k=k+1;

}

printf('n Numarul de solutii=%d',nrsolutii);

Rezolvare2: Programul C pentru rezolvarea problemei damelor (varianta recursiva)

#include <math.h>

int stiva[100]; //solutia se construieste in stiva

int nrsolutii;

int n;

int valid(int k)

int final(int k)

void tipareste()

void dame(int k)

void main()