Met Backtrackingkk

Conf. dr. M. Vlada

METODA BACKTRACKING 1. Rezolvarea problemelor în AI (Artificial Intelligence); 2. Spatiul starilor problemei, Soluţii, reguli de producţie, reguli de căutare; 3. Exemple de programe/baze de cunostinte. - http://en.wikipedia.org/wiki/Computer_science În Informatică (Computer Science) s-au impus în domeniul tehnicilor de programare (metode pentru rezolvarea problemelor) câteva metode definite şi elaborate de AI: ƒ metoda backtracking (metoda „revenirii” implementată sub diverse forme (de exemplu, motorul de inferenţă PROLOG este conceput să caute solutiile folosind conceptia acestei metode; parcurgerea in adancime a arborilor; DF(depth, first)); Metoda face legatura dintre programarea procedurala si programarea delarativa; ƒ metoda Divide et Impera („desparte şi stapâneşte”, utilizată în strategii de căutare pentru arbori AND/OR; ƒ metoda Greedy (metoda „inghitirii” pentru probleme de optimizare); ƒ metoda BRANCH AND BOUND („ramificare si marginire”, implementata prin folosirea unei cozi; utilizată în parcurgerea pe latime a arborilor; BF ); ƒ metoda programării dinamice. Metoda Backtracking = metoda „revenirii”, definită şi elaborată de AI; este rezultatul unei istorii din 1852, când studentul englez Francis Guthner a enunţat problema celor 4 culori: „sunt suficiente 4 culori pentru a colora o hartă ce reprezintă diverse ţări, cu condiţia ca oricare două ţări vecine (cu frontiera comună) să fie colorate cu culori diferite”. Teoretic, problema a fost rezolvată pentru 5 culori, dar rezolvarea ei completă – pentru 4 culori (n >4 ) a fost posibilă doar în 1977 (K.Apple şi W. Hakel) prin utilizarea calculatorului. Metoda se aplica pentru problemele ale căror soluţii se pot reprezenta sub formă de vectori n

S = (x1 ,..., x n ) ∈ S = ∏ S i i =1

unde

S = spaţiul soluţiilor posibile si = |Si|; Si fiind de o anumită natură (tipuri de date reale, matrice etc.). Complexitatea problemei este determinată de dimensiunea spaţiilor soluţiilor posibile. |S| = s1,…sn De exemplu,

dacă s1=s2=…=sn=n, atunci |S|=nn dacă s1=s2=…=sn=2, atunci |S|=2n.

Definiţie: Se numeşte soluţie-rezultat, vectorul x= (x1,x2,…xn) ce satisface aşanumitele condiţii interne proprii problemei concrete: 1

Conf. dr. M. Vlada

ϕ: S → {true, false} este predicat,

 true daca  false

ϕ ( x1 ,..., x n ) = 

x1 ,..., x n

verifica diverse conditii altfel

Exemplu: Generarea permutărilor mulţimii {1,2,…,n}: Si={1,2,…n}, i=1,…,n si=n si |S|=nn dimensiunea spaţiilor soluţiilor posibile Vectorul X=(xi)i=1,…,n este soluţie rezultat, dacă  true daca ∀i, j ∈ {1,..., n}, i ≠ j , xi ≠ x j altfel  false

ϕ ( x1 ,..., x n ) = 

Observaţie: (1,1,…,1) nu este soluţie rezultat, dar e soluţie posibilă; (1,2,…,n) este soluţie rezultat. Numărul soluţiilor rezultat este n!. Definiţie: Se spune că vectorul (x1,…,xk) ∈ (S1,…,Sk), k≥1 verifică aşanumitele condiţii de continuare, dacă ϕk(x1,…,xk)=true, ϕk : S1xS2x…xSk → {true,false} are valoarea true în cazul în care (x1,…,xk) poate fi dintr-o soluţie rezultat.

Exemplu: Pentru generarea permutărilor mulţimii {1,2,…,n}, condiţiile de continuare sunt:  true daca ∀i, j ∈ {1,..., k}, i ≠ j , xi ≠ x j altfel  false

ϕ ( x1 ,..., x k ) = 

