Tehnica de programare Backtracking

Descrierea tehnicii

Aceast tehnic se folosete n rezolvarea problemelor care ndeplinesc simultan

urmtoarele condiii:

- soluia lor poate fi pus sub forma unui vector S=x1,x2, ...,xn, cu x1 A1, x2 A2 ,...,xn

An;

- mulimile A1, A2 , ., An sunt mulimi finite, iar elementele lor se consider c se afl

ntr-o relaie de ordine bine stabilit;

- nu se dispune de o alt metod de rezolvare, mai rapid;

- x1 x2 , xn pot fi la rndul lor vectori;

- A1, A2 , An pot coincide.

Tehnica Backtracking are la baz un principiu extrem de simplu:

- se construiete soluia pas cu pas: x1, x2 ,xn

- dac se constat c, pentru o valoare aleas, nu avem cum s ajungem la soluie, se

renun la acea valoare i se reia cutarea din punctul n care am rmas.

Concret:

- se alege primul element x1, ce aparine lui A1;

- presupunnd generate elementele x1,x2 ,xp , aparinnd mulimilor A1,

A2 ,Ap , se alege (dac exist) xp+1 , primul element disponibil din mulimea Ap+1. Apar

dou posibiliti :

1) Nu s-a gsit un astfel de element, caz n care se reia cutarea considernd generate

elementele x1,x2 ,xp+1 , iar aceasta se reia de la urmtorul element al mulimii Ap rmas

netestat;

2) A fost gsit, caz n care se testeaz dac acesta ndeplinete anumite condiii de

continuare aprnd astfel dou posibiliti:

- ndeplinete, caz n care se testeaz dac s-a ajuns la soluie i apar din nou dou

posibiliti:

- s-a ajuns la soluie (soluie final), se tiprete soluia i se reia algoritmul

considernd generate elementele x1,x2 ,xp , (se caut n continuare, un alt element al

mulimii Ap , rmas netestat);

- nu s-a ajuns la soluie final , caz n care se reia algoritmul considernd generate

elementele x1,x2 ,xp , i se caut un prim element xp+1 Ap.

- nu le ndeplinete, caz n care se reia algoritmul considernd generate elementele

x1,x2 ,xp , iar elementul xp-1 se caut ntre elementele mulimii A, rmase netestate.

Algoritmul se termin atunci cnd nu exist nici un element x1 A1 netestat.

Observaie: tehnica Backtracking are ca rezultat obinerea tuturor soluiilor problemei. n

cazul n care se cere o sigur soluie se poate fora oprirea, atunci cnd aceasta a fost

gsit.

Am artat c orice soluie se genereaz sub form de vector. Vom considera c

generarea soluiilor se face intr-o stiv. Astfel, x1 A1, se va gsi pe primul nivel al stivei, x2

A2 se va gsi pe al doilea nivel al stivei,..., xp Ap se va gsi pe nivelul p al stivei. n acest fel,

stiva (notat ST) va arta astfel:

ST

Nivelul p+1 al stivei trebuie iniializat (pentru a alege, n ordine, elementele mulimii p+1 ).

Iniializarea trebuie fcut cu o valoare aflat (n relaia de ordine considerat, pentru

mulimea Ap+1 ) naintea tuturor valorilor posibile din mulime. De exemplu, pentru generarea

permutrilor mulimii {1,2.....n}, orice nivel al stivei va lua valori de la 1 la n. Iniializarea unui

nivel (oarecare) se face cu valoarea 0.

Odat ales un element, trebuie vzut dac acesta ndeplinete condiiile de continuare

(altfel spus, dac elementul este valid). Acest test se face cu ajutorul funciei valid(p).

Dac s-a ajuns sau nu la soluia final se face cu ajutorul funciei solutie(), iar o soluie

se tiprete cu ajutorul funciei tipar(). Prezentm n continuare rutina back() descrisa in

pseudocod:

Subalgoritm: BACK(): p1 st[p]0 ct timp p>0 execut {cat timp stiva nu este vida} daca atunci

st[p] daca valid(p) returneaza ADEVARAT atunci daca atunci

apel tipar(p) altfel {se urca in stiva pentru completarea solutiei}

p p+1; st[p] 0

sfdaca sfdaca

altfel p p-1 {daca nu mai sunt valori de incercat, se face pas inapoi}

sfdaca Sfrit ct timp Sfrit subalgoritm

I

xp

x2

x1

mplementarea strategiei pentru problema PERMUTARILOR: Procedure back; Var k:integer; Begin p:=1;

st[p]:=0; {se initializeaza varful p al stivei} while p>0 do if st[p]

GENERAREA ARANJAMENTELOR

var st:array[1..20] of integer;n,k:integer;

function valid(p:integer):boolean; var i:integer;

begin

valid:=true;

for i:=1 to p-1 do

if st[p]=st[i] then {daca valoarea de pe nivelul p se

regaseste pe valid:=false;

nivelele inferioare}

end;

procedure tipar(p:integer); var i:integer;

begin

for i:=1 to p do

write(st[i],' ');

writeln;

end;

procedure back; var p:integer;

begin

p:=1;st[p]:=0;

while p>0 do

if st[p]

GENERAREA COMBINRILOR

{la COMBINARI, valorile care se pun pe stiva trebuie sa fie in

ordine STRICT CRESCATOARE}

function valid(p:integer):boolean; var i:integer;

begin

valid:=true;

for i:=1 to p-1 do

if st[p]0 do

if st[p]

GENERAREA TUTUROR SUBMULIMILOR UNEI MULIMI

