Backtracking

1.1.1 Prezentare generala

În multe din aplicaţiile metodei, soluţia se poate exprima sub forma unui vector (x1,x2 xn) unde xi S1, ( ) i {1,2, ,n}, mulţimile Si fiind finite şi ordonate. De multe ori, pentru a fi rezolvată, problema necesită găsire unui vector care maximizează (minimizează sau satisface) o anumită condiţie P (x1, x2, ,xn). Uneori sunt căutaţi toţi vectorii care satisfac P. De exemplu, sortarea crescătoare a tabloului de numere intregi x[1 n] este o problemă a cărei soluţie este de forma unui vector. Dacă i este indexul celui mai mic element, condiţia P este în acest caz: xi xi +1, i {1,2, ,n}, dar sortarea nu este în mod obişnuit o problemă care se rezolvă cu ajutorul acestei metode. Presupunem că mi este cardinalul mulţimii Si. Fie m (m=m1*m2* *mn) vectori cu n componente care pot satisface condiţia P. O metodă directă de găsire a soluţiilor, cunoscută sub numele de metoda forţei brute, ar fi aceea de a genera toţi aceşti vectori şi de a alege doar pe aceia care verifică condiţiile problemei. Metoda backtracking are ca avantaj abilitatea de a ne îndrepta către acelaşi răspuns, dar efectuând mai puţin de m încercări. Ideea de bază este să construim vectorul soluţiilor componentă cu componentă şi să folosim condiţii modificate Pk (x1, x2, ,xk), denumite uneori funcţii, utile pentru a verifica dacă vectorul format are şansă de success. Principalul avantaj al acestei metode este următorul: dacă se constată că vectorul parţial (x1, x2, , xk) nu poate conduce la o soluţie “realizabilă “, atunci cei mk+1, mn vectori rămaşi netestaţi pot fi ignoraţi în totalitate. Multe din problemele care se rezolvă utilizând metoda backtracking necesită ca soluţiile să satisfacă un set complex de restricţii.

Pentru orice problemă, aceste restricţii pot fi împărţite în două categorii: implicite şi explicite.

Definiţia 1. Restricţiile explicite sunt reguli care impun ca fiecare xk să ia valori dintr-o mulţime dată.

Exemplul 1:

xk≥0 sau Sk={xk|xk Z+}

(xk=0 sau xk=1) sau Sk {0, 1}

1k ≤xk ≤uk sau Sk= {a|1k≤a≤uk}

Restricţiile explicite depind de condiţia specifică i a fiecărei a problemei de rezolvat. Cu alte cuvinte toţi vectorii care satisfac restricţiile explicite definesc spaţiul soluţiilor posibile S1 x S2 x x Sn.

Definiţia 2. Restricţiile implicite sunt reguli care determină ce vectori din domeniul soluţiilor lui xk satisfac funcţia criteriu. Astfel, restricţiile implicite descriu felul în care elementele componente xk trebuie să se lege între ele.

1.1.2 Problema celor 8 regine

O problemă clasică este plasarea a 8 regine pe o tablă de şah 8 x 8 astfel încât să nu se atace reciproc, altfel spus, să nu se afle două regine pe acelaşi rând, pe aceeaşi coloană sau diagonală.

Se numerotează liniile şi coloanele de pe tabla de şah de la 1 la 8. De asemenea, reginele se numerotează de la 1 la 8. Dacă fiecare regină trebuie să se afle pe rânduri diferite, putem plasa regina k pe linia k. Deci, toate soluţiile problemei pot fi reprezentate ca vectori (x1, x2, , x8), unde xk este coloana unde este plasată regina k. Utilizând această formulare, restricţiile explicite sunt Sk = {x1, x2, , x8}, 1≤k≤8.

Rezultă că domeniul soluţiilor este format din 88 vectori. Restricţiile implicite ale problemei impun ca toate elementele xk să fie diferite între ele (toate reginele să se afle pe coloane diferite) şi nici o regină să nu fie pe aceeaşi diagonală cu o altă regină. Prima din aceste două restricţii presupune că toate soluţiile sunt permutări ale vectorului (1, 2, 3, 4,5, 6, 7, 8). Acest lucru reduce mărimea domeniului soluţiilor de la 88 la 8! posibilităţi. Vom încerca să prezentăm în termenii lui xi (coloanele tablei) restricţiile cerute:

Figură

Pentru ca regina de pe linia i coloana xi să fie pe aceeaşi diagonală cu regina de pe linia k şi coloana xk, triunghiul dreptunghic care se formează ar trebui să aibă unghiurile de 450, deci să fie isoscel. Prin urmare catetele de lungimi |i-k| respectiv |xi-xk| trebuie să fie egale; condiţia |i-k| ≠ |xi-xk| exprimă faptul că două regine nu pot fi plasate pe aceeaşi diagonală. Faptul că nu pot fi plasate două regine pe aceeaşi coloană poate fi exprimat prin condiţia xi ≠ xk.

Soluţia dată în figură este (4, 6, 8, 2, 7, 1, 3, 5)