Metode generale de elaborare a algoritmilor (i)

METODE GENERALE DE ELABORARE A ALGORITMILOR (I)

1.Continutul lucrarii

In lucrare sunt prezentate principiile metodelor Greedy si backtracking, variantele lor de aplicare si exemple.

2.Consideratii teoretice

2.1.Metoda Greedy.

Metoda Greedy se aplica urmatoarelor tipuri de probleme:

Dintr-o multime A de n elemente se cere determinarea unei submultimi B care sa indeplineasca anumite conditii pentru a fi acceptata.

Numele metodei vine de la urmatorul fapt: se alege pe rand cate un element din multimea A si eventual se introduce in solutie.

Se mentioneaza faptul ca o data ce un element a fost ales el ramane in solutia finala, iar daca un element a fost exclus, el nu va mai putea fi reconsiderat pentru includere in solutie.

Metoda determina o singura solutie.

Exista doua variante de rezolvare a unei probleme cu ajutorul metodei Greedy:

a)         Varianta I

Se pleaca de la multimea B vida. Se alege din multimea A un element neales in pasii precedenti. Se cerceteaza daca adaugarea la solutia partiala B conduce la o solutie posibila. In caz afirmativ se adauga elementul respectiv la B.

Descrierea variantei este urmatoarea:

#define max  

GREEDY1(int A[max], int n, int B[max], int *k)

/* A este multimea de n elemente date;

B este multimea extrasa de k elemente */

}

In varianta I a metodei, functia ALEGE stabileste criteriul care duce la solutia finala.

b)         Varianta II

Se stabileste de la inceput ordinea in care trebuie considerate elementele multimii A. Apoi se ia pe rand cate un element in ordinea stabilita si se verifica daca prin adaugare la solutia partiala B anterior construita, se ajunge la o solutie posibila. In caz afirmativ se face adaugarea.

Descrierea variantei este urmatoarea:

#define max  

GREEDY2(int A[max], int n, int B[max], int *k)

/* A este multimea de n elemente date;

B este multimea extrasa de k elemente */

Dificultatea elaborarii functiei PRELUCRARE este identica cu cea a functiei ALEGE din varianta precedenta.

Exemplu: Determinarea arborelui de acoperire de cost minim prin algoritmul lui Prim.

Problema a fost enuntata in cadrul lucrarii nr.7 paragraful 2.3.

Algoritmul consta in urmatoarele:

a)     Initial se ia arborele ce contine un singur varf. S-a demonstrat ca nu are importanta cu care varf se incepe; ca urmare se ia varful 1. Multimea arcelor este vida.

b)    Se alege arcul de cost minim, care are un varf in arborele deja construit, iar celalalt varf nu apartine arborelui. Se repeta in total acest pas de n-1 ori.

Pentru evitarea parcurgerii tuturor arcelor grafului la fiecare pas, se ia vectorul v avand n componente definit astfel:

daca varful i apartine arborelui deja construit

daca varful i nu apartine arborelui deja construit; k este varful arborelui deja construit a. i. muchia (i, k) este de cost minim.

Initial v[1]=0 si v[2]=v[3]==v[n]=1, adica initial arborele este A =(, Ø).

/*Algoritmul lui Prim */

#include <stdio.h>

#include <conio.h>

#define nmax 10

#define MAX 0x7fff

void prim(int n,int c[nmax][nmax],

int muchii[nmax][2],int *cost)

/* n -numarul nodurilor;

c - matricea costurilor;

muchii-muchiile arborelui de acoperire de cost minim;

cost-costul arborelui de acoperire de cost minim */

{

int v[nmax]; /* v[i]=0 daca i apartine arborelui;

v[i]=j daca i nu apartine arborelui.

j este nodul din arbore a.i.

Analiza: Documente specifice operatiilor cu numerar Eseu: Forma de contabilitate utilizata la o societate comerciala

muchia (i,j) este de cost minim */

int i,j,k,minim;

*cost=0;

v[1]=0;

for(i=2;i<=n;i++) v[i]=1; /*arborele este (,) */

/* determinarea celor n-1 muchii */

for(i=1;i<=n-1;i++)

muchii[i][0]=v[j];

muchii[i][1]=j;

*cost=*cost+c[j][v[j]];

/*reactualizare vector v */

v[j]=0;

for(k=1;k<=n;k++)

if(v[k]!=0)

if(c[k][v[k]]>c[k][j]) v[k]=j;

}

}

void main()

}

while(j>0);

};

prim(n,c,muchii,&cost);

printf('nCOSTUL ARBORELUI = %d',cost);

printf('nMUCHIILE ARBORELUI COSTUL MUCHIEIn');

for(i=1;i<=n-1;i++)

printf(' %2d - %2d %10dn',muchii[i][0],muchii[i][1],

c[muchii[i][0]][muchii[i][1]]);

getch();

}

Metoda backtracking

Metoda backtracking se aplica algoritmilor pentru rezolvarea urmatoarelor tipuri de probleme:

Fiind date n multimi S₁, S₂, S_n, fiecare avand un numar nrs_i de elemente, se cere gasirea elementelor vectorului X =(x₁, x₂, x_n) Є S=S₁xS₂x . S_n, astfel incat sa fie indeplinita o anumita relatie φ(x₁, x₂, . ,x_n) intre elementele sale.

Relatia φ(x₁, x₂, . ,x_n) se numeste relatie interna, multimea S=S₁xS₂x . S_n se numeste spatiul solutiilor posibile, iar vectorul X se numeste solutia rezultat.

Metoda backtracking determina toate solutiile rezultat ale problemei. Dintre acestea se poate alege una care indeplineste in plus o alta conditie.

Metoda backtracking elimina generarea tuturor celor posibilitati din spatiul solutiilor posibile. In acest scop la generarea vectorului X, se respecta urmatoarele conditii:

a)        x_k primeste valori numai daca x₁, x₂, ,x_k-1 au primit deja valori;

b)        dupa ce se atribuie o valoare lui x_k, se verifica relatia numita de continuare φ^{`</sup>(x<sub>1</sub>, x<sub>2</sub>, . ,x<sub>k</sub>), care stabileste situatia in care are sens sa se treaca la calculul lui x<sub>k+1</sub>. Neindeplinirea conditiei φ<sup>`} exprima faptul ca oricum am alege x_k+1, x_k+2, ,x_n nu se ajunge la solutia rezultat. In caz de neindeplinire a conditiei φ^{`</sup>(x<sub>1</sub>, x<sub>2</sub>, . ,x<sub>k</sub>), se alege o noua valoare pentru x<sub>k</sub> Є S<sub>k</sub> si se reia verificarea conditiei φ<sup>`}. Daca multimea de valori x_k s-a epuizat, se revine la alegerea altei valori pentru x_k-1 s.a.m.d. Aceasta micsorare a lui k da numele metodei, ilustrand faptul ca atunci cand nu se poate avansa se urmareste inapoi secventa curenta din solutia posibila. Intre conditia interna si cea de continuare exista o stransa legatura. Stabilirea optima a conditiilor de continuare reduce mult numarul de calcule.

Algoritmul backtracking este redat sub forma nerecursiva astfel:

#define nmax

backtracking_nerecursiv(int n)

/* se considera globale multimile S_i si numarul lor de elemente nrs_i */

if (v==0) k=k-1;

else if (k==n) afisare (x, n); /* afisarea sau eventual prelucrarea solutiei */

else k=k+1;

}

Sub forma recursiva, algoritmul backtracking poate fi redat astfel:

#define nmax

int x[nmax];

/* se considera globale n, multimile S_i si numarul lor de elemente nrs_i */

backtracking_recursiv(int k)

}

Apelul se face:

backtracking_recursiv(1);

Exemplu: Problema damelor de sah.

Se cere gasirea tuturor solutiilor de asezare pe tabla de sah de n linii si n coloane a n dame, astfel incat ele sa nu se atace. Se considera ca ele se ataca daca sunt pe aceeasi linie, coloana sau diagonala.

Intrucat pe o linie se gaseste o singura dama, solutia se prezinta sub forma de vector

x =(x₁, x₂, ,x_n), unde x_i reprezinta coloana pe care se afla dama in linia i.

Conditiile de continuare sunt:

a)    

doua dame nu se pot afla pe aceeasi coloana, adica:

b)    

doua dame nu se pot afla pe aceeasi diagonala, adica:

Varianta nerecursiva este urmatoarea:

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#define nmax 10

void dame_nerecursiv(int n)

/* functia gaseste toate asezarile posibile pe o tabla

de sah de n*n patrate pentru ca n dame sa nu se atace */

if(v==0) k=k-1;

else ;

getch();

else ;

void main(void)

Varianta recursiva este urmatoarea:

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#define nmax 10

/* Varianta recursiva a problemei damelor */

int n; /*dimensiunea (ordinul) tablei de sah */

int nr_solutie;

int x[nmax];

int FI(int k)

void back_recursiv(int k)

;

getch();

}

}

}

void main(void)

Mersul lucrarii

Utilizand metoda Greedy sa se rezolve urmatoarele probleme:

Se dau m vectori V₁, V₂, V_m, care contin n₁, n₂, n_m elemente, ordonate crescator dupa o cheie. Se interclaseaza vectorii dati, obtinandu-se un vector de lungime n₁+n₂++n_m elemente, ordonate crescator. Se stie ca interclasarea a doi vectori care contin n₁, respectiv n₂ elemente necesita un timp proportional cu suma lungimilor lor. Sa se determine ordinea optima in care trebuie efectuata interclasarea tuturor vectorilor dati.

Problema rucsacului. Greutatea maxima care poate fi transportata cu un rucsac este G. Dandu-se n materiale, fiecare avand greutatea m si costul C pe unitatea de greutate, sa se gaseasca ce cantitate din fiecare material sa fie introdus in rucsac pentru ca sa se obtina castigul maxim. Se vor deosebi doua cazuri:

a)     un material poate fi luat numai in intregime;

b)     se poate lua o fractiune din material.

3.3 Problema activitatilor. Exista o multime S=1, 2, 3, , n de n activitati care doresc sa foloseasca o aceeasi resursa (de exemplu o sala de clasa). Aceasta resursa poate fi folosita de o singura activitate la un anumit moment de timp. Fiecare activitate i are un timp de pornire tp_i si un timp de terminare tf_i (tp_i < tf_i). Daca este selectata activitatea i, ea se desfasoara pe durata [tp_i, tf_i). Spunem ca activitatile i si j sunt compatibile daca duratele lor nu se intersecteaza. Sa se selecteze o multime maximala de activitati mutual compatibile.

Utilizand metoda backtracking sa se rezolve urmatoarele probleme:

3.4.Colorarea grafurilor. Fiind dat un graf neorientat G =(X, Γ) unde X este multimea formata din n noduri, iar Γ este multimea muchiilor si un numar de m culori, se cere sa se determine toate colorarile posibile ale nodurilor grafului folosind cele m culori, astfel incat oricare doua noduri adiacente sa fie colorate in mod diferit.

3.5.Problema ciclului hamiltonian. Se da un graf conex neorientat G =(X, Γ) prin matricea costurilor pozitive.

Se cere sa se determine ciclul hamiltonian de cost minim (ciclul hamiltonian este un ciclu care trece prin toate nodurile).

3.6. Fiind data o matrice A de elemente numere naturale, sa se determine cea mai mica suma de n elemente luate din linii diferite si coloane diferite.

3.7.Fiind date o tabla de sah de dimensiune patrate si un cal plasat in patratul din stanga sus al tablei, sa se afiseze toate posibilitatile de mutare a calului astfel incat sa treaca o singura data prin fiecare patrat al tablei.

3.8.Un labirint este codificat printr-o matrice de elemente ale carui culoare sunt reprezentate prin elemente egale cu 1, situate in pozitii consecutive pe o aceeasi linie sau coloana, celelalte elemente fiind 0. O persoana se gaseste in pozitia (i, j) din interiorul labirintului. Se cere afisarea tuturor traseelor de iesire din labirint care nu trec de mai multe ori prin acelasi loc.

3.9.Se considera o multime formata din n elemente numere intregi. Sa se genereze toate submultimile acestei multimi avand proprietatea ca suma elementelor lor este egala cu S.

3.10.Se dau doua multimi de numere intregi A si B. Sa se genereze toate functiile.