METODE GENERALE DE ELABORARE A ALGORITMILOR (I)
1.Continutul lucrarii
În 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 îndeplineasca anumite conditii pentru a fi acceptata.
Numele metodei vine de la urmatorul fapt: se alege pe rând câte un element din multimea A si eventual se introduce în solutie.
Se mentioneaza faptul ca o data ce un element a fost ales el ramâne în solutia finala, iar daca un element a fost exclus, el nu va mai pute 747f54h a fi reconsiderat pentru includere în 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 în pasii precedenti. Se cerceteaza daca adaugarea la solutia partiala B conduce la o solutie posibila. În 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 */
}
În varianta I a metodei, functia ALEGE stabileste criteriul care duce la solutia finala.
b) Varianta II
Se stabileste de la început ordinea în care trebuie considerate elementele multimii A. Apoi se ia pe rând câte un element în ordinea stabilita si se verifica daca prin adaugare la solutia partiala B anterior construita, se ajunge la o solutie posibila. În 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 în cadrul lucrarii nr.7 paragraful 2.3.
Algoritmul consta în urmatoarele:
a) Initial se ia arborele ce contine un singur vârf. S-a demonstrat ca nu are importanta cu care vârf se începe; ca urmare se ia vârful 1. Multimea arcelor este vida.
b) Se alege arcul de cost minim, care are un vârf în arborele deja construit, iar celalalt vârf nu apartine arborelui. Se repeta în total acest pas de n-1 ori.
Pentru evitarea parcurgerii tuturor arcelor grafului la fiecare pas, se ia vectorul v având n componente definit astfel:
daca vârful i apartine arborelui
deja construit
daca vârful i nu apartine arborelui deja construit; k este vârful arborelui deja construit a. î. 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.
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 MUCHIEI\n");
for(i=1;i<=n-1;i++)
printf(" %2d - %2d %10d\n",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 S1, S2, ... Sn, fiecare având un numar nrsi de elemente, se cere gasirea elementelor vectorului X =(x1, x2, ... xn) Є S=S1xS2x.Sn, astfel încât sa fie îndeplinita o anumita relatie φ(x1, x2, . ,xn) între elementele sale.
Relatia φ(x1, x2, . ,xn) se numeste relatie interna, multimea S=S1xS2x.Sn 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 îndeplineste în plus o alta conditie.
Metoda
backtracking elimina generarea tuturor celor 
posibilitati
din spatiul solutiilor posibile. În acest scop la generarea
vectorului X, se respecta urmatoarele conditii:
a) xk primeste valori numai daca x1, x2, ... ,xk-1 au primit deja valori;
b) dupa ce se atribuie o valoare lui xk, se verifica relatia numita de continuare φ`(x1, x2, . ,xk), care stabileste situatia în care are sens sa se treaca la calculul lui xk+1. Neîndeplinirea conditiei φ` exprima faptul ca oricum am alege xk+1, xk+2, ... ,xn nu se ajunge la solutia rezultat. În caz de neîndeplinire a conditiei φ`(x1, x2, . ,xk), se alege o noua valoare pentru xk Є Sk si se reia verificarea conditiei φ`. Daca multimea de valori xk s-a epuizat, se revine la alegerea altei valori pentru xk-1 s.a.m.d. Aceasta micsorare a lui k da numele metodei, ilustrând faptul ca atunci când nu se poate avansa se urmareste înapoi secventa curenta din solutia posibila. Între conditia interna si cea de continuare exista o strânsa 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 Si si numarul lor de elemente nrsi */
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 Si si numarul lor de elemente nrsi */
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 încât ele sa nu se atace. Se considera ca ele se ataca daca sunt pe aceeasi linie, coloana sau diagonala.
Întrucât pe o linie se gaseste o singura dama, solutia se prezinta sub forma de vector
x =(x1, x2, ... ,xn), unde xi reprezinta coloana pe care se afla dama în 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
Utilizând metoda Greedy sa se rezolve urmatoarele probleme:
Se dau m vectori V1, V2, ... Vm, care contin n1, n2, ... nm elemente, ordonate crescator dupa o cheie. Se interclaseaza vectorii dati, obtinându-se un vector de lungime n1+n2+...+nm elemente, ordonate crescator. Se stie ca interclasarea a doi vectori care contin n1, respectiv n2 elemente necesita un timp proportional cu suma lungimilor lor. Sa se determine ordinea optima în care trebuie efectuata interclasarea tuturor vectorilor dati.
Problema rucsacului. Greutatea maxima care poate fi transportata cu un rucsac este G. Dându-se n materiale, fiecare având greutatea m si costul C pe unitatea de greutate, sa se gaseasca ce cantitate din fiecare material sa fie introdus în rucsac pentru ca sa se obtina câstigul maxim. Se vor deosebi doua cazuri:
a) un material poate fi luat numai în întregime;
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 tpi si un timp de terminare tfi (tpi < tfi). Daca este selectata activitatea i, ea se desfasoara pe durata [tpi, tfi). Spunem ca activitatile i si j sunt compatibile daca duratele lor nu se intersecteaza. Sa se selecteze o multime maximala de activitati mutual compatibile.
Utilizând 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 încât oricare doua noduri adiacente sa fie colorate în 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 în patratul din stânga sus al tablei, sa se
afiseze toate posibilitatile de mutare a calului astfel încât
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 în
pozitii consecutive pe o aceeasi linie sau coloana, celelalte
elemente fiind 0. O persoana se gaseste în 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 întregi. Sa se genereze toate submultimile acestei multimi având proprietatea ca suma elementelor lor este egala cu S.
3.10.Se dau doua multimi de
numere întregi A si B. Sa se genereze toate functiile
.
|
