Lab 7

Laborator 7. Metode de elaborare a algoritmilor – plan de desfăşurare a lucrării practice –

1. Scopul lucrării În această lucrare se vor prezenta metoda de elaborare a algoritmilor.

2. Mod de desfăşurare a lucrării practice Se vor prezenta metode diverse de elaborare a algoritmilor. Se va prezenta pe cazul general metodele greedy şi backtracking. Pentru aceste metode lucrarea contine exemplificări. Se vor prezenta generalităţi despre programarea dinamică şi metoda divide-et-impera.

3. Metoda Greedy 3.1. Aspecte teoretice Metoda Greedy se aplică următorului tip de probleme: se dă o mulţime A cu n elemente. Se cere să se găsească o submulţime B a mulţimii A care să indeplinească o anumită condiţie. Metoda Greedy nu determină toate soluţiile posibile şi nu are ca obiect determinarea unei soluţii optime. Prezentăm în cele ce urmează algoritmul general de aplicare a metodei Greedy: Procedure Greedy(A: set, n: integer, B:set, k:integer) Var  i,x:integer v:boolean begin procedure k ← 0;  /* se pleaca de la multimea vida */ for i ← 1 to n loop call alege(A,i,x); /* se alege elementul x dintre  elementele ai, ai+1, …, an, şi se aduce  acest element pe pozitia i */ call posibil(B,x,v); /* se verifica dacă elementul x poate  face parte din solutia B. v ia valoarea  adevarat în cazul afirmativ, altfel ia  valoarea fals. */ if v then agaug(B,x,k); /* se agauda elementul x la solutia  B */ Endloop End

Metoda prezentata în figura 1 poate fi reconsiderată în cazul în care putem determina o modalitate de ordonare prealabilă a elementelor mulţimii A. Astfel, la începutul metodei, se face o re-ordonare a elementelor mulţimii A. În acest caz, alege(A,i,x) înseamnă a considera elementul ai ca şi element ales x.

3.2. Exemplu Se dă o multime de numere pozitive, P şi un număr M. Se cere determinarea unui subset a lui P a cărui sumă a elementelor să fie cel mult M. #include <stdio.h> int main() { int n, p[200], rez[200], k, M, i, j, sum, temp, x; printf("introduceti n: "); scanf("%d", &n); for (i=0; ip[j]) { temp = p[i]; p[i] = p[j]; p[j] = temp; }; k = 0; sum = 0; for (i=0; i
4. Metoda BackTracking 4.1. Aspecte teoretice Metoda backtracking se aplică problemelor în care soluţia se poate prezenta sub forma unui vector x = {x1 , x 2 ,..., x n } ∈ S = S1 xS 2 x...xS n , unde S i sunt mulţimi finite. Cerinţa problemei este, de obicei, găsirea tuturor soluţiilor posibile, care satisfac anumite condiţii specifice problemei. S reprezintă spaţiul tuturor soluţiilor posibile iar condiţiile pe care o soluţie corectă trebuie să le indeplinească vor fi notate cu Φ ( x1 , x2 ,..., xn ) şi reprezintă condiţii interne. Metoda evită generarea tuturor soluţiilor posibile. Se va căuta obţinerea unei soluţii prin alegerea succesivă de elemente din mulţimile S1 , S 2 , …, S n . Astfel, la pasul k, se va alege un element x k ∈ S k . Inainte de a trece la pasul k+1, se verifică dacă sunt satisfăcute condiţiile de continuare, derivate din condiţiile interne Φ . În cazul în care pentru o valoare x k aleasă, condiţiile de continuare nu sunt satisfăcute, se va alege o altă

