Metoda backtracking

CAPITOLUL 1:

ASPECTE TEORETICE

Această tehnică se foloseşte în rezolvarea problemelor care îndeplinesc simultan următoarele condiţii:

• soluţia lor poate fi pusă sub forma unui vector S=x1,x2,….xn, cu x1 A1,….,An;

• mulţimile A1,A2,….,An sunt mulţimi finite, iar elementele lor se consideră că se află într-o relaţie că se află într-o relaţie de ordine bine stabilită ;

• nu se dispune de o altă metodă mai rapidă ;

Observaţii :

• nu pentru toate problemele n este cunoscut de la început ;

• x1,x2,….,xn pot fi la rândul lor vectori ;

• în multe probleme mulţimile A1,A2,….,An coincid.

La întâlnirea unei astfel de probleme, dacă nu cunoaştem această tehnică, suntem tentaţi să generăm toate elementele produsului cartezian A1XA2X….XAn şi fiecare element să fie testat dacă este soluţie. Rezolvând problema în acest mod, timpul de execuţie este atât de mare,încât poate fi considerat infinit, algoritmul neavând nicio valoare practică.

De exemplu, dacă dorim să generam toate permutările unei mulţimi finite A, nu are rost să generăm produsul cartezian AXAX....XA, pentru ca, apoi, să testăm, pentru fiecare element al acestuia, dacă este sau nu permutare (nu are rost să generăm 1,1,...,1. pentru ca să constatăm că nu am obţinut o permutare, când de la a doua cifra 1 ne puteam da seama că cifrele nu sunt distincte).

Observaţie : tehnica Backtracking are ca rezultat obţinerea tuturor soluţiilor problemei. În cazul în care se cere o singura soluţie, se poate forţa oprirea, atunci când a fost gasită.

• Pentru uşurarea înţelegerii metodei, vom prezenta o rutina unică (aplicabilă oricărei probleme), rutina care este elaborate folosind structura de stivă. Rutina va apela funcţii care au întotdeauna acelaşi nume şi care, din punct de vedere al metodei, realizează acelaşi lucru. Sarcina rezolvitorlui este să scrie explicit, pentru fiecare problema în parte funcţiile apelate de metoda backtracking.

• Evident, o astfel de abordare conduce la programe lungi. Nimeni nu ne opreşte ca, după înţelegerea metodei, să scriem programe scurte, specifice fiecărei probleme în parte (de exemplu, scurtăm substanţial textul doar dacă renunţăm utilizarea unor funcţii, scriind instrucţiunile lor chiar în corpul rutinei).

• Am arătat că orice soluţie se generează sub forma de vector. Vom considera că generarea soluţiilor se face într-o stivă. Astfel x1 A1 se va găsi pe nivelul k al stivei , x2 A2 se va găsi pe nivelul 2 al stivei ,.. xk Ak se va găsi pe nivelul k. În acest fel , stiva (notat st) va arăta ca mai jos :

Xk

...

...

...

x2

x1

Nivelul k+1 al stivei trebuie iniţializat (pentru a alege, în ordine, elementele mulţimii k+1). Iniţializarea trebuia facută cu o valoare aflată (în relaţia de ordine considerate pentru mulţimea Ak+1) înaintea tuturor valorilor posibile din mulţime.

De exemplu, pentru generarea permutărilor mulţimii {1,2,.....,n} , orice nivel al stivei va lua valori de la 1 la n. Iniţializarea unui nivel (oarecare) se face de obicei cu valoarea 0.

• Dacă mai există elemente netestate în mulţimea Ak se testează, dacă adăugate la soluţia parţială pot conduce la o soluţie validă, în funcţie de condiţiile interne ale problemei. În caz afirmativ valoarea returnată de funcţia valid () este 1, altfel funcţia returnează 0.

• Testăm dacă s-a ajuns sau nu la soluţia finală urmărind condiţiile impuse de problemă

• Soluţia se tipăreşte cu ajutorul funcţiei Soluţie().