1

8. Metoda de programare Backtracking 8.1. Prezentare general Imaginai-v c astzi este ziua vostr i avei invitai. Aranjai o mas frumoas, apoi v gndii cum s v aezai invitaii la mas. Ai vrea s tii toate posibilitile de aezare a invitailor la mas, dar realizai n acelai timp c trebuie s inei seama i de preferinele lor. Printre invitai exist anumite simpatii dar i unele antipatii, de care dorii neaprat s inei seama, pentru ca petrecerea s fie o bucurie pentru toi. S ne gndim cum procedai pentru a identifica toate posibilitile de a plasa invitaii la mas. ncepei prin a scrie nite cartonae cu numele invitailor. Alegei un invitat. Pentru a-l alege pe al doilea, selectai din mulimea cartonaelor rmase un alt invitat. Dac tii c cele dou persoane nu se agreeaz, renuntai la cartonaul lui i alegei altul i aa mai departe. Se poate ntmpla ca la un moment dat, cnd vrei s alegei cartonaul unui invitat s constatai c nici unul dintre invitaii rmai nu se potrivete cu ultima persoan slectat pn acum. Cum procedai? Schimbai ultimul invitat plasat cu un invitat dintre cei rmai i ncercai din nou, dac nici aa nu reuiti, schimbai penultimul invitat cu alcineva i ncercai din nou i aa mai departe pn cnd reuii s plasati toi invitaii. nseamn c ai obinut o soluie. Pentru a obine toate celelalte soluii, nu v rmne dect s o luai de la nceput. Avei cam mult de muncit, iar dac numrul invitailor este mare...operaiunea devine foarte anevoioas. Iat de ce avei nevoie de un calculator i cunotine de programare .

n general vom modela soluia problemei ca un vector v=(v1,v2,v3,...,vn) n care fiecare element vk aparine unei mulimi finite i ordonate Sk, cu k=1,n. n anumite cazuri particulare, mulimile S1 ,S2, S3,...,Sn pot fi identice . Procedm astfel: 1. La fiecare pas k pornim de la o soluie parial v=( v1,v2,v3,...,vk-1) determinat

pn n acel moment i ncercm s extindem aceast soluie adugnd un nou element la sfritul vectorului.

2. Cutm n mulimea Sk , un nou element. 3. Dac exist un element neselectat nc, verificm dac acest element

ndeplinete condiiile impuse de problem, numite condiii de continuare. 4. Dac sunt respectate condiiile de continuare, adugm elementul soluiei

pariale. 5. Verificm dac am obinut o soluie complet.

Backtracking este o metod de parcurgere sistematic a spaiului soluiilor posibile al unei probleme. Este o metod general de programare, i poate fi adapt pentru orice problem pentru care dorim s obinem toate soluiile posibile, sau s selectm o soluie optim, din mulimea soluiilor posibile. Backtracking este ns i cea mai costisitoare metod din punct de vedere al timpului de execuie.

2

- dac am obinut o soluie complet o afim i se reia algoritmul de la pasul 1.

- dac nu am obinut o soluie, k

3

v k=1

1 k 1 2 3 v k=2 1 1

k 1 2 3 element incorect (se repet) v k=2 1 2

k 1 2 3 v k=3 1 2 1

k 1 2 3 element incorect (se repet) v k=3 1 2 2

k 1 2 3 element incorect (se repet) v k=3 1 2 3

k 1 2 3 k=3 s-a obinut o soluie se nchide ultimul nivel de stiv pentru c nu mai sunt elemente n ultima mulime v k=2 1 3

k 1 2 3 v k=3 1 3 1

k 1 2 3 element incorect (se repet) v 1 3 2

k 1 2 3 k=3 s-a obinut o soluie v k=3 1 3 3

k 1 2 3 element incorect (se repet) v k=2 1 3

k 1 2 3 v k=1 2

k 1 2 3 se repet aceiai pai construindu-se soluiile urmtoare

STIVA i=1

STIVA

i=1 i=1

STIVA i=1,2

i=1

STIVA i=1

i=1,2

i=1

STIVA i=1,2

i=1,2

i=1

STIVA i=1,2,3

i=1,2

i=1

STIVA i=1,2,3

i=1

STIVA i=1

i=1,2,3

i=1 STIVA i=1,2

i=1,2,3

i=1

STIVA i=1,2,3

i=1,2,3

i=1

STIVA i=1,2,3

i=1

STIVA i=1,2

4

Problema generrii permutrilor, este cea mai reprezentativ pentru metoda

backtracking, ea conine toate elementele specifice metodei. Probleme similare, care solicit determinarea tuturor soluiilor posibile,

necesit doar adaptarea acestui algoritm modificnd fie modalitatea de selecie a elementelor din mulimea Sk, fie condiiile de continuare fie momentul obinerii unei soluii.

#include // PERMUTRI const MAX=20; int n,v[MAX] ; //n-nr. de elemente, v[20]-vectorul n care construim soluia int valid(int k); int solutie(int k); void afisare(int k); void BK(int k); int main() {coutn; //se citete n BK(1); return 0; //apelm funcia BK pentru completarea poziiei 1din vectorul v } void BK(int k) {int i; //i-elementul selectat din multimea Sk, trebuie sa fie variabil local, pentru // a se memora pe stiv for (i=1;i

5

2. PRODUS CARTEZIAN Se dau n mulimi, ca cele de mai jos: S1={1,2,3,...,w1} S2={1,2,3,...,w2} ......................... Sn={1,2,3,...,wn} Se cere s se gnereze produsul lor cartezian. Exemplu: pemtru n=3 i urmroarele mulimi S1={1,2} w1=2 S2={1,2,3} w2=3 S3={1,2} w3=2 produsul cartezian este: S1 xS2 xS3 ={ (1,1,1),(1,1,2),(1,2,1),(1,2,2),(1,3,1),(1,3,2),

(2,2,1),(2,1,2),(2,2,1),(2,2,2),(2,3,1),(2,3,2)} Prin urmare o soluie este un ir de n elemente, fiecare element iSi, cu i=1,n S analizm exemplul de mai sus:

1. La pasul k selectm un element din mulimea Sk ={1,2,3,...,wk}. 2. Elementele unei soluii a produsului cartezian, pot s se repete, pot fi n

orice ordine, iar valori strine nu pot apare, deoarece le selectm doar dintre elementele mulimii Sk . Prin urmare nu trebuie s impunem condiii de continuare.

3. Obinem o soluie n momentul n care am completat n elemente n vectorul v.

Vom memora numrul de elemente al fiecerei mulimi Sk , ntr-un vector w. Soluiile le vom construi pe rnd n vectorul v.

#include // PRODUS CARTEZIAN #include const MAX=20; int n,v[MAX],w[MAX]; //n-nr. de mulimi, v-vectorul soluie, w-conine nr. de elemente di //fiecare mulime Sk void BK(int k); void citire(); void afisare(int k); int solutie(int k); void main() {citire(); //citire date BK(1); //apelm funcia BK pentru selectarea primului element n v } void BK(int k) //funcia becktreacking {int i; for (i=1;i

6

3. ARANJAMENTE

Se citesc n i p numere naturale cu pn; //se citete numrul de mulimi for(i=1;i>w[i]; //se citete numrul de elemente al fiecrei mulimi f.close(); } int solutie(int k) //funcia soluie determin momentul n care se ajunge la o soluie {if (k==n) //obinem o soluie dac am dpus n vectorul v, n elemente return 1; return 0; } void afisare(int k) //afueaz o soluie {int i; for (i=1;i

7

Vom genera pe rnd soluiile problemei n vectorul v=(v1,v2,v3,...,vn), unde vkSk. S facem urmtoarele observaii:

1. Pentru aceast problem toate mulimile Sk sunt identice, Sk={1,2,3,....,n}. La pasul k selectm un element din mulimea Sk.

2. n cadrul unei combinri elementele nu au voie s se repete. S mai observm i faptul c dac la un moment dat am generat de exemplu soluia (1,2), combinarea (2,1) nu mai poate fi luat n considerare, ea nu mai reprezint o soluie. Din acest motiv vom considera c elementele vectorului reprezint o soluie, numai dac se afl n ordine strict cresctoare. Acestea reprezint condiiile de continuare ale problemei.

3. Oinem o soluie n momentul n care vectorul conine p elemente. Putem genera toate elementele unei combinri, parcurgnd mulimea {1,2,3,...,n},

apoi s verificm condiiile de continuare aa cum am procedat n cazul permutrilor. Putem ns mbuntii timpul de execuie, selectnd din mulimea {1,2,3,...,n}, la

pasul k un element care este n mod obligatoriu mai mare dect elementul v[k-1], adic i=v[k-1]+1.

Ce se ntmpl ns cu primul element plasat n vectorul v? Acest element a fost plasat pe poziia 1, iar vectorul v deine i elementul v[0] n mod implicit n C++. v[0]=0, deoarece vectorul v este o variabil global i se iniializeaz automat elementele lui cu 0. n acest fel, impunnd aceste restricii nc din momentul seleciei unui element, condiiile de continuare vor fi respectate i nu mai avem nevoie de funcia valid.

Algoritmul a fost substanial mbuntit, deoarece nu selectm toate elementele mulimii i nu verificm toate condiiile de continuare, pentru fiecare element al mulimii.

#include // COMBINRI const MAX=20; int n,p,v[MAX] ; int solutie(int k); void afisare(int k); void BK(int k); void main() {coutn; coutp; BK(1); } void BK(int k) {int i; for (i=v[k-1]+1;i

8

4. SUBMULIMI

S se genereze toate submulimile mulimii S={1,2,3, ... ,n}. Exemplu: pentru n=3, S={1,2,3}, submulimile sunt urmtoarele: -mulimea vid, {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} S observm c pentru a obine toate submulimile unei mulimi, este suficient s generm pe rnd 121 ,...,, nnnn CCC , pentru mulimea S={1,2,3, ... ,n}, la care trebuie

s adugm mulimea vid i mulimea S. n aceste condiii, este suficient s modificm doar funcia principal pentru a genera toate submulimile i afiarea datelor ca mulimi de elemente. Funiile BK i soluie genereaz n realitate pnC elemente.

#include // SUBMULIMI 1 const MAX=20; int n,p,v[MAX] ; int solutie(int k); void afisare(int k); void BK(int k); void main() {int i; coutn; cout

9

Putem construi un algoritm mai eficient pentru generarea tuturor submulimilor unei mulimi.

De exemplu dac genetm mulimile n urmtoarea ordine: mulimea vid, {1}, {1,2}, {1,2,3}, {2}, {2,3}, {3}

5. Problema celor n dame

Fiind dat o tabl de ah de dimensiune nxn, se cere s se aranjeze cele n dame

n toate modurile posibile pe tabla de ah, astfel nct s nu se afle pe aceeai linie, coloan, sau diagonal (damele s nu se atace). Exemplu pentru n=4 o soluie este:

D

D

D

D

#include //SUBMULIMI 2 const MAX=20; int n,p,v[MAX] ; int valid(int k); int solutie(int k); void afisare(int k); void BK(int k); void main() {int i; coutn; cout

10

Observm c o dam va fi plasat ntotdeauna singur pe o linie. Acest lucru ne permite s memorm fiecare soluie ntr-un vector v, considernd c o csut k a vectorului reprezint linia k iar coninutul ei, adic v[k] va conine numrul coloanei n care vom plasa regina.

Pentru exemplul de mai sus, vectorul v va avea urmtorul coninut:

2 4 1 3

1 2 3 4 S facem urmtoarele observaii: 1. Pentru aceast problem toate mulimile Sk sunt identice, Sk={1,2,3,....,n} i

reprezint numrul coloanelor tablei de ah. Indicele k reprezint numrul liniei tablei de ah. Prin urmare, la pasul k selectm un element din mulimea Sk.

2. Condiiile de continuare ale problemei : a) Damele s nu fie pe aceeai linie - aceast condiie este ndeplinit prin modul

n care am organizat memorarea datelor i anume ntr-o csu a vectorului putem trece un singur numr de coloan.

b) Damele s nu fie pe aceeai coloan adic v[k]v[i], cu 1

11

v k=1 1

v k=2 1 1

v k=2 1 2

k=2 1 3

pe linia 3 nu mai putem plasa nici o dam, selectm alt valoare pe linia 2 v k=2 1 4

v k=3 1 4 1

v k=3 1 4 2

