Metoda backtracking este o tehnica de programare, aplicabila problemelor cu mai multe solutii care verifica anumite conditii. Exista probleme care nu pot fi rezolvate fara aplicarea metodei backtracking.
Dupa cum se stie, in timpul executiei unui program, limbajul Pascal gestioneaza si utilizeaza o structura interna de date numita stiva. Aceasta este organizata dupa principiul LIFO ("Last Input, First Output" - adica, "primul intrat, primul iesit") si are un rol bine definit: la pelul unui subprogram (procedura sau functie) se salveaza contextul modulului apelant (variabilele locale si parametrii transmisi prin valoare) si adresa de revenire (adresa instructiunii ce urmeaza a fi executata dupa terminarea subprogramului).
In cadrul unui program, utilizatorul isi poate de fini propriile sale structure de tip stiva. Cel mai simplu mod de a implementa o stiva este cu ajutorul unui vector, pe care-l vom numi, sugestiv, st. Pentru a simula caracterul de stiva, vom privi vectorul st ca si cum elementele sale ar fi aranjate "pe verticala", unul peste altul. Daca la un moment dat stiva contine elementele st[1], st[2], ., st[p], atunci pozitia p a elementului cel mai de sus, se numeste varful stivei. In general, pozitia unui element in vectorul stiva este numit nivel al stivei.
Adaugarea si extragerea de elemente in/din stiva, se poate face numai pe la capatul de sus al acesteia:
adaugarea unui nou element in stiva inseamna marirea cu o unitate a varfului stivei (p := p + 1) si stocarea unui element st[p] pe noua pozitie p;
eliminarea (extragerea) unui element din stiva inseamna abandonarea elementului aflat in varful stivei, adica nivelul stivei se micsoreaza cu o unitate (p := p - 1).
Schematic, aceste principii se pot reprezenta astfel:
|
nivel |
|
|
p |
st[p] |
|
st[2] |
|
|
st[1] |
Metoda backtracking se aplica problemelor in care solutia se poate reprezenta sub forma unei stive, implementata ca un vector. Pentru a explica principiul metodei backtracking, vom nota vectorul stiva cu st, iar numarul valorilor care formeaza o solutie cu n.
Deci, vectorul st format din elementele (st[1], st[2], ., st[n]), se va numi solutie finala.
Multimea finita S = S1 x S2 . x Sn se numeste multimea solutiilor posibile. Multimile S1, S2 . Sn sunt multimi finite avand fiecare un numar si de elemente.
Pentru fiecare problema concreta exista anumite relatii (conditii) ce trebuie satisfacute de elementele st[1], st[2], ., st[p] ale stivei st. Acestea se numesc conditii de validare (sau conditii interne). Vom spune despre o configuratie st[1], st[2], ., st[p] ca reprezinta o solutie valida a problemei daca si numai daca sunt satisfacute conditiile de v 24424m1210y alidare. O solutie valida devine solutie finala daca numarul p al nivelelor este egal cu numarul n al valorilor care alcatuiesc solutia.
Cel mai simplu procedeu de determinarea a solutiilor finale, ar fi verificarea, pentru toate solutiile posibile ale problemei, daca ele satisfac sau nu conditiile de validare. Dezavantajul acestui procedeu consta in faptul ca trebuie generate toate solutiile posibile si apoi verificarea lor, ceea ce impune un mare consum de timp.
Metoda backtracking urmareste evitarea generari tuturor solutiilor posibile. Pentru a realiza acest deziderat, elementului st[p] (varful stivei) i se atribuie o valoare numai daca au fost atribuite deja valori lui st[1], st[2], ., st[p-1]; cu alte cuvinte, obtinerea solutiei finale se realizeaza prin completarea stivei nivel cu nivel. La fiecare nivel p al stivei se verifica daca valoarea lui st[p] impreuna cu valorile anterioare indeplinesc conditiile de validare si pot conduce la o solutie finala. Daca valorile st[1], st[2], ., st[p] nu indeplinesc conditiile de validare nu este posibila obtinerea unei solutii finale. In cazul neindeplinirii conditiilor de validare, trebuie sa se verifice o alta valoare dintre valorile netestate ale multimii Sp pentru nivelul p al stivei.
Este posibil ca la un moment dat, pe un anumit nivel, nu mai exista nici o valoare netestata din multimea solutiilor. In acest caz, vom face un pas inapoi, la nivelul anterior al stivei se reluam cautarea cu valorile netestate pe acest nivel anterior. Repectivul nivel a mai fost "vizitat", dar s-a trecut la nivelul urmator dupa ce am pus pe el o valoare care a generat o solutie valida, deci este posibil sa mai existe valori netestate aici. Daca nici pe acest nivel nu mai exista valori netestate, mai facem un pas inapoi s.a.m.d. Aceasta miscosrare a nivelului stivei sta la originea numelui metodei (backtracking - cautare cu revenire). Conditiile de continuare si conditiile de validare nu sunt identice dar nici independente, intre ele existand o legatura.
Plecand de la nivelul 1 si repetand algoritmul pana cand pe toate nivelele au fost incercate toate valorile din multimea solutiilor, vom obtine solutiile finale.
Datorita facptului ca fiecare noua configuratie a stivei rezulta pornind de la precedenta, algoritmul backtracking se poate implementa intr-o maniera recursiva. Se pot scrie si programe nerecursive, dar acestea sunt mai laboriaose.
Pemutarile de n elemente sunt multimi ordonate ce contin elementele , , , , . Deci, configuratiile stivei pentru obtinerea acestor solutii vor arata astfel:
|
nivel 3 | ||||||
|
nivel 2 | ||||||
|
nivel 1 |
Cel mai simplu procedeu pentru rezolvarea acestei probleme ar fi formarea tuturor numerelor posibile folosind cifrele 1, 2 si 3, retinand doar numerele care au cifre distincte. Parcurgand multimea prin enumerare in ordine crescatoare vom obtine numerele 111, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213 etc. Acest algoritm ar conduce, pentru n = 3, la inspectarea a 27 de numere (in cazul general nn numere). Dar numarul de permutari al multimii este n! care este mai mic de cat nn.
Folosind metoda backtracking, fiecare dintre numerele enumerate mai sus va fi memorat in vectorul stiva st sub forma unei configuratii (st[1], st[2], st[3]), unde st[i] va fi cifra aflata pe pozitia i in cadrul numarului, cu i = 1, 2, 3. Dintre toate configuratiile posibile, vor forma solutii finale, doar cele care contin numai valori distincte pe nivelele stivei.
Asa cum s-a vazut mai inainte, solutiile se vor construi "din mers", prin completarea stivei nivel cu nivel. Notand cu p varful stivei la un moment dat (nivelul la care s-a ajuns pe stiva), ne propunem sa completam nivelul urmator p + 1, deci sa atribuim o valoare elementului st[p + 1]. Acest lucru se va realiza numai daca valorile st[1], st[2], ., st[p], deja existente pe stiva, indeplinesc anumite conditii. Altfel spus, vom continua constructia unei solutii numai cand stim ca pe calea respectiva ajungem la o solutie valida. In caz contrar, ne "retragem" pana la ultima pozitie anterioara pe care mai exista cel putin inca o posibiltate netestata. Este evident ca nu se pot formula criterii generale de continuare. De aceea "continuarea", "validitatea" etc. sunt notiuni specifice fiecarei probleme.
In cazul generarii permutarilor, daca intr-o permutare, incepand de la un rang (pozitia unei cifre in cadrul permutarii), toate cifrele care urmeaza sunt in ordine descrescatoare, atunci obtinerea unei alte permutari nu se mai poate face decat prin modificarea ultimei valori aflate inaintea rangului dat. Aceasta observatie ne ofera un criteriu de continuare, care ne va permite selectarea solutiilor finale valide din multimea numerelor de trei cifre care pot fi generate cu cifrele 1, 2, 3.
Din figura urmatoare rezulta evolutia stivei si modul de obtinere a solutiilor finale:
|
| |||||||||||||||||
Plecam de la primul nivel al stivei, p = 1. Pe acest nivel incercam valori din multime , pana cand una care genereaza o solutie valida. Deoarece chiar prima valoare din multimea , adica 1, este valida trecem la nivelul urmator.
Prima valoare ce poate fi incercata pe nivelul p = 2 este 1, dar ea nu genereaza o solutie valida, deoarece valoarea 1 exista si pe nivelul anterior.
A doua valoare ce poate fi incercata pe nivelul p = 2 este 2, care genereaza o solutie valida, deci trecem la nivelul urmator p = 3.
Prima valoare ce poate fi incercata pe nivelul p = 3 este 1, dar ea nu genereaza o solutie valida, deoarece valoarea 1 exista si pe primul nivel.
A doua valoare ce poate fi incercata pe nivelul p = 3 este 2, dar ea nu genereaza o solutie valida, deoarece valoarea 2 exista si pe nivelul anterior.
A treia valoare ce poate fi incercata pe nivelul p = 3 este 3, care genereaza o solutie valida. Solutia obtinuta este si finala, deoarece contine toate elementele multimii , fiecare element este luat o singura data.
Pe nivelul p = 3 nu mai putem incerca nici o valoare, deci trebuie sa revenim pe nivelul anterior (p = 2).
Pe nivelul p =
Prima valoare ce poate fi incercata pe nivelul p = 3 este 1, dar ea nu genereaza o solutie valida, deoarece valoarea 1 exista si pe primul nivel.
A doua valoare care poate fi incercata pe acest nivel este 2, care genereaza o solutie valida, dar si finala.
Pe acest nivel mai trebuie incercata doar valoarea 3, care nu conduce la o solutie valida.
Pe nivelul p = 3 nu mai avem ce incerca si deci ne intoarcem la nivel anterior, p = 2.
Pe nivelul p = 2 am incercat toate valorile si deci trebuie sa mai coboram un nivelul, ajungand astfel pe nivelul p = 1.
Pe nivelul p = 1 am incercat numai valoarea 1, asa ca trecem la urmatoarea valoare (2), obtinand o solutie valida cu un singur nivel.
Trecem la nivelul p = 2 si incepem testarea valorilor pentru acest nivel pentru a genera o solutie valida s.a.m.d.
Algoritmul se incheie atunci cand s-a ajuns din nou la nivelul p = 1 si nu mai exista nici o valoare netestata pe acest nivel (practic facem inca un pas inapoi ajungand la nivelul p = 0, adica stiva vida).
Pentru a intocmi programul backtracking recursiv de generare a permutarilor de n elemente este necesar sa declaram doua variabile globale: st vectorul stiva si n numarul de elemente. Pentru consecventa cu prezentarea anterioara vom nota cu p nivelul la care am ajuns pe stiva (varful stivei).
Pentru a putea comenta mai usor programul, se vor prezenta mai intai cele patru rutine, numite: initializare, validare, afisare si bktr, pe baza carora se va construi programul final. Pentru rezolvarea problemei propuse pot exista si alte variante de program.
Are rolul de a citi datele si de a initializeaza stiva.
In cazul permutarilor, ea trebuie sa citeasca numarul de elemente (n) si sa initializeze cu 0 toate elementele din stiva. In principiu aceasta procedura poate fi scrisa astfel:
procedure initializare;
var i: byte;
begin
write('Numarul de elemente: '); readln(n);
for i := 1 to n do
st[i] := 0
end;
Este o functie de tip boolean care va returna true daca solutia (st[1], st[2], ., st[p]) este valida, respectiv false in caz contrar. Aceasta functie se utilizeaza la implementarea conditiilor de validare pentru a determina daca solutia obtinuta la un moment dat este valida sau nu.
In problema permutarilor pentru ca noul element st[p] sa genereze solutia valida (st[1], st[2], ., st[p]), trebuie ca valoarea st[p] sa nu se mai gaseasca pe nici unul din nivelele anterioare 1, 2, ., p - 1. Functia primeste ca parametru nivelul p al stivei si ar putea fi de forma:
function validare(p: byte): boolean;
var i: byte;
begin
validare := true; (*1)
for i := 1 to p - 1 do (*2)
if st[i] = st[p] then (*3)
begin
validare := false;
n: byte;
procedure initializare;
var i: byte;
begin
write('Numarul de elemente: '); readln(n);
for i := 1 to n do
st[i] := 0
end;
function validare(p: byte): boolean;
var i: byte;
begin
validare := true;
for i := 1 to p - 1 do
if st[i] = st[p] then
begin
validare := false;
exit
end
end;
procedure afisare;
var i: byte;
begin
for i := 1 to p do
write(st[p]);
writeln
end;
procedure bktr(p: byte);
var j: byte;
begin
for j := 1 to n do
begin
st[p] := j;
if validare(p) then
if p = n then
afisare(p)
else
bktr(p + 1)
end
end;
BEGIN
initializare;
bktr(1);
readln
END.
In continuare este prezintata o alta varianta a procedurii recursive bktr:
procedure bktr(p: byte);
var j: byte;
begin
if p = n + 1 then
afisare(p - 1)
else
for j := 1 to n do
begin
st[p] := j;
if validare(p) then
bktr(p + 1)
end
end;
Enuntul problemei
Fiind date doua numere naturale n si k, sa se genereze toate combinarile de n elemente luate cate k.
Indicatii
Sa consideram multimea . Aranjamentele de n elemente luate cate k reprezinta seturile alcatuite cu cate k elemente dinstincte din multimea data, luate in diverse ordini. Spre exemplu, pentru n=3 si k=2, multimea este iar aranjamentele de 3 luate cate 2 sunt: , , , , , .
O parte dintre aceste aranjamente contin aceleasi elemente luate in alta ordine. Luand doar cate unul din seturile cu aceleasi elemente, obtinem combinarile de n luate cate k: Spre exemplu, pentru cazul anterior obtinem: , , .
Pentru n=4 si k=3, combinarile de 4 elemente luate cate 3 alcatuite pe multimea sunt: , , , .
Fiecare solutie va fi o configuratie a stivei (st[1], st[2], ., st[k]), alcatuita din k elemente distincte ale multimii .
O solutie (st[1], st[2], ., st[k]) este valida daca valoarea st[p] de pe nivelul p nu se mai gaseste pe nici unul din nivelele anterioare 1, 2, ., p-1. Dar pentru a nu lua drept solutii valide doua seturi cu aceleasi elemente in ordini diferite se pune conditia ca elementele unei solutii sa fie in ordine descrescatoare. Astfel pentru n=4 si k=3, dintre seturile , , , , , , va fi considerata solutie valida doar .
O valoare pusa pe un nivel p al stivei a generat o solutie finala, daca p = k.
program combinari;
uses wincrt;
var st: array[1..50] of byte;
n,
k: byte:
procedure initializare;
var i: byte;
begin
clrscr;
repeat
gotoxy(5, 1); clreol;
write('Numarul de elemente de combinat: '); readln(n)
until n in [1..50];
repeat
gotoxy(5, 2); clreol;
write('Numarul elementelor dintr-o combinatie: '); readln(k)
until k <= n;
for i := 1 to 50 do
st[i] := 0
end;
function validare(p: byte): boolean;
var i: byte;
begin
validare := true;
for i := 1 to p - 1 do
if st[p] <= st[i] then
begin
validare := false;
exit
end
end;
procedure afisare;
var i: byte;
begin
for i := 1 to p do
write(st[p]:4, ' ');
writeln
end;
procedure bktr(p: byte);
var j: byte;
begin
if n = 1 then
begin
writeln('Combinari de 1 = ', 1);
exit
end;
for j := 1 to n do
begin
st[p] := j;
if validare(p) then
if p = n then
afisare(p)
else
bktr(p + 1)
end
end;
BEGIN
initializare;
bktr(1);
readln
END.
Enuntul problemei
Pe o tabla de sah de dimensiuni n x n sa se aranjeze n dame, astfel incat ele sa nu se atace intre reciproc (doua dame se ataca reciproc daca sunt dispuse pe aceeasi linie, coloana sau diagonala). Fiecare solutie finala se va scrie in fisier pe n randuri; fiecare rand corespunde unei linii a tablei de sah si contine o succesiune de caractere 'D' si '*', conform coloanelor de pe linia respectiva pe care se pot plasa sau nu dame.
Indicatii
Avem o tabla de sah de dimensiunea n x n si n dame numerotate 1, 2, ., n. Pe fiecare linie se va pune numai o dama, evitand astfel din start atacul damelor pe linie. Notand vectorul stiva cu st, vom memora in st[p] coloana pe care se afla dama de pe linia p.
Deci, solutia finala va avea n nivele, corespunzatoare celor n linii ale tableide sah. Conditiile ca dama st[p] sa nu produc atacuri pe coloane sau diagonale sunt:
pentru ca damele sa nu atace pe coloana: coloana ocupata de dama de pe linia p, nu trebuie sa mai fie intalnita printre coloanele ocupate de catre damele de pe liniile anterioare, adica valoarea st[p] sa nu mai apara pe unul din nivelele anterioare 1, 2, ., p-1. Conditia de validare este ca st[p] <> st[i], oricare ar fi i = 1, 2, ., p-1;
pentru ca damele sa nu se atace pe diagonala: din punct de vedere geometric, damele nu trebuie sa se afle pe varfurile ipotenuzei virtualului triunghiului dreptunghic isoscel ce se poate forma (vezi figura).
|
nivel 4 | |||||||
|
D |
nivel 3 | ||||||
|
nivel 2 | |||||||
|
D |
nivel 1 | ||||||
|
stiva |
|||||||
Pentru a determina conditiile de validare astfel ca doua dame sa nu se atace pe diagonala vom considera doua pozitii ipotetice, ca in figura urmatoare (zona hasurata reprezinta tabla de sah, iar prin litera D am marcat pozitia damei):
Daca am fi pe nivelul p=3 (linia 3 a tablei de sah) si am plasa o dama in coloana 1 (st[3] = 1), aceasta s-ar ataca cu dama plasata in coloana 3 pe nivelul 1 (st[1] = 3). Deci, avem:
st[p] = st[3] = 1 si st[i] = st[1] = 3
Se poate observa ca: | stp] - st[i] | = | p - i |
Rezulta ca pentru ca dama de pe nivelul p sa nu se atace cu damele plasate pe nivelele anterioare trebuie ca | stp] - st[i] | <> | p - i |, oricare ar fi i = 1, 2, ., p - 1.
program sah_dame;
uses wincrt;
var st: array[1..25] of integer;
n,
j: integer;
fis: text;
linie: string;
gasit: boolean;
procedure initializare;
var i: integer;
begin
repeat
clrscr;
write('Introduceti dimensiunea tablei de sah: '); readln(n)
until n in [1..25];
for i := 1 to 25 do
st[i] := 0
end;
function validare(p: integer): boolean;
var i: integer;
begin
validare := true;
for i := 1 to p - 1 do
if (st[p] = st[i]) or (abs(st[p] - st[i]) = abs(p - i)) then
begin
validare := false;
exit
end
end;
procedure scriere;
var i, j: integer;
begin
for i := 1 to n do
begin
for j := 1 to n do
if st[i] = j then
write(fis, 'D')
else
write(fis, '*');
writeln(fis)
end;
writeln(fis);
gasit := true
end;
procedure bktr(p: integer);
var v: integer;
begin
for v := 1 to n do
begin
st[p] := v;
if validare(p) then
if p = n then
scriere
else
bktr(p + 1)
end
end;
BEGIN
clrscr; gasit := false;
assign(fis, 'dame.txt');
rewrite(fis);
initializare;
bktr(1);
close(fis);
if gasit then
begin
writeln('Solutiile gasite sunt:');
reset(fis);
while not eof(fis) do
begin
readln(fis, linie);
writeln(linie)
end;
close(fis);
end
else
writeln('Nu s-a gasit o solutie valida');
readln
END.
Enuntul problemei
Fiind date n multimi A1, A2, ., An sa se afiseze produsul cartezian A1 * A2 * . * An.
Indicatii
Pentru a se putea rezolva recursiv aceasta problema se introduce o simplificare: in loc sa se genereze produsul cartezian al multimilor date, se va forma produsul cartezian al multimii indicilor I1 * I2 * . * In. De exemplu, pentru n = 3 si multimile I1 = , I2 = , I3 = , produsul crtezian I1 * I2 * I3 al acestora este:
In cazul general, fiecare solutie finala va fi o configuratie a stivei (st[1], st[2], ., st[n]), in care st[i] este un element al multimii Ii cu numarul de ordine i, i = 1, 2, ., n. In exemplu anterior, solutia este formata din st[1]=3 un element al multimii I1, st[2]=1 un element al celei de-a doua multimi I2 si st[3]=1 un element al celei de-a treia multimi I3.
program ProdusCartezian;
uses wincrt;
var
nr,
st:array[1..50] of integer;
n: integer;
procedure initializare;
var i: byte;
begin
repeat
clrscr;
write('Numarul de multimi: ');
readln(n)
until n in [1..50];
for i := 1 to n do
begin
write('Numarul elementelor din multimea ', i:2, ' este: ');
readln(nr[i])
end;
for i := 1 to 50 do
st[i] := 0
end;
function validare(p: integer): boolean;
begin
validare := true
end;
procedure afisare(p: integer);
var i: integer;
begin
for i := 1 to p do
write(st[i]:4, ' ');
writeln
end;
procedure bktr(p: integer);
var k: integer;
begin
if p = n + 1 then
afisare(p - 1)
else
for k := 1 to nr[p] do
begin
st[p] := k;
if validare(p) then
bktr(p+1)
end
end;
BEGIN
initializare;
bktr(1);
readln
END.
Enuntul problemei
Se dau n cuburi numerotate 1, 2, ., n, de laturi Li si culori Ci, i = 1, 2, ., n (fiecare culoare este codificata printr-un caracter). Sa se afiseze toate turnurile ce se pot forma luand k cuburi din cele n disponibile, astfel incat:
laturile cuburilor din turn sa fie in ordine descrescatoare;
culorile a oricare doua cuburi alaturate din turn sa fie diferite.
Indicati
Tinand cont ca trebuie sa formam turnuri din k cuburi din cele n cuburi disponibile, inseamna ca avem de rezolvat o problema de tipul combinarilor de n luate cate k, doar ca difera conditiile de validare.
In afara de vectorul stiva, in program trebuie sa mai definim doi vectori latura si culori, pentru laturile respectiv culorile cuburilor.
latura[i] - reprezinta latura cubului cu numarul de ordine i;
culori[i] - reprezinta culoarea cubului cu numarul de ordine i.
Un turn inseamna o solutie finala, adica o configuratie (st[1], st[2], ., st[k]), unde fiecare element este numarul de ordine al unui cub din turn.
Conditiile de validare:
pentru laturi: latura[p] > latura[i], pentru orice i=1, 2, ., p-1;
pentru culori: culori[p] <> culori[p-1].
program TurnuriDeCuburi;
uses wincrt;
var stiva,
latura: array[1..25] of integer;
culori: array[1..25] of char;
n,
k: integer;
procedure initializare;
var
i: integer;
begin
repeat
clrscr;
write('Introduceti numarul total de cuburi: '); readln(n)
until n in [1..25];
repeat
gotoxy(1, 2) ; clreol;
write('Introduceti numarul de cuburi pentru un turn: ');
readln(k)
until k <= n;
writeln('Introduceti laturile cuburilor: ');
for i := 1 to n do
begin
write('Latura cubului[', i, ']= ');
readln(latura[i]);
end;
writeln('Introduceti culorile cuburilor:');
for i := 1 to n do
begin
write('Culoarea cubului[', i, ']= ');
readln(culori[i]);
end;
for i := 1 to n do stiva[i] := 0
end;
procedure afisare(p: integer);
var j: integer;
begin
for j := 1 to p do
write(stiva[j]:4, ' ');
writeln
end;
function validare(p: integer): boolean;
var j: integer;
begin
validare := true;
for j := 1 to p - 1 do
begin
if latura[stiva[p]] <= latura[stiva[j]] then
begin
validare := false;
exit
end;
if culori[stiva[p]] = culori[stiva[j]] then
begin
validare := false
end
end;
end;
procedure bktr(p:integer);
var j: integer;
begin
for j := 1 to n do
begin
stiva[p] := j;
if validare(p) then
if p = k then
afisare(p)
else
bktr(p + 1)
end
end;
BEGIN
initializare;
bktr(1);
readln
END.
|