function valid(p:integer):boolean; var i:integer;

begin

valid:=true;

for i:=1 to p-1 do

if st[p]0 do

if st[p]

GENERAREA PRODUSULUI CARTEZIAN

{NU exista condiie de validare}

procedure tipar(p:integer); var i:integer;

begin

for i:=1 to p do

write(st[i],' ');

writeln;

end;

{elementele care se incerca pe niveluL p sunt valorile de la 1 la

nr[p] }

procedure back; var p:integer;

begin

p:=1;st[p]:=0;

while p>0 do

if st[p]

GENERAREA TUTUROR PARTIIILOR UNEI MULIMI

var st:array[1..100] of integer; n:integer;

function maxim(p:integer):integer; var i,max:integer;

begin

max:=st[1];

for i := 2 to p do

if st[i]>max then

max:=st[i];

maxim:=max;

end;

procedure tipar (p:integer); var i,j,k:integer;

begin

k:=maxim(p);

for i:= 1 to k do

begin

write('{');

for j:= 1 to n do

if st[j]=i then

write(j,' ');

write('} ');

end;

writeln;

end;

procedure back(p:integer); var i : integer;

begin

for i := 1 to maxim(p-1)+1 do

begin

st[p]:=i;

if p=n then

tipar(p)

else

back(p+1);

end;

end;

Begin write('n=');

readln(n);

back(1);

readln

End.

Sarcini de lucru: 1. Pentru generarea aranjamentelor de n luate cte k, care sunt asemnarile i

deosebirile cu generarea permutrilor? 2. Pentru generarea combinarilor de n luate cte k, care sunt asemnarile i deosebirile

cu generarea aranjamentelor? 3. Fiind dat o tabl de ah, de dimensiune n, xn, se cere s se scrie coninutul funiilor

standard din rutina back ce genereaz toate soluiile de aranjare a n dame, astfel nct s nu se afle dou dame pe aceeai linie, coloan sau diagonal (damele s nu se atace ). Precizai ce punem pe stiv i ce reprezint nivelul stivei n acest caz, precum i funciile programului.

4. Fiind dat o hart cu n ri, se cer toate soluiile de colorare a hrii, utiliznd cel mult 4 culori, astfel nct 2 ri cu frontiera comun s fie colorate diferit. Este demonstrat matematic faptul c sunt suficiente numai 4 culori pentru ca orice hart s poat fi colorat astfel.

O soluie a acestei probleme este urmtoarea: ara 1 culoarea 1 ara 2 culoarea 2 ara 3 culoarea 1 ara 4 culoarea 3 ara 5 culoarea 4

Harta este furnizat programului cu ajutorul unei matrice (tablou) nnA , .

altfel 0,

j cu tara frontiera are i tara1,),( jiA

Matricea A este simetric. Pentru rezolvarea problemei se utilizeaz stiva st , unde nivelul k al stivei simbolizeaz ara k, iar st[k] culoarea ataat arii k. Stiva are nlimea n i pe fiecare nivel ia valori intre 1 i 4.

5. Un comis-voiajor trebuie s viziteze un numr de n orae. Iniial, acesta se afl ntr-unul dintre ele, notat 1. Comis-voiajorul dorete s nu treac de dou ori prin acelai ora,iar la intoarcere sa revin n oraul 1. Cunoscnd legturile existente ntre orae, se cere s se tipreasc toate drumurile posibile pe care le poate efectua comis-voiajorul.

n figura de mai jos sunt simbolizate, pentru n=6, cele 6 orae, precum i drumurile existente ntre ele. Comis-voiajorul are urmtoarele posibiliti de parcurgere: 1,2,3,4,5,6,1

1,2,5,4,3,6,1

1

2

4

5

3

6 5

4 1

3 2

1,6,3,4,5,2,1

1,6,5,4,3,2,1

Backtracking recursiv.

Pentru metoda backtracking recursiv, soluiile finale st[i] sunt generate n cadrul procedure recursive backr(p:integer) unde p reprezint nivelul pn la care s-a ajuns pe stiv. Adic la fiecare execuie din lanul de auto-apeluri, procedura backr trateaz nivelul p al stivei.

Algoritmul recursiv de backtracking este prezentat mai jos n limbajul pseudocod. backr( intreg p)

pentru contor de la la execut

st[p]contor

dac valid(p) atunci

dac atunci

apel tipar

altfel auto-apel backr(p+1)

sfritdaca

sfritdaca

sfritpentru

ntr-un ciclu, prin variabila contor vor trece pe rnd toate valorile din intervalul la

care ar putea fi ncercate pe nivelul p al stivei. La fiecare pas al ciclului, pentru fiecare dintre valorile variabilei contor:

Se memoreaz pe nivelul p valoarea contor prin st[p]contor. Se obine astfel soluia parial(st[1],st[2],,st[p]),

Se verific dac aceast soluie este valid prin funcia valid(p). Dac da atunci se verific dac soluia este final : - Dac este soluie final atunci se apeleaz funcia tipar; - n caz contrar, avem o soluie valid parial; vom urca la nivelul urmtor n stiv prin apelul backr(p+1). Algoritmul se reia de la capt, dar cu p+1 n loc de p.

Sarcini de lucru:

Sarcina de lucru: (PROIECT) S se realizeze un portofoliu de 5 probleme ce au ca algoritm de rezolvare metoda

backtracking recursiv, enun, rezolvare, testare pentru date de intrare corespunztoare diferitelor cazuri. Codul surs s fie cu comentarii referitoare la semnificaia variabilelor i a funciilor folosite.