COLEGIUL ECONOMIC "ANGHEL RUGINA"

VASLUI

Atestat la informatica

= METODA =

=BACKTRACKING=

METODA BACKTRACKING

Stiva

Stiva este acea forma de organizare a datelor (structura de date) cu proprietatea ca operatiile de introducere si scoatere a datelor se fac in varful ei.

Pentru a intelege modul de lucru cu stiva, ne imaginam un numar n de farfurii identice, asezate una peste alta (o "stiva" de farfurii). Adaugarea sau scoaterea unei farfurii se face, cu usurinta, numai in varful stivei. Daca cele n farfurii sunt asezate una peste alta, spunem ca stiva este vida. Dupa ce am scos toate farfuriile din stiva, spunem ca aceasta este vida. Oricat ar parea de simplu, principiul stivei, el are consecinte uriase in programare.

Stivele se pot utiliza folosind vectori.

Fie ST(i) un vector. ST(1),ST(2),.,ST(n) pot retine numai litere sau cifre. O variabila K indica in permanenta varful stivei.

Exemplificam, in continuare, modul de lucru cu stiva:

in stiva initial vida se introduce litera A, varful stivei va fi la nivelul 1 (k=1);

introducem in stiva litera B, deci k va lua valoarea 2;

scoatem din stiva pe B (A nu poate fi scos);

scoatem din stiva pe A; stiva ramane vida

Observatii:

in mod practic, la scoterea unei variabile din stiva, scade cu 1 valorea variabilei ce indica varful stivei, iar atunci cand scriem ceva in stiva, o eventuala valoare reziduala se pierde;

pe un anumit nivel se retine, de regula, o singura informatie (litera sau cifra), insa este posibil, asa cum va rezulta din exemplele prezentate in lucrare, sa avem mai multe informatii, caz in care avem de a face cu stive duble, triple, etc;

intreaga teorie se bazeaza pe structura de tip stiva.

Prezentarea tehnicii backtracking

Aceasta tehnica se foloseste in rezolvarea problemelor ce indeplinesc simultan urmatoarele conditii:

solutia lor poate fi pusa sub forma unui vector S=x₁, x₂, ., x_n, cu x₁IA₁, x2IA₂, ., x_nIA_n;

multimile A₁, A₂, ., A_n sunt multimi finite, iar elementele lor se considera ca se afla intr-o relatie de ordine bine stabilita;

nu se dispune de o alta metoda de rezolvare;

Observatii:

nu pentru toate problemele n este cunoscut de la inceput;

x₁, x₂, ., x_n pot fi la randul lor vectori;

in multe probleme, multimile A₁, A₂, ., A_n coincid.

La intalnirea unei astfel de probleme, daca nu cunoastem aceasta tehnica, suntem tentati sa generam toate elementele produsului cartezian A₁* A₂* .* A_n si fiecare element sa fie testat daca este solutie. Rezolvand problema in acest mod, timpul de executie este atat de mare, incat poate fi considerat infinit, algoritmul neavand nici o valoare practica.

De exemplu, daca dorim sa generam toate permutarile unei multimi finite A,nu are rost sa generam produsul cartezian A*A*.*A, pentru ca apoi, sa testam, pentru fiecare element al acestuia, daca este sau nu permutare (nu are rost sa generam 1,1,1..,1, pentru ca apoi sa constatam ca nu am obtinut o permutare, cand de la a doua cifra 1 ne putem da seama ca cifrele nu sunt distincte).

Tehnica backtracking are la baza un principiu extrem de simplu:

se construieste solutia pas cu pas: x₁, x₂, ., x_n;

daca se constata ca, pentru o valoare aleasa, nu avem cum sa ajungem la solutie, se renunta la acea valoare si se reia cautarea din punctul in care am ramas.

Concret:

se alege primul element x₁, ce apartine lui A₁;

presupunad generate elementele x₁, x₂, ., x_n, apartinand multimilor A₁, A₂, ., A_k, se alege (daca exista) x_k+1 primul element disponibil din multimea A_k+1, apar doua posibilitati:

nu sa gasit un atfel de element, caz in care se reia cautarea considerand generate elementele x₁, x₂, ., x_k, iar aceasta se reia de la urmatorul element al multimii A_k, ramas netastat;

a fost gasit, caz in care se tasteaza daca acesta indeplineste anumite conditii de continuare, aparand astfel doua posibilitati:

A) le indeplineste, caz in care se tasteaza daca s-a ajuns la solutie si apar, din nou, doua posibilitati:

a)          s-a ajuns la solutie, se tipareste solutia si se reia algoritmul considerand generate elementele x₁, x₂, .x_k (se cauta, in continure, un alt element al multimii A_k+1 ramas netastat);