-pe linia 4 nu putem plasa nici o dam -pe linia 3 nici o alt coloan nu este corect -pe linia 2 nu mai exist nici o poziie disponibil -se revine la linia 1 v k=1 2

v k=2 2 1

v k=2 2 2

v k=2 2 3

v k=2 2 4

v k=3 2 4 1

v k=4 2 4 1 1

v k=4 2 4 1 2

v k=4 2 4 1 3

Algoritmul continu pentru a genera

toate soluiile.

D

D D

D D

D D D

D

D D

D D

D

D D

D D

Am obinut prima soluie !

12

#include // DAME #include #define MAX 20 int n,v[MAX],sol; int valid(int k); int solutie(int k); void afisare(); void BK(int k); void main() {coutn; BK(1); } void BK(int k) {int i; for (i=1;i

13

6. Plata unei sume cu monede de valori date. Fiind dat o sum S i n monede de valori date, s se determine toate modalittile de plat a sumei S cu aceste monede. Considerm c sunt monede suficiente din fiecare tip.

#include // PLATA SUMEI #include #define MAX 20 int n=0,x,v[MAX],w[MAX],z[MAX],S,Suma,sol; //v-vectorul soluie,w-valoarea monedelor,z-nr.maxim de monede de un anumit tip void citire(); int valid(int k); int solutie(); void afisare(int k); void BK(int k); void main() {citire(); BK(1); } void BK(int k) {int i; for (i=0;i>S>>n; //se citete suma S i numrul de monede for(i=1;i>w[i]; //se citesc valorile monedelor z[i]=S/w[i];} //z-memorez numrul maxim de monede de un anumit tip, penru a plati suma S int valid(int k) {int i; Suma=0; for (i=1;i

14

7. Problema rucsacului ntr-un rucsac se poate transporta o anumit greutate maxim G. O persoan dispune de n obiecte. Pentru fiecare obiect se cunoare greutatea i

ctigul pe care persoana l poate obine transportnd acelst obiect. Ce obiecte trebuie s transporte persoana respectiv pentru a obine un ctig

maxim. Datele de intrare se citesc din fiierul RUCSAC.IN astfel: - linia 1: n G -unde n este numrul de obiecte i G greutatea maxim admis

de rucsac - linia i: nume[i] g[i] c[i]

unde: -nume este numele obiectului -g este greutatea obiectului - c este catigul obinut pentru acel obiect

cu i=1,n Exemplu: RUCSAC.IN 4 20 pantaloni 5 5 caciula 10 3 camasa 10 7 pantofi 5 2 pentru datele de intrare de mai sus, soluia optim este: Castigul maxim:14 pantaloni 5 5 camasa 10 7 pantofi 5 2

Dup cum observai prolema nu solicit obinerea tuturor soluiilor ci determinarea

soluiei optime. Pentru a determina soluia optim vom genera cu metoda backtracking toate

soluiile i vom reine dintre acestea doar soluia cea mai bun. Aceasta presupune s nu afim fiecare soluie ci, n momentul obinerii unei noi soluii o vom compara cu soluia precedent, n cazul n care ctigul obinut este mai mare dect precedentul vom reine aceast soluie. Vom considera ctigul iniial 0.

Vom folosi urmtoarele variabile:

n-numrul de obiecte G - greutatea maxim admis de rucsac nume[ ][ ] - reinem renumirea obiectelor g[ ] - reinem greutatea fiecrui obiect c[ ] -reinem ctigul pentru fiecare obiect v[ ] -vectorul soluie:

0-obiectul nu este transportat, 1-obiectul este transportat

s_max -reine ctigul maxim sol_max -reine soluia maxim

15

#include #include #include #define MAX 20 int n,v[MAX],sol_max[MAX],g[MAX],c[MAX],s,s_max,G,gr,nr_sol; char nume[MAX][MAX]; void back(int k); int valid(int k); void optim(); void citire(); void afisare(); main() {citire(); back(1); afisare(); //afisam solutia optima } void back(int k) { int i; for(i=0;i>G; //n-nr. obiecte, G-greutatea maxima for (int i=1;i>nume[i]>>g[i]>>c[i]; //se citeste greutatea si ponderea fiecarui obiect f.close(); } void afisare() { nr_sol++; cout