valoare din mulţimea S k , până cand fie se va găsi o valoare pentru care condiţiile de continuare sunt satisfăcute, fie se epuizează toate elementele mulţimii S k . În cazul în care se găseşte un element x k convenabil, se trece la pasul k+1. Dacă pentru toate elementele mulţimii S k condiţiile interne nu sunt satisfăcute, se va reveni la pasul anterior (k-1), în care se va renunta la valoarea x k −1 aleasă şi se va căuta alegerea unei alte valori. Algoritmul poate fi prezentat în două versiuni: o versiune recursivă şi una nerecursivă. Din considerente de eficienţă a implementării, vom opta pentru prezentarea versiunii nerecursive a algoritmului, studenţii fiind incurajaţi, totuşi, să caute să realizeze şi versiunea recursivă, aceasta din urmă fiind mai convenabilă din punct de vedere a scrierii codului. Procedure Backtracking(n:integer) Var v,k:integer Begin procedure k ← 1; while (k > 0) v ← 0; while (mai exista o valoare t∈Sk netestata and (v==0)) xk ← t; if Φ(x1,x2,…,xk) then v ← 1; endif endwhile if (v==0) then k ← k-1; else if (k==n) then afiseaza(x1,x2,…,xn) else k ← k+1 endif endif endwhile end

Figura 1. Pseudocod pentru varianta nerecursivă de backtracking 4.2. Exemple 4.2.1

Problema damelor de şah

Enunţ: Să se găsească toate soluţiile posibile de aşezare pe tabla de şah de n linii şi n coloane a n dame, astfel încât să nu existe două dame pe aceaşi linie, coloană sau diagonală. Rezolvare: Se ia un vector x = {x1 , x 2 ,..., x n } unde xi reprezintă coloana pe care se va aşeza dama de pe linia i. Conform enunţului, se observă că pe fiecare linie a tablei de şah trebuie să se aşeze o singură damă. Condiţia ca damele să nu se afle pe aceaşi coloană este ca xi ≠ x j pentru i ≠ j . Condiţia ca damele să nu se afle pe aceaşi diagonală este: | k − i |≠| x k − xi | pentru i = 1,2,..., k − 1 . Program C: #include <stdio.h> #include <math.h>

int main() { int n,i,k,v; int x[20]; /* x[i] va reprezenta coloana pe care se afla dama de pe linia i */ printf("Introduceti n:"); scanf("%d",&n); k = 1; x[1] = 0; while (k > 0) { v=0; while ((x[k] <= n-1) && (v==0)) { x[k]++; for (v=1,i=1; (i<=k-1) && (v==1);i++) if ((x[k]==x[i])||(k-i == abs(x[k]-x[i]))) v=0; } if (v==0) k--; else if (k==n) { for (i=1;i<=n;i++) printf("%d ",x[i]); printf("\n"); } else { k++; x[k] = 0; } } }

4.2.2

Problema calului

Enunţ: Să se determine toate modalităţile în care un cal poate parcurge în întregime o tablă de şah, de dimensiuni nxn, astfel încât să treacă prin fiecare câmp o singură dată. Rezolvare: Se va considera aşezarea calului pe tablă, la pasul k în poziţia (i,j). Din această poziţie, mutările posibile sunt în următoarele poziţii: (i-1, j-2), (i-2, j-1), (i-2, j+1), (i-1, j+2), (i+1, j+2) (i+2, j+1), (i+2, j-1), (i+1, j-2). Pentru fiecare din aceste posibile mutări, se va verifica dacă există posibilităţi de continuare, în caz contrar, revenindu-se la alegerea unei alte mutări. Această problemă exemplifică varianta recursivă de backtracking, care facilitează o scriere rapidă a codului. Program C: #include <stdio.h> int a[] = {-1, -2, -2, -1, 1, 2, 2, 1}; int b[] = {-2, -1, 1, 2, 2, 1, -1, -2}; int x[30][30], n; void aseaza(int k, int i, int j) { int t,r,p ; x[i][j] = k; if (k==n*n) { printf("\n"); for (t=0;t=0) && (r
(p>=0) && (p
5. Alte metode de rezolvare a problemelor 5.1. Metoda “branch and bound” Este o metodă înrudită cu backtracking însă apar diferenţe în ceea ce priveşte ordinea de parcurgere a spaţiului stărilor şi privitor la modul de eliminare a ramurilor ce nu pot conduce la rezultat. Astfel, metoda presupune folosirea unei liste în care sunt memorate vârfurile arborelui spaţiului soluţiilor care trebuie parcurs. Iniţial lista vârfurilor active este vida, iar căutarea porneşte de la un vârf oarecare. La un moment dat, printr-o anume metoda se considera un vârf activ, dintre cele memorate din lista. Pentru acest vârf, sunt generaţi descendenţii şi se memorează aceşti descendenţi în lista vârfurilor active ale arborelui. Căutarea se opreşte la găsirea unei soluţii, şi anume în momentul când se ajunge la o frunză a arborelui spaţiului soluţiilor. 5.2. Metoda programării dinamice Se aplică problemelor de optim în care soluţia poate fi privită ca şi rezultatul unui şir de decizii secvenţiale dependente de cele luate anterior, fiecare decizie respectând principiul optimalităţii. Astfel, dacă d1, d2, … dn este un sir de decizii optime care transformă starea s0 în starea finală sn trecând prin stările intermediare s1, s2, …, sn-1, atunci pentru orice i = 1,…,n-1, rezultă că d1, d2, …, di este un şir de decizii optime pentru perechea de stări (s0,şi) şi di+1,…,dn este un sir de decizii optime pentru perechea de stări (şi, sn). Exemplu: determinarea drumurilor cele mai scurte într-un graf. Fie un graf orientat cu n vârfuri, reprezentat prin matricea de adiacentă. Astfel, în matricea de adiacentă elementul de pe poziţia (i,j) indică lungimea drumului direct de la nodul i la nodul j. Dacă în graf nu există arc de la i la j atunci elementul (i, j) este nul. Se cere să se determine lungimea drumului minim de la i la j. Soluţie. Presupunem că drumul minim de la i la j trece prin nodul k. atunci, conform principiului optimalităţii, drumurile de la i la k şi de la k la j sunt minime. Iniţial, matricea C conţine lungimile drumurilor directe de la un element i la un nod j. Vom construi matricea A (nxn) care va conţine în final toate drumurile minime între 2 noduri i

şi j. Iniţial, A(i,j) = C(i,j). pentru fiecare k, k=1,n, se verifică dacă A(i,j) > A(i,k) + A(k,j), pentru orice i şi j. În caz afirmativ, se inlocuieste valoarea lui A(i,j) cu valoarea A(i,k) + A(k,j). În final, vom avea în matricea A lungimea drumurilor minime. 5.3. Metoda divide-et-impera Metoda constă în împărţirea repetată a unei probleme în două sau mai multe subprobleme de acelaşi tip, soluţia problemei iniţiale obţinându-se prin combinarea soluţiilor subproblemelor. Exemplu: căutare binară: Se dă un şir ordonat A, cu n elemente, şi o valoare x. să se determine dacă valoarea x se află între elementele şirului A. Problema se rezolvă în felul următor. Se identifică elementul de la mijlocul şirului A. Dacă x este mai mic decât acest element, atunci căutarea continuă în subsirul din stânga elementului median, în caz contrar, căutarea continuă în subşirul din dreapta. Exemplu: Sortarea prin partiţionare (quicksort)

6. Probleme propuse spre rezolvare: 1. Colorarea grafurilor. Se dă un graf neorientat, şi un număr de m culori. Să se determine toate modalităţile de colorări posibile ale grafului, astfel încât oricare două vârfuri adiacente să fie colorate diferit. 2. Se dă o tablă de şah de 8x8 şi 5 dame. Să se determine toate posibilităţile de a aşeza damele astfel încât orice câmp al tablei să fie controlat de cel puţin o damă. 3. Se da un graf conex în care fiecărui arc i se asociază un cost pozitiv. Să se determine toate ciclurile hamiltoniene care pleacă dintr-un vârf dat al grafului. Un ciclu este hamiltonian dacă trece exact o singură data prin fiecare vârf al grafului.