b)          nu s-a ajuns la solutie, caz in care se reia algoritmul considerand generate elementele x₁, x₂, ., x_k si se cauta un prim element x_k+2IA_k+2.

B)          nu le indeplineste, caz in care se reia algoritmul considerand generate elementele x₁, x₂, ., x_k, iar elementul x_k+1 se cauta intre elementele multimii A_k+1 ramase netastate.

Algoritmul se termina atunci cand nu mai exista nici un element x₁IA₁, netastat.

Observatie: tehnica Backtracking are ca rezultat obtinerea tuturor solutiilor problemei. In cazul in care se cere o singura solutie, se poate forta oprirea, atunci cand a fost gasita.

Pentru usurarea intelegerii metodei, vom prezenta o rutina unica, aplicabila oricarei probleme, rutina care utilizeaza notiunea de stiva. Rutina va apela proceduri si functii care au intotdeauna acelasi nume si parametri si care, din punct de vedere al metodei, realizeaza acelasi lucru. Sarcina rezolvitorului este de a scrie explicit, pentru fiecare problema in parte, procedurile si functiile apelate de rutina backtracking. Evident, o astfel de abordare conduce la programe lungi. Nimeni nu ne opreste, ca dupa intelegerea metodei, sa scriem programe scurte, specifice fiecareI probleme in parte (de exemplu, scurtam substantial textul doar daca renuntam la utilizarea procedurilor si functiilor).

Am aratat ca orice solutie se genereaza sub forme de vector. Vom considera ca generarea solutiilor se face intr-o stiva. Astfel, x₁IA₁, se va gasi pe primul nivel al stivei, x₂I A₂ se va gasi pe al doilea nivel al stivei, . x_k IA_k se va gasi pe nivelul k al stvei. In acest fel, stiva (notata ST) va arata ca mai jos:

ST

Nivelul k+1 al stivei trebuie initializat (pentru a alege, in ordine, elementele multimii k+1). Initializarea trebuie facuta cu o valoare aflata (in relatia de ordine considerata pentru multimea A_k+ , inaintea tuturor valorilor posibile din multime. De exemplu, pentru generarea permutarilor multimii , orice nivel al stivei va lua valori de la 1 la n. Initializarea unui nivl (oarecare) se face cu valoarea 0. Procedura de initializare o vom numi INIT si va avea doi parametri: k (nivelul care trebuie initializat si ST stiva).

Gasirea urmatorului element al multimii A_k (element care nu a fost tastat) se face cu ajutorul procedurii SUCCESOR (AS,ST,K). Parametrul AS (am succesor) esteb o variabila booleana. Insituatia in care am gasit elementul, acesta este pus in stiva si AS ia valoarea TRUE, contrar (nu a ramas un element netastat) AS ia valoarea FALSE

Odata ales un element, trebuie vazut daca acesta indeplineste conditiile de continuare (altfel spus, daca elementul este valid). Acest test se face cu alutorul procedurii VALID EV,ST,K

Testul daca s-a ajuns sau nu la solutia finala se face cu ajutorul functiei SOLUTIE K), iar o solutie se tipareste cu ajutorul procedurii TIPAR

Prezentam in continuare rutina backtracking:

k:=1;init(1,st);

while k>0 do

begin

repeat

succesor(as,st,k);

if as then valid(ev,st,k);

until (not as) or (as and ev);

if as then

if solutie (k)

then tipar

else begin

k:=k+1;

init(k,st)

end

else k:=k-1

end

Observatie:

Problemele rezolvate prin aceasta metoda necesita un timp indelungat. Din acest motiv, este bine sa utilizam metoda numai atunci cand nu avem la dispozitie un alt algoritm mai eficient. Cu toate ca exista probleme pentru care nu se pot elabota alti algoritmi mai eficienti, tehnica Backtracking trebuie aplicata numai in ultima instanta.

In continuare prezentam mai multe probleme rezolvate prin aceasta metoda.

Backtracking elementar

Denumirea din titlu este folosita pentru a desemna utilizarea tehnicii backtrackingpentru nprobleme la care solutia este sub forma de vector, altfel spus, probleme pentru care stiva are latimea 1. Tot asa, exista probleme pentru care se foloseste stiva dubla, tripla (numite in programa probleme de backtracking in plan). In ce ne priveste, daca tot trebuie sa le 'botezam', le vom numi probleme de backtracking generalizat.

Generarea permutarilor

Se citeste un numar natural n. Sa se genereze toate permutarile multimii .

Definitie Vom numi permutare a multimii A= o functie bijectiva definita pe A cu valori in A.

Exemplu: A o permutare este (2,1,3).

