7.2.metoda backtracking

Metoda BACKTRACKINMetoda BACKTRACKINGG

Notiuni teoreticeNotiuni teoretice

Această metodă de programare se foloseşte în cazul problemelor a caror soluţie se prezintă sub forma x1, x2, ..., xi, ...xn.O metodă simplă de determinare a soluţiilor rezultat constă în a genera într-un mod oarecare toate soluţiile posibile şi de a verifica dacă ele satisfac condiţiile interne. Dezavantajul consta în faptul că timpul cerut de aceasta investigare exhaustiva este foarte mare, el este de ordinul 2^n, deci exponenţial.Metoda determină aceste şiruri de soluţii prin încercări succesive de extindere a unei soluţii parţiale. În fiecare etapă a căutării pentru care nu este posibilă o extindere a soluţiei partiale curente, se revine la o soluţie parţială anterioara şi se încearcă din nou. În mod curent metoda este utilizată pe scara largă pentru rezolvarea problemelor combinatorice din domeniul analizei sintactice, jocurilor şi optimizărilor.

Condiţiile îndeplinite simultan pentru rezolvarea problemelor cu această metodă sunt:• soluţia lor poate fi pusa sub forma de vector S=x1,x2...xn cu xi Ai, unde i=1,n;• mulţimile A1,A2,...An sunt mulţimi finite, cu elemente într-o relaţie de ordine bine stabilită;• nu se dispune de o alta soluţie mai rapidă

Se fac următoarele observaţii:• nu la toate problemele n este cunoscut;• x1,x2,...xn pot fi la randul lor vectori;• în multe probleme A1,A2,...An coincid

Metoda backtrading constă în următorul algoritm:

1. se alege primul element x1 din A1;2. se presupun generate elementele x1,...xk aparţinând mulţimilor A1,...Ak se al

ege (dacă există) xk+1 primul element disponibil din multimea Ak+1 care îndeplineşte anumite condiţii de continuare, aparând astfel 2 posibilităţi:• elementul exista – se testeaza dacă nu s-a ajuns la o soluţie, în caz afirm

ativ aceasta se tipăreşte, în caz contrar se consideră generate x1,x2,...xk, xk+1

• elementul nu există – situaţie în care se consideră generate elementele x1,x2,...,xk-1 reluându-se căutarea de la elementele urmatoare lui xk în multimea Ak

3. algoritmul se incheie când au fost luate in consideratie toate elementele multimii A1.

Algoritmul poate fi descris in mod formal în următorul pseudocod:

procedura BACKTRACK este| k ← 1| S1 ← A1| cât timp k>0 repeta| | cât timp Sk0 repeta| | | xk ← *cel mai mic element din Sk| | | Sk ← Sk - {xk}| | | dacă *x este solutie atunci| | | | *memorează soluţia| | | |_▄| | | k ← k+1| | | *calculează Sk| | |_▄ | | k ← k-1| |_▄|__▄

Acest proces poate fi reprezentat cu ajutorul unui arbore care reprezintă mulţimea soluţiilor parţiale. Reprezentarea se face după cum urmează:

a) radacina arborelui este reprezentată de vectorul nul;b) fii unui nod de pe nivelul k-1 reprezintă elementele mulţimii Ak.

În situaţia descrisă, algoritmul parcurge arborele în ordinea indicată de săgeţile punctate. O astfel de cautare este numită şi cautare depth-first. Cautarea depth-first este folosită pentru cateva probleme de grafuri.

O importanţă şi mai mare în reducerea duratei de execuţie a programului o are reducerea numărului de noduri din arborele în care se face căutarea. Pentru a realiza aceasta există patru modalităţi:1. revenirea la soluţia anterioara trebuie să se facă de îndată ce s-a ajuns

la concluzia că soluţia parţială curentă nu mai poate produce soluţii;2. sa nu se parcurgă ramuri ale arborelui care sunt izomorfe cu altele,

dacă acestea au fost parcurse;3. nodurile trebuie să fie aranjate în arbore astfel încat cele care au un

grad mai mic să se afle pe un nivel superior faţă de cele care au un grad mai mare;

4. în cazul în care se doreşte obţinerea unei soluţii optime este indicat să se genereze soluţii parţiale în ordinea creşterii costului.

Deoarece mulţimile Sk, cu k=1,n, sunt mulţimi finite, atunci fiecare element al mulţimii poate fi identificat prin indicele său, urmând ca informaţia aferentă elementului de indice k să fie conţinut intr-o zonă de date. În concluzie, în vectorul x, în pozitia k vom depune valorile 1 pina la nk, unde nk reprezinta cardinalul multimii Sk. Astfel, alegerea elementelor de pe poziţia k se va face în ordinea crescătoare a indicilor.

Presupunând condiţiile de continuare stabilite, putem scrie procedura BACKTRACK, in care CONT reprezintă condiţiile de continuare pentru x1,..., xk, iar ESTE_SOL reprezintă condiţia ca x1, ..., xk să reprezinte o soluţie.Cea mai intuitivă metodă este cea care foloseşte implementarea recursivitatii. Algoritmul în pseudocod este prezentat mai jos:procedura BACKTRACK(k) este | pentru i=1,nk,1 repetă | | xk ← i | | dacă CONT(x,n,k)=1 atunci | | | dacă ESTE_SOL(x,k) atunci | | | | *scrie x1, ..., xk | | | |_▄ | | | execută BACKTRACK(k+1) | | |_▄ | |_▄ |_▄

Programul principal are forma:execută BACKTRACK(1)

Metoda recursivă prezentată anterior are avantajul de a fi naturală si lizibila, dar are dezavantajul de a fi mai putin eficientă deoarece se încarcă inutil stiva calculatorului.

Varianta iterativa este prezentata mai jos.procedura BACKTRACK(x,n) este :| k ← 1| xk ← 0| cât timp k>0 repetă| | gasit ← 0| | i ← xk +1| | cât timp (ink) /\ (gasit=0) repetă| | | xk ← i| | | dacă CONT(x,n,k)=1 atunci| | | | gasit ←1 | | | | altfel i ← i+1 | | | |_▄ | | |_▄ | | dacă gasit=0 atunci | | | k ← k-1 | | | altfel dacă ESTE_SOL(x,k,n)=1 atunci | | | | *scrie x1, ..., xk | | | |_▄ | | | k ← k+1 | | | xk ← 0 | | |_▄ | |_▄ |_▄

Algoritmul general prezentat este aplicabil şi în cazul în care problema admite soluţii de lungime diferită, dar care coincid pe k poziţii. În cazul în care, natura problemei nu permite existenţa unor astfel de situaţii algoritmii anterior trebuie modificaţi, astfel încât se elimină cautarea redundantă.

În aceste condiţii procedurile devin:

- varianta recursivăprocedura BACKTRACK(k) este| pentru i=1,nk,1 repetă| | xk ← i| | dacă CONT(x,n,k)=1 atunci| | | dacă ESTE_SOL(x,k) atunci| | | | * scrie x1, ..., xk| | | | altfel execută BACKTRACK(k+1)| | | |_▄ | | |_▄ | |_▄ |_▄

- varianta iterativăprocedura BACKTRACK(x,n) este :| k ← 1| xk ← 0| cât timp k>0 repeta| | gasit ← 0| | i ← xk+1| | ┌ cât timp ink si gasit=0 repetă| | | xk ← i| | | dacă CONT(x, n, k)=1 atunci| | | | gasit ←1| | | | altfel i ← i+1| | | |_▄ | | |_▄ | | dacă gasit=0 atunci | | | k ← k-1| | | altfel dacă ESTE_SOL(x, k, n)=1 atunci| | | | * scrie x1, ..., xk| | | | altfel k ← k+1| | | | xk ← 0| | | |_▄ | | |_▄ | |_▄ |_▄

Implementarea metodei Backtracking se poate face iterativ folosind o stivă. Astfel elementele x1, x2, ..., xk le putem imagina într-o stivă notată ST.

Gasirea elementelor xk+1 determină urcarea în stivă pe nivelul k+1, în caz contrar se coboara la nivelul k-1. Când se ajunge la nivelul 0 algoritmul se termină.

xk

…

x2

x1

ST

unde: - INIT ( ) – procedura de initializarea astivei în poziţia k- SUCCESOR ( ) – funcţia care gaseste elementul urmator al mulţimii Ak+1. Dacă există succesor, acesta este pus în stivă şi functia returnează TRUE sau 1, altfel funcţia returnează FALSE sau 0.- SOLUTIE ( ) – funcţia care testează dacă s-a ajuns sau nu la soluţia finală, în caz afirmativ returnează TRUE sau 1, altfel funcţia returnează FALSE sau 0;- TIPAR ( ) – procedura ce tipareste solutia;-VALID ( ) – funcţia care testează condiţiile de continuare (adică daca avem sau nu şansa ca prin valoarea aflată pe nivelul k+1 să ajungem la soluţie). Ea intoarce TRUE sau 1 daca condiţiile sunt îndeplinite, şi FALSE sau 0 în caz contrar

Pe un anumit nivel k se cauta succesorul, atât timp cât există succesor care nu este valid. Variabila AS are rolul de a reţine dacă, atunci când s-a ieşit din ciclu, am avut succesor, caz în care acesta este valid (contrar nu s-ar fi ieşit din ciclu). Toate variabilele, cum ar fi stiva ST şi nivelul la care s-a ajuns k, sunt globale.

Această metodă folosind o stivă se poate trata si recursiv, adică procedura BACK(k) va fi recursivă, şi va primi ca parametru nivelul k.

Algoritmul pseudocod este urmatorul:procedura BACK( k) este :| dacă (SOLUTIE(k)) atunci| | execută TIPAR()| |altfel| | execută INIT(k)| | cât timp (SUCCESOR(k) )| | | dacă (VALID(k)) atunci| | | | execută BACK(k+1)| | | |_▄| | |_▄| |_▄|_▄Toate procedurile şi funcţiile prezentate la varianta iterativă primesc ca parametrul nivelul din stivă la momentul respectiv, adică k.În programul principal apelul procedurii ce implementeaza medoda Backtracking se face astfel BACK(1), unde k=1 este primul nivel din stiva cu soluţii.

Probleme rezolvateProbleme rezolvate

Exemplul 1. Problema celor n dame. Se dă o tablă de şah nxn, se cer toate soluţiile de aranjare a n dame, astfel încât două dame să nu se atace, adică să nu se afle pe aceeaşi linie, coloană sau diagonală.

Se consideră un exemplu în care presupunem o tablă de şah cu 4x4. O soluţie ar fi:

D

D

D

D

Observăm ca o damă trebuie să fie plasată singură pe linie.

D D

D

D

D

D

D

D

D D

D

D

D

D

D

D

D

D

Algoritmul continuă în acest mod, până când trebuie scoasă de pe tabla prima dama. Pentru reprezentarea unei soluţii putem folosi un vector cu n componente (având în vedere că pe fiecare linie se găseşte o singura damă). Pentru soluţia găsită avem vectorul st ce poate fi asimilat unei stive. Doua dame se gasesc pe aceeaşi diagonală dacă şi numai dacă este îndeplinită condiţia:

| st(i) – st(j) | = | i – j |

În general st(i) = k semnifică faptul că pe linia i dama ocupa pozitia k.

Deci, soluţia anterioara:

3 st(4)

1 st(3)

4 st(2)

2 st(1)

Exemplu: In tabla 4 x 4 situatia este urmatoarea:

D

D

st(1) = 1 i = 1

st(3) = 3 j = 3

| st(1) – st(3) | = | 1 – 3 | = 2

| i – j | = | 1 – 3 | = 2

Sau:

D

D

st(1) = 3 i = 1

st(3) = 1 j = 3

| st(1) – st(3) | = | 3 – 1 | = 2

| i – j | = | 1 – 3 | = 2

Programul in C – Exemplul 1 (varianta iterativa)

#include<stdio.h>#include<conio.h>#include<math.h>int st[100],k,n;void Init(){

st[k]=0;}int Succesor(){

if(st[k]<n){ st[k]++;

return 1; } else return 0;}int Valid(){

int i;for(i=1;i<k;i++)

if((st[k]==st[i])||(abs(st[k]-st[i])==abs(k-i)))return 0;

return 1;}

int Solutie(){ return (k= =n); }void Tipar(){

int i;for(i=1;i<=n;i++) printf("%d ",st[i]);

printf("\n"); getch();}void Back(){ int AS=0;k=1; Init(); while(k>0){ do{ }while((AS=Succesor())&& (!Valid())); if(AS) if(Solutie()) Tipar(); else{

k++;Init();

} else k--; }}void main(){ printf("n=");scanf("%d",&n); Back();}

Programul in C – Exemplul 1 (varianta recursiva)

#include<stdio.h>#include<conio.h>#include<math.h>int st[100],k,n;void Init(int k){

st[k]=0;}int Succesor(int k){ if(st[k]<n){ st[k]++; return 1; } else return 0;}int Valid(int k){

int i;for(i=1;i<k;i++) if((st[k]==st[i])||(abs(st[k]-st[i])==abs(k-i))) return 0;return 1;

}int Solutie(int k){

return (k= =n+1); }

void Tipar(){int i;

for(i=1;i<=n;i++) printf("%d ",st[i]); printf("\n"); getch();}void Back(int k){ if(Solutie(k)) Tipar(); else {

Init(k);while (Succesor(k)){

if (Valid(k)) Back(k+1);}

}}void main(){

clrscr(); printf("n=");scanf("%d",&n); Back(1);}

Exemplul 2. Problema colorării hărţilor. Fiind dată o hartă cu n ţări, se cer toate soluţiile de colorare a hărtii, utilizând cel mult patru culori, astfel încât două ţări cu frontiera comună să fie colorate diferit.Pentru exemplificare, vom considera următoarea hartă, unde ţările sunt numerotate cu cifre cuprinse intre 1 si 5.

4

5

2 1

3

O soluţie a problemei este urmatoarea:- tara 1 - culoarea 1- tara 2 - culoarea 2- tara 3 - culoarea 1- tara 4 - culoarea 3- tara 5 - culoarea 4

Harta este furnizată programului cu ajutorul unei matrici Anxn , unde:

1, ţara i are frontiera comuna cu ţara jA(i, j) =

0, ţara i nu are frontiera comuna cu ţara j.

Matricea A este simetrica.

Se va utiliza stiva st, unde nivelul k al stivei simbolizează ţara k, iar st[k] culoarea ataşată ţării k. Stiva are înălţimea n şi pe fiecare nivel ia valori intre 1 şi 4, adică numărul culorilor e maxim 4.

Condiţia ca două ţări vecine sa aibă aceeaşi culoare este:(st[k]=st[i]) /\ (a[i][k])=1)

Programul in C – Exemplul 2

#include<stdio.h>#include<conio.h>#include<math.h>int st[100],a[100][100],k,n;void Init(){

st[k]=0;}int Succesor(){

if(st[k]<4){

st[k]++;

return 1;

} else return 0;}int Valid(){

int i;

for(i=1;i<=k-1;i++) if((st[k]==st[i])&&(a[i][k]==1)) return 0;

return 1;}int Solutie(){

return (k= =n); }

void Tipar(){int i;

printf("Solutia:\n"); for(i=1;i<=n;i++)

printf("Tara %d - culoarea %d \n",i, st[i]); printf("\n"); getch();}void Back(){ int AS=0;k=1; Init(); while(k>0){ do{ }while((AS=Succesor())&& (!Valid())); if(AS)

if(Solutie()) Tipar();

else{k++;Init();

} else k--; }}

void main(){ printf("Nr. de tari n=");scanf("%d",&n); printf("Matricea tarilor vecine \n"); for (int i=1; i<=n; i++)

for (int j=1; j <=i-1; j++) {printf ("a[%d] [%d] =", i, j);scanf ("%d", &a[i][j]);a[j][i] = a[i][j];

} Back();}

7.2.metoda backtracking

Documents