Programarea calculatoarelor-

Algoritmi

Semestrul 2

Curs 2

Cuprins

2. Metode de programare

recursive/nerecursive

2.1. Metoda backtracking

2.2. Metoda divide et impera

3

2. Metode de programare

recursive/nerecursive

2.1. Metoda backtracking

Exist aplicaii pentru care trebuie determinat

configuraia unui set de date de intrare ce maximizeaz

sau minimizeaz o anumit funcie

Astfel de probleme se numesc probleme de optimizare,

iar funcia respectiv se numete funcie criteriu sau

funcie obiectiv

4

O prim modalitate de rezolvare:

- considerarea tuturor combinaiilor posibile ale

candidailor

- evaluarea funciei criteriu pentru fiecare combinaie

Aceast metod (algoritm) se numete metoda forei

brute (brute force):

cel mai adesea, necesit un timp de calcul

exponenial

n multe cazuri numrul total de combinaii poate

atinge dimensiuni astronomice

5

Optimizare prin reguli specifice problemei care:

fie permit selectarea combinaiilor ce vor fi evaluate

mai nti

fie permit eliminarea anumitor combinaii fr ca

acestea s mai fie evaluate

O alt abordare - utilizarea constrngerilor pentru a

reduce numrul de combinaii pentru care se evalueaz

funcia criteriu

Metoda backtracking face parte din aceast categorie i

este de fapt, o rafinare a metodei forei brute

6

Principiul:

In metoda backtracking standard, soluia se poate reprezenta sub forma unui vector (tablou unidimensional) X:

X(x1,x2,, xn) S=S1xS2xxSn

unde:

S este spaiul soluiilor posibile, spaiu care este finit (produs cartezian a Si )

xi, i=1,...n, sunt componentele soluiei S, care pot s aib valori n domeniile Si

Metoda i propune s determine toate soluiile rezultat posibile

In backtracking se traverseaz

spaiul soluiilor pn la gsirea

unei soluii finale cu revenire

pe urma lsat

Soluiile date de backtracking trebuie s satisfac un set

de constrngeri:

explicite - reguli ce definesc (restrng) setul de valori

pentru fiecare component

implicite - determin care combinaii din spaiul soluiilor

satisfac funcia criteriu

8

Caracteristici:

soluia final se construiete secvenial;

se pornete cu un vector gol i la fiecare pas se extinde

vectorul parial cu o nou valoare pentru acea

component;

pe msura utilizrii unei noi valori la o component, se

evalueaz funcia criteriu;

dac valoarea adugat conduce la o soluie posibil,

se trece la urmtoarea component

9

Caracteristici:

dac valoarea considerat nu conduce la o soluie plauzibil, se alege o alt valoare din alternativele posibile pentru acea component ;

procesul continu secvenial pan se obine o soluie final.

aici se continu cutarea altor valori, iar dac alternativele posibile asociate unei componente sunt epuizate, se revine la componenta anterioar (revenire pe urm);

procesul revenirii continu, iar dac n urma revenirii nu mai sunt componente (e prima component a soluiei), procesul se ncheie.

10

De obicei, se folosesc funcii recursive:

fiecare instan se ocup de o nou component i

prelucreaz toate valorile posibile pstrnd numai

acea valoare care este consistent cu urmtorul apel

recursiv

Exist i variante implementate nerecursiv (iterative)

11

Att n varianta recursiv ct i n cea nerecursiv, iniial

se determin (citesc) date referitoare la:

numrul componentelor, n;

domeniul valorilor, h;

alte date necesare pentru elaborarea algoritmului

In C/C++ considerm o soluie sub forma unui vector:

x[k], k=0,,n-1 i x[k]=1,,h,

deci soluia are n componente 0,...,n-1, fiecare

component avnd valori n domeniul 1,...,h.

12

Concluzie:

La orice problem de backtracking stabilim:

1. k = 0,,n-1, numrul de componente ale soluiei;

2. x[k]=1,,h, domeniul valorilor posibile ale unei

componente;

3. posibil(k), condiia de continuitate

13

14

Varianta nerecursiv

//initializari pas si componente solutie

k = 0;

x[k] = 0;

// repeta cat timp exista componente

do {

// atata timp cat mai sunt valori de ales pentru o //componenta

while( x[k] < h )

{

// trec la urmatoarea valoare

x[k] = x[k]+1;

15

//daca solutia partiala este posibila

if (posibil(k))

{

// daca am ajuns la o solutie completa

if ( k==n-1)

afiseaza_solutia(X);

else {

// trec la urmatoarea componenta

k = k+1;

x[k] = 0;

}

}

}//while

k = k-1; // pasul inapoi (componenta anterioara)

} while(! (k=0) nu mai exista componente

16

Varianta recursiv

void Backtracking(int k)

{

// pentru toate valorile pe care le poate lua x[k]

for(int i=1; i

17

Apel n main( ):

// initializari

Backtracking(0);

Funcia posibil( ) d condiia de continuitate (condiie

intern) care stabilete ce relaii trebuie respectate ntre

componentele unei soluii i returneaz:

TRUE dac soluia parial este corect i se poate

continua;

FALSE n caz contrar

18

Exist variante de backtracking n care soluiile nu au

aceeai lungime (nr. variabil de componente) sau se cere

obinerea unor soluii optimale, etc.

Exemple:

1. colorarea benzilor unui drapel cu n benzi avnd h culori

disponibile, benzile alturate avnd culori diferite (numr

fix de componente)

2. descompunerea unui numr n, n sum de numere

naturale (numr variabil de componente)

3. problema comis-voiajorului

19

Problema drapelului varianta nerecursiv

#include

#define DIM 5

int posibil(int);

void afis_sol(void);

int x[DIM],n;

void main(void)

{

int k,h;

printf("\nIntrodu numarul de culori ale unui drapel(benzi,

20

k=0;

x[k]=0;

do

{

while(x[k] < h) // mai sunt valori posibile pentru // componenta k

{

x[k]++; //trec la urmatoarea valoare

if(posibil(k))

if(k==(n-1)) afis_sol(); //e gata solutie

else {k++; x[k]=0; } // trec la urmatoarea // componenta cu // valori de la zero

}//while

k--; // nu mai sunt valori pentru componenta k. Revin la // componenta k-1

}while(!(k=0

}//main

21

int posibil(int k)

{

if(k==0)return 1; //initial totul este posibil

if(x[k-1]==x[k]) return 0; // doua culori alaturate // identice - nu e posibil

return 1; //culorile alaturate nu sunt identice

}//posibil

void afis_sol(void)

{

for(int i=0;i

22

Problema drapelului - Varianta recursiv

#include

#define DIM 5

int posibil(int);

void afis_sol(void);`

void dr_rec(int k);

int x[DIM],n;

int h;

void main(void)

{

printf("\nIntrodu numarul de culori ale unui drapel(benzi,

23

void dr_rec(int k)

{

for(int i=1;i

24

Descompunerea numrului - Varianta iterativ

#define DIM 20

int posibil(int k, int &s);

void afis_sol(int k);

int x[DIM], n;

void main(void)

{

int k,sum;

printf("\nNumarul ce va fi descompus(

25

do { while(x[k] < n)

{

x[k]++;

if(posibil(k, sum)) {

if(sum == n) // solutia finala

afis_sol(k);

else {

k++;

x[k] = 0;

}

}

} // bucla valori componenta

k--; // pas inapoi

} while(!(k < 0)); // bucla componente

}

26

Descompunerea numrului - Varianta recursiv

#include

#define DIM 20

void back_SubSet(int n);

int posibil(int k, int &s);

void afis_sol(int k);

int x[DIM], n;

void main(void){

printf("\nNumarul ce va fi descompus(

27

void back_SubSet(int k)

{

int sum;

x[k] = 0;

// pentru toate valorile pe care le poate lua x[k]

while(x[k] < n)

{

x[k]++;

if(posibil(k, sum)) // solutie posibila

{

if(sum == n) // solutie completa

afis_sol(k);

else

back_SubSet(k+1);

}

}

}

28

int posibil(int k, int &s)

{

s=0;

if(k==0) return 1; // initial totul este posibil

if(x[k] > x[k-1]) {

for( int i=0; i

29

Problema Comis voiajorului varianta recursiv

/*n orase intre care pot exista legaturi directe cu un cost dat in COST[n][n], daca nu, e 0. Pornind din orasul i sa se determine ruta pe care o foloseste pentru a merge doar o data in cele n orase cu cost minim si a reveni */

#include

#include

#define MAX 7

void gene(int k); //metoda recursiva

void cit(int [][MAX],int &);

void afis(int [][MAX],int &);

int max_cost(int [][MAX],int &);

void afis_sol(long &);

int posibil(int);

int x[MAX],Y[MAX]; //x componentele solutiei, rezultatul Y

int COST[MAX][MAX];

int n;

long cost_M,C;

30

void main(void)

{

int k;

printf("Introdu dim matrice costuri(nr.orase)

31

int posibil(int k)

{

if(k==0)return 1;

if(COST[x[k-1]][x[k]]!=0){//drum direct

for(int i=0;i

32

void gene(int k)

{

for(int i=0;i

33

Concluzii

Soluia se determin printr-o cutare sistematic n

spaiul soluiilor

Se construiete vectorul soluie (tabloul unidimensional) component cu component i se testeaz la fiecare pas dac vectorul parial are anse de succes:

dac da, se continu

dac nu, vectorul parial este ignorat

34

Concluzii:

Etape specifice metodei backtracking: Specificarea vectorului soluie X[N]:

dimensiunea N,

semnificaia elementelor X[i],

domeniului valorilor pentru X[i](constrangeri explicite),

valoarea de pornire a0,

constrngerile (implicite) pentru componentele vectorului (ce satisfac obtinerea soluiei)

Se implementeaz funcia posibil() ce va verifica respectarea constrngerilor implicite

Metoda nu se aplic acolo unde dimensiunea vectorului soluie ar putea fi foarte mare datorit timpului mare de determinare a soluiilor

35

Exemple de probleme ce se preteaz la rezolvarea prin metoda backtracking (laborator) :

- colorarea unui drapel cu n benzi, fiecare band putnd avea h culori

problema damelor de ah: se cere s se plaseze N dame pe o tabl de ah de dimensiune NxN, fr s se atace una pe alta;

problema investirii optime de capital: pentru un investitor cu un capital C i n oferte la care trebuie avansate fondurile fi si care aduc beneficiile bi, se cere selectarea acelor oferte care i aduc beneficiul maxim;

36

determinarea petelor de culoare de arie maxim pentru o imagine reprezentat sub forma unei matrici cu NL linii i NC coloane care conine NG nuane de gri;

- traseul comis-voiajorului : stabilirea celui mai scurt traseu fiind date o localitate de pornire, n localiti ce trebuie vizitate o singur dat, revenirea fiind obligatorie la localitatea de pornire (comis voiajor, algoritmul de rutare a pachetelor Bellman-Ford, Dijkstra).

problema sumei subseturilor: se considera un set P de n numere pozitive P(p0, p1, ..., pn-1) i M un numr pozitiv; s se gseasc toate subseturile lui P pentru care suma numerelor este M;

37

2. METODE DE PROGRAMARE

RECURSIVE/NERECURSIVE

2.2. Metoda divide et impera

Principiul propus de metod:

se descompune problema n subprobleme, n mod

recursiv, pn cnd ajungem la o subproblem pe

care o putem rezolva direct

soluiile subproblemelor se vor combina obinnd

soluia final a problemei

38

Cutarea binar

Fie un ir de elemente ordonat. Se pune problema gsirii

unui element (cheia) n ir.

Descompunerea problemei :

se compar cheia cu valoarea din mijloc

dac avem egalitate am gsit poziia n ir

dac nu, vom ti n care din cele dou jumti de ir

trebuie s cutm mai departe pornind de la valoarea

comparat

se continu n acest mod pn cnd gsim elementul n

ir sau pn cnd vom ajunge la un ir vid

39

Valoarea cutat: 23

40

Valoarea cutat: 88

41

Funcia de cutare va returna poziia n ir dac s-a gsit elementul dat sau valoarea (-1) n caz de insucces:

int CautareBinara(int *p, int inc, int sfr, int val)//recursiv

{

int mij;

mij = (inc + sfr)/2;

if(p[mij] == val)

return mij;

if(inc val)

sfr = mij - 1;

else

inc = mij + 1;

return CautareBinara(p, inc, sfr, val);

}

return -1;

}

42

Problema turnurilor din Hanoi

Fie 3 tije A, B, C, i n discuri de diametre diferite, iniial puse pe tija A astfel nct orice disc este aezat peste un disc de diametru mai mare

Dac numerotm discurile n ordinea cresctoare a diametrelor:

discul 1 are diametrul cel mai mic, apoi discul 2, .a.m.d., discul n avnd diametrul cel mai mare,

atunci discul 1 se afl n vrf, discul n fiind la baz

43

Se cere s se mute discurile de pe tija A pe tija B

respectnd urmtoarele reguli:

la fiecare pas se va muta un singur disc

discurile vor forma secvene descresctoare pe oricare

din cele 3 tije, deci peste discul k se pot aeza doar

discurile 1, 2, , k-1

tija C va fi folosit ca i tij de manevr

Se cere i determinarea numrului de micri efectuate

Problema se rezolv recursiv n 3 etape, cunoscnd

rezolvarea pentru (n-1) discuri

44

Etapa1: Se deplaseaz discurile 1, 2, , n-1 de pe tija A pe C astfel:

45

Etapa2: Discul n se mut de pe tija A pe tija B astfel:

46

Etapa3: Se deplaseaz cele (n-1) discuri de pe tija C pe B astfel:

47

Practic, problema turnurilor din Hanoi cu n discuri s-a

redus la rezolvarea aceleiai probleme cu n-1 discuri, pe

care tim s o rezolvm dac tim pentru n-2 discuri

.a.m.d., tim s o rezolvm dac o tim rezolva pentru

n=1

Dar pentru n=1, practic se mut discul de pe tija surs A

pe cea destinaie B

48

Cele 3 tije pot s fie n situaiile:

Surs: discuri care trebuie transportate pe alt tij

Destinaie: tija pe care se afla discurile transferate de pe surs

Manevr: tija folosit pentru stocarea temporar a discurilor

Rolul tijelor se schimb n cele 3 etape diferite ale procesului de deplasare a discurilor

Pentru rezolvare se definete o funcie recursiv:

void hanoi(int n, char a, char b, char c);

int n, numrul de discuri;

char a, tija surs;

char b, tija destinaie;

char c, tija de manevr

49

double mutari; // numar de mutari

void hanoi(int n, char a, char b, char c);

void main( )

{

int n;

cout n;

mutari = 0;

hanoi(n,'A','B','C');

cout

50

void hanoi(int n, char a, char b, char c)

{

if (n==1) {

printf("Se muta discul 1 de pe tija %c pe tija %c\n",a, b);

mutari++;

getch( );

return;

}

// n>1, Etapa 1, n-1 discuri, a-sursa, c-destinatia, b-manevra

hanoi(n-1, a, c, b);

// Etapa 2, discul n de pe tija a se muta pe b

printf(Se muta discul %d de pe tija %c pe tija %c\n",n, a, b);

mutari++;

getch( );

//Etapa 3, n-1 discuri, c-sursa, b-destinatia, a-manevra

hanoi(n-1,c, b, a);

}

51

Maximul unui ir

Abordarea recursiv:

se descompune irul n 2 subiruri

se determin maximul pentru fiecare subir

se determin maximul dintre cele dou maxime

pentru fiecare subir se procedeaz n acelai mod

pn cnd ajungem la un ir de lungime 1

52

determinarea maximului unui ir cu ajutorul funciei

recursive m_max( ):

int m_max(int *vector, int pozi, int len);

irul este introdus de la intrarea standard (cu funcia

citire_sir( )), ir cu o lungime mai mic dect o valoare

MAX dat

irul va fi afiat cu funcia tip_sir( )

53

#define MAX 8

void citire_sir(int*, int);

void tip_sir(int*, int);

int m_max(int*, int, int);

void main( )

{

int n, Maxim;

int vect[MAX];

cout

54

int m_max(int *vector, int pozi, int len)

{

int a,b;

if(len == 1)

return *(vector+pozi);

else

{

a = m_max(vector, pozi, len/2);

b = m_max(vector, len/2+pozi, len/2+len%2);

if(a>b)

return a;

else

return b;

}

}

55

void citire_sir(int* v, int n)

{

// corp functie

}

void tip_sir(int* v, int n)

{

// corp functie

}