Generarea permutarilor se va face tinand cont ca orice pemutare va fi alcatuita din elemente distincte ale multimii A. Din acest motiv, la generarea unei permutari, vom urmari ca numerele sa fie distincte.

Prezentam algoritmul corespunzator cazului n=3:

se incarca in stiva pe nivelul 1 valoarea 1;

incarcarea valorii 1 pe nivelul al 2-lea nu este posibila, intrucat aceasta valoare se gaseste si pe nivelul 1 al stivei;

incarcarea valorii 2 pe nivelul al 2-lea este posibila, deoarece aceasta valoare nu mai este intalnita;

valoarea 1 din nivelul al 3-lea se regaseste pe nivelul 1;

valoarea 2 din nivelul al 3-lea se regaseste pe nivelul al 2-lea;

valoarea 3 pe nivelul al 3-lea nu e intalnita pe nivelurile anterioare;

Intrucat nivelul 3 este completat corect. tiparim: 1 2 3

Algoritmul continua pana cand stiva devine vida.

program permutari;

type stiva=array [1..100] of integer;

var st:stiva;

n,k:integer;

as,ev:boolean;

procedure init(k:integer;var st:stiva);

begin

st[k]:=0;

end

procedure succesor(var as:boolean;var st:stiva;k:integer);

begin

if st[k]<n

then

begin

st[k]:=st[k]+1;

as:=true

end

else as:=false

end

procedure valid(var ev:boolean;st:stiva;k:integer);

var i:integer;

begin

ev:=true;

for i:=1 to k-1 do if st[k]=st[i] then ev:=false

end

function solutie(k:integer):boolean;

begin

solutie:=(k=n)

end

procedure tipar;

var i:integer;

begin

for i:=1 to n do write(st[i]);

writeln

end

begin

write('N= ');readln(n);

k:=1;init(k,st);

while k>0 do

begin

repeat

succesor(as,st,k);

if as then valid(ev,st,k);

until (not as) or (as and ev);

if as then

if solutie (k)

then tipar

else begin

k:=k+1;

init(k,st)

end

else k:=k-1

end

end

Problema celor n dame

Fiind data o tabla de sah, de dimensiune n*n, se cer toate solutiile de aranjare a n dame, astfel incat sa nu se afle doua dame pe aceeasi linie, coloana sau diagonala (damele sa nu se atace reciproc).

Exemplu: presupunand ca dispunem de o tabla de dimensiune 4*4, o solutie ar fi urmatoarea:

Cum procedam? Observam ca o dama trebuie sa fie plasata singura pe linie. Plasam prima dama pe linia 1, coloana 1.

A doua dama nu poate fi asezata decat in coloanaa-3-a.

Observam ca a treia dama nu poate fi plasata in linia a-3-a. Incercam atunci plasarea celei de-a doua dame in coloana a-4-a.

A treia dama nu poate fi plasata decat in coloana a-2-a.

In aceasta situatie dama a patra nu mai poate fi asezata.

Incercand sa avansam cu dama a treia, observam ca nu este posibil sa o plasam nici in coloana a-3-a, nici in coloana a-4-a, deci o vom scoate de pe tabla. Dama a doua nu mai poate avansa, deci si ea este scoasa de pe tabla. Avansam cu prima dama in coloana a-2-a.

A doua dama nu poate fi asezata decat in colana a-4-a.

Dama a treia se aseaza in prima coloana.

Acum este posibil sa plasam a patra dama in coloana a-3-a si astfel am obtinut o solutie a problemei.

	D
			D
D

Algoritmul continua in acest mod pana cand trebuie scoasa de pe tabla prima dama.

Pentru reprezentarea unei solutii putem folosi un vector cu n componente (avand in vedere ca pe fiecare linie se gaseste o singura dama).

Intrucat doua dame nu se pot gasi in aceeasi coloana, rezulta ca o solutie este sub forma de permutare. O prima idee ne conduce la generarea tuturor permutarilor si la extragerea solutiilor pentru problema (ca doua dame sa nu fie plasate in aceeasi diagonala). A proceda astfel, inseamna ca lucram conform strategiei backtracking. Aceasta presupune ca imediat ce am gasit doua dame care se ataca, sa reluam cautarea. fata de programul de generare a tuturor solutiilor problemei celor n dame, are o singura conditie suplimentara, in procedura VALID.

Semnificatia procedurilor este urmatoarea:

INIT - nivelul k al stivei este initilizat cu 0;

SUCCESOR - mareste cu 1 valoarea aflata pe nivelul k al stivei in situatia un care aceasta este mai mica decat n si atribuie variabilei EV valoarea TRUE; in caz contrar, atribuie variabilei EV valoarea FALSE