Concepţia şi strategia metodei BACKTRACKING Metoda a fost concepută pentru a evita generarea tuturor soluţiilor posibile. În acest sens, metoda foloseşte un arbore virtual construit astfel: nivelul 0 conţine rădăcina virtuală r; nivelul 1 conţine ca noduri, elementele mulţimii S1, în care componenta x1 ia valori, legăturile mulţimii etichetate cu1,2,…, s1; ƒ nivelul k≥2, conţine ca noduri elementele mulţimii Sk, astfel ca din orice nod de pe nivelul k-1 pleacă exact sk muchii; nivelul conţine s1,…sk noduri; ƒ nivelul n conţine s1 ... sn noduri terminale.

ƒ ƒ

2

Conf. dr. M. Vlada

r 1 x1

s1 s1

1 2

2…s2

..

s2

1

2...s2

1

. . . 2 ..sn

→

1 2.

noduri s1s2 noduri

→

. . .

xn

…

→

1 x2

2..

. . . ….sn

1

2…sn

s1…sn noduri

Arborele ataşat spaţiului soluţiilor posibile.

Metoda Backtracking utilizează arborele ataşat soluţiilor posibile pentru a genera soluţiile rezultat, evitând generarea tuturor soluţiilor posibile prin verificarea condiţiilor de continuitate ϕk(x1,…,xk)

Exemplu: Arborele ataşat spaţiului soluţiilor posibile pentru problema generării permutărilor mulţimii {1,2,…,n}: r 1 x1

n n

2….n

1 2

..

n

1

2...n

→

. . . 1 xn

…

→

1 x2

2..

. . . 2 ..n

1 2.

noduri n2 noduri

. . . ….n

1

2…n

→

S1={1,2,…n}; S2={1,2,…n}; … Sn={1,2,…n};

3

|Sn|=n;

Sn={1,2,…,n}.

nn noduri

Conf. dr. M. Vlada

Observaţie: Generarea elementelor produsului cartezian {1,…,n}x … x {1,…,n} presupune generarea întregului spaţiu al soluţiilor posibile. Observaţie: O soluţie rezultat este un drum de la rădăcină la un nod terminal. Metoda va genera drumuri de la stânga la dreapta conform parcurgerii DF(depth, first) a arborilor (în adâncime) şi anume va genera vectorul (x1,x2,…,xn) astfel: ƒ componentele x1,x2,…,xn primesc pe rând valori, adică mai întâi x1, apoi x2, …, deci xk vor primi valoare numai dacă au fost deja stabilite valori pentru x1,x2,…,xk-1; ƒ dacă xk a primit valoare, nu se trece la nivelul urmator ca să i se atribuie valori lui xk+1, fără să se testeze condiţiile de continuare ϕk(x1,…,xk); ƒ dacă ϕk(x1,…,xk)=true, atunci se încearcă să se dea valori pentru xk+1. ƒ dacă ϕk(x1,…,xk)=false, atunci: va trebui o altă alegere pentru xk, dacă Sk nu s-a epuizat sau a) dacă Sk s-a epuizat, se revine la nivelul inferior (k-1) şi xk primeşte o b) nouă alegere, abandonându-se un întreg arbore (de aici denumirea metodei).

x1 → x2 →

Observaţie: ϕn(x1,…,xn) ≡ ϕ

x3 → xk-1 →

1

2

sk

xk →

1

2

sk

1

2

sk

Implementarea metodei Procedura nerecursivă INPUT

:

{

}

____

S k = α k1 , α k2 ,..., α ksk , k = 1, n, sk = sk

( )

∧

valorile α k0 ∉ S k cu proprietatea ca succ α k0 = α k ϕk(x1,…,xk) condiţii de continuare

OUTPUT:

(x1,…,xn) soluţii rezultat.

Procedure BACK; 4

Conf. dr. M. Vlada k←1 {reprezintă nivelul în arbore} 0 {valoare de start} x k ← αk while k>0 do {se generează drumuri} if k=k+1 then {s-a găsit o soluţie} k ← k-1 write x1,x2,…,xn else {altă soluţie} sk if xk< αk then {altă valoare pentru xk} xk ← succ(xk) if ϕk(x1,…,xk) then k ← k+1 else {s-a epuizat sk} xk← αk0 {valoare de start} k ← k-1 Varianta recursivă:

Procedure BACK(k:integer); if k=k+1 then write (x1,x2,…,xn) else {se caută altă soluţie} {valoare de start} xk← αk0 sk while xk< αk do {Sk nu s-a epuizat}} xk ← succ(xk) if ϕk(x1,…,xk) then back(k+1)

Utilizare: BACK(1); Exemplul 1: Generarea permutărilor mulţimii {1,2,….n} program permutari; var x:array[1..200] of integer; nr,i,n,k:integer; function col(k:integer):boolean; begin col:=true; for i:=1 to k-1 do if x[i]=x[k] then begin col:=false; exit; end; end; begin write('n='); readln(n);

5

Conf. dr. M. Vlada nr:=0; k:=1; for i:=1 to n do x[i]:=0; while k>0 do if k=n+1 then begin k:=k-1; nr:=nr+1; writeln(' solutia nr ',nr); for i:=1 to n do write(x[i]:2); readln; end else if x[k]
Observaţii: pt. n=3 se obţin 6 soluţii: 1 2 3; 1 3 2; 2 1 3; 2 3 1; 3 1 2; 3 2 1. Exemplul 2: Problema celor n dame (regine). Să se aşeze cele 8 dame pe o tablă de şah pătrată cu 8 linii şi 8 coloane, astfel ca să nu se atace reciproc, adică să nu existe două dame pe aceeaşi linie, coloană sau diagonală. Orice soluţie rezultat X=(x1,…,xn), xi=coloana pe care se află dama de pe linia „i”. Condiţii interne: Fie i şi j două dame: a) damele să nu se afle pe aceeaşi coloană xi≠xj; i≠j b) să nu se afle pe diagonala xi , xj

(i,xi)

(i,xi)

j-i ≠ xj – xi

(j,xj)

(j,xj)

⇓

|i-j| ≠ |xi-xj| 6

i-j ≠ xi -xj

Conf. dr. M. Vlada Program cele_8_regine; var x:array[1..200] of integer; nr,i,n,k:integer; function col(k:integer):boolean; begin col:=true; for i:=1 to k-1 do if (x[i]=x[k]) or (abs(i-k)=abs(x[i]-x[k])) then begin col:=false; exit; end; end; begin write('n='); readln(n); nr:=0; k:=1; for i:=1 to n do x[i]:=0; while k>0 do if k=n+1 then begin k:=k-1; nr:=nr+1; writeln(' solutia nr ',nr); for i:=1 to n do write(x[i]:2); readln; end else if x[k]
Observaţii: Pentru n = 3, nu sunt soluţii; Pentru n = 4 sunt 2 soluţii: 2 4 1 3, 3 1 4 2; Pentru n = 5 sunt 10 soluţii: 1 3 5 2 4; 1 4 2 5 3, 2 4 1 3 5, … , 5 3 1 4 2 Pentru n = 6 sunt 4 soluţii: 2 4 6 1 3 5, 3 6 2 5 1 4, 4 1 5 2 6 3, 5 3 1 6 4 2; Pentru n = 8 există 92 de soluţii, dintre care 12 sunt distincte ( restul au fost obţinute din simetricele lor, prin rotirea tablei cu 900, 1800, 2700). Ex: 1 5 8 6 3 7 2 4, 1 6 8 3 7 4 2 5, 1 7 4 6 8 2 5 3, 1 7 5 8 2 4 6 3, 2 4 6 8 3 1 7 5, 2 5 7 1 3 8 6 4, 2 5 7 4 1 8 6 3, 2 6 1 7 4 8 3 5, 2 6 8 3 1 4 7 5, 2 7 3 6 8 5 1 4, 2 7 5 8 1 4 6 3, 2 8 6 1 3 5 7 4, 3 1 7 5 8 2 4 6, 3 5 2 8 1 7 4 6, 3 5 2 8 6 4 7 1, 3 5 7 1 4 2 8 6, 3 5 8 4 1 7 2 6, 3 6 2 5 8 1 7 0 … sol 92 = 8 4 1 3 6 2 7 5. Exemplul 3: Colorarea grafurilor – hărţilor:

7

Conf. dr. M. Vlada Fiecărei hărţi i se poate ataşa un graf planar.

G=(Vi,E), Vi=mulţimea nodurilor; E = mulţimea muchiilor; n=nr. de ţări; n=|V| nr. de noduri; c= nr. de culori; Sk={1,2,…,c}; k=1,…,n; Soluţie: (x1,…,xn), xi∈{1,…,c}; xi = culoarea ataşată nodului i. G poate fi reprezentat prin:

•

1 daca exista muchie aij  altfel 0 matricea de adiacenţă A = ||aij|| i=1,…,n; j=1,…,n;

• matricea muchiilor xi ≠ xj, i ≠ j  true daca ∀i, j ∈ {1,..., k}, i ≠ j , xi ≠ x j tari vecine altfel  false

ϕ ( x1 ,..., x k ) = 

Intrări:

n = nr. de noduri m = nr. de muchii (i,j) = muchiile c = nr. de culori Ieşiri: (x1,x2,…,xn), xi ∈ {1,…,c}, i = 1,…,n Program colorare_harti; var a:array[1..30,1..30] of 0..1; x:array[1..30] of integer; nr,i,j,n,m,k,c:integer; function cont(k:integer):boolean; begin cont:=true; for i:=1 to k-1 do for j:=i+1 to k do if (a[i,j]=1) and (x[i]=x[j]) then begin cont:=false;

8

Conf. dr. M. Vlada

end;

exit;

end; begin write('nr de noduri (tari): n='); readln(n); write('nr.de muchii (vecini): m='); readln(m); nr:=0; k:=1; for i:=1 to n do for j:=1 to n do a[i,j]:=0; writeln('introduceti muchiile (i j):'); for i:=1 to m do begin readln(k,c); a[k,c]:=1; a[c,k]:=1; end; write('nr. de culori c='); readln(c); k:=1; for i:=1 to n do x[i]:=0; while k>0 do if k=n+1 then begin k:=k-1; nr:=nr+1; writeln(' solutia nr ',nr); for i:=1 to n do write(x[i]:2); readln; end else if x[k]
Observaţii: dacă V={1,2,3,4,5,6}; E=(1,2), (1,4), (1,6), (2,4), (2,5), (2,3),(3,5), (3,6), (4,5), (4,6), (5,6) Se obţin 120 soluţii: 4 2 4 1 3 2, 4 2 4 3 1 2, 4 3 1 1 2 3,…

9

Conf. dr. M. Vlada

Metoda Divide et Impera („desparte şi stapâneşte”, utilizată în strategii de căutare pentru arbori AND/OR) Exemplul : Problema turnurilor din HANOI • Se dau n discuri de mărimi diferite aşezate în ordine într-o stivă pe tija A, discul cel mai mic fiind vârful , iar cel mai mare fiind baza. • Folosind tija C ca tijă intermediară, să se treacă cele n discuri de pe A pe B, ţinând cont de următoarele restricţii: - totdeauna se mută discul din vârful unei stive, deasupra vârfului altei stive; - nu se poate aşeza un disc mare peste unul mai mic; • Să se realizeze trecerea discurilor printr-un numar minim de mutări. n

xn-1 →

1

1 →

A,left

← xn-1 B,centre

C,right

Demonstratia faptului ca 2n-1 este numarul minim de mutari pentru cele n discuri. xn = nr. minim de mutări xn= ? 1 + xn-1 xn=xn+1 + ↓ ↓ ↓ trecere trecere trecerea celor pe C A→B (n-1) discuri pe B xn=2xn-1+1 xn+1=2xn-1+2 yn=xn+1 yn=2yn-1, y0=0 yn=2n ===>xn=2n-1 nr. minim de mutari pentru cele n discuri.

Towers of Hanoi (Prolog- baza de cunostinte/ program) This example simulates the Towers of Hanoi problem of moving discs from a left pole to a right pole. hanoi(N) :- move(N, left, right, centre). move(0, _, _, _) :- !. move(N, A, B, C) :M is N-1, move(M, A, C, B), format("move a disc from the ~w pole to the ~w pole\n", [A,B]), move(M, C, B, A). Program turnuri_Hanoi; ( metoda: Divide et impera } var n:integer;

10

Conf. dr. M. Vlada a,b,c:char; procedure Hanoi(n:integer;a,b,c:char); begin if n=1 then writeln(a,b) else begin Hanoi(n-1,a,c,b); writeln(a,b); Hanoi(n-1,c,b,a); end; end; begin write('dati nr.de discuri n='); readln(n); a:='a'; b:='b'; c:='c'; Hanoi(n,a,b,c); end.

11