VALID - valideaza valoarea pusa pe nivelul k al stivei, verificand daca nu avem doua dame pe aceeasi linie (|st(k)-st(i)|=|k-i|), caz in care variabilei EV i se atribuie FALSE, in caz contrar, variabilei EV i se atribuie TRUE

SOLUTIE - verifica daca stiva a fost completata pana la nivelul n inclusiv;

TIPAR - tipareste o solutie.

program dame;

type stiva=array [1..100] of integer;

var st:stiva;

n,k:integer;

as,ev:boolean;

procedure init(k:integer;var st:stiva);

begin

st[k]:=0;

end

procedure succesor(var as:boolean;var st:stiva;k:integer);

begin

if st[k]<n

then

begin

st[k]:=st[k]+1;

as:=true

end

else as:=false

end

procedure valid(var ev:boolean;st:stiva;k:integer);

var i:integer;

begin

ev:=true;

for i:=1 to k-1 do

if (st[k]=st[i]) or(abs(st[k]-st[i])=abs(k-i)) then

ev:=false

end

function solutie(k:integer):boolean;

begin

solutie:=(k=n)

end

procedure tipar;

var i:integer;

begin

for i:=1 to n do write(st[i]);

writeln

end

begin

write('N= ');readln(n);

k:=1;init(k,st);

while k>0 do

begin

repeat

succesor(as,st,k);

if as then valid(ev,st,k);

until (not as) or (as and ev);

if as then

if solutie (k)

then tipar

else begin

k:=k+1;

init(k,st)

end

else k:=k-1

end

end

Produsul cartezian a n multimi

Se dau multimile:

A₁

A₂

.......

A_n

Se cere produsul catezian a celor n multimi.

Exemplu: A₁=, A₂=, A₃=.

A₁*A₂*A₃=

Pentru rezolvare se foloseste stiva ST si un vector A ce retine numerele k₁,k₂,.,k_n. Utilizam metoda backtracking , usor modificata, din urmatoarele motive:

a) orice element aflat pe nivelul k al stivei este valid, motiv pentru care procedura VALID nu face altceva decat sa atribuie variabilei EV valoaree TRUE;

b) limita superioara pe nivelul k al stivei este data de A(k).

Observatie:

- problema admite o rezolvare fara a cunoaste metoda backtracking, dar am preferat aceasta metoda din dorinta de a o rezolva standardizat.

program produs-cartez;

type stiva=array [1..100] of integer;

var st:stiva;

i,n,k:integer;

as,ev:boolean;

a:array [1..100] of integer;

procedure init(k:integer;var st:stiva);

begin

st[k]:=0;

end

procedure succesor(var as:boolean;var st:stiva;k:integer);

begin

if st[k]<a[k]

then

begin

st[k]:=st[k]+1;

as:=true

end

else as:=false

end

procedure valid(var ev:boolean;st:stiva;k:integer);

begin

ev:=true;

end

function solutie(k:integer):boolean;

begin

solutie:=(k=n)

end

procedure tipar;

var i:integer;

begin

for i:=1 to n do write(st[i]);

writeln

end

begin

write('Numarul de multimi= ');readln(n);

for i:=1 to n do

begin

write('a[',i,']=');

readln(a[i])

end;

k:=1;init(k,st);

while k>0 do

begin

repeat

succesor(as,st,k);

if as then valid(ev,st,k);

until (not as) or (as and ev);

if as then

if solutie (k)

then tipar

else begin

k:=k+1;

init(k,st)

end

else k:=k-1

end

end

Problema colorarii hartilor

Fiind data o harta cu n tari, se cer toate solutiile de colorare a hartii, utilizand cel mult 4 culori, astfel incat doua tari cu frontiera comuna sa fie colorate diferit. Este demonstrat faptul ca sunt suficiente numai 4 culori pentru ca orice harta sa poata fi colorata.

Pentru exemplificare, vom considera urmatoarea harta unde tarile sunt numerotate cu cifre cuprinse intre 1 si 5:

O solutie a acestei probleme, este urmatoarea:

tara 1 - culoarea 1;

tara 2 - culoarea 2;

tara 3 - culoarea 1;

tara 4 - culoarea 3;

tara 5 - culoarea 4;

Harta este furnizata programului cu ajutorul unei matrici A_n,n.

1, daca tara i se invecineaza cu tara j,

A(i,j)=

0, in caz contrar.

Matricea A este simetrica. Pentru rezolvarea problemei se utilizeaza stiva st, unde nivelul k al stivei simbolizeaza tara k, iar st[k] culoarea atasata tarii k. Stiva are inaltimea n si pe fiecare nivel ia valori intre 1 si 4.

Prezentam algoritmul pe exemplul dat: