Metode de elaborare a algoritmilor
- plan de desfasurare a lucrarii practice -
În aceasta lucrare se vor prezenta metoda de elaborare a algoritmilor.
Se vor prezenta metode diverse de elaborare a algoritmilor. Se va prezenta pe cazul general metodele greedy si backtracking. Pentru aceste metode lucrarea contine exemplificari. Se vor prezenta generalitati despre programarea dinamica si metoda divide-et-impera.
Metoda Greedy se aplica urmatorului tip de probleme: se da o multime A cu n elemente. Se cere sa se gaseasca o submultime B a multimii A care sa indeplineasca o anumita conditie. Metoda Greedy nu determina toate solutiile posibile si nu are ca obiect determinarea unei solutii optime.
Prezentam în cele ce urmeaza algoritmul general de aplicare a metodei Greedy:
|
Procedure Greedy(A: se 353d39d t, n: integer, B:set, k:integer) Var i,x:integer v:boolean begin procedure k /* 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, si se aduce acest element pe pozitia i */ call posibil(B,x,v); /* se verifica daca 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 reconsiderata în cazul în care putem determina o modalitate de ordonare prealabila a elementelor multimii A. Astfel, la începutul metodei, se face o re-ordonare a elementelor multimii A. În acest caz, alege(A,i,x) înseamna a considera elementul ai ca si element ales x.
Se da o multime de numere pozitive, P si un numar M. Se cere determinarea unui subset a lui P a carui suma a elementelor sa fie cel mult M.
|
#include <stdio.h> int main() printf("Introduceti suma: "); scanf("%d", &M); /* incepem abordarea greedy a problemei */ /* ordonam crescator multimea de numere p */ for (i=0; i<n-1; i++) for (j=i+1; j<n; j++) if (p[i]>p[j]) ; k = 0; sum = 0; for (i=0; i<n; i++) else break; printf("submultimea rezultat: "); for (i=0; i<k; i++) printf(" %d", rez[i]); printf("\n"); |
Metoda backtracking
se aplica problemelor în care solutia se poate prezenta sub forma
unui vector 
, unde 
sunt multimi
finite. Cerinta problemei este, de obicei, gasirea tuturor solutiilor
posibile, care satisfac anumite conditii specifice problemei. S
reprezinta spatiul tuturor solutiilor posibile iar
conditiile pe care o solutie corecta trebuie sa le
indeplineasca vor fi notate cu 
si
reprezinta conditii interne.
Metoda evita generarea tuturor
solutiilor posibile. Se va cauta obtinerea unei solutii
prin alegerea succesiva de elemente din multimile 
, 
, ., 
. Astfel, la pasul k, se va alege un element 
. Inainte de a trece
la pasul k+1, se verifica daca sunt satisfacute conditiile
de continuare, derivate din conditiile interne 
. În cazul în care pentru o valoare 
aleasa, conditiile
de continuare nu sunt satisfacute, se va alege o alta valoare din
multimea 
, pâna cand fie se va gasi o valoare pentru care
conditiile de continuare sunt satisfacute, fie se epuizeaza
toate elementele multimii . În cazul în care se gaseste un element convenabil, se trece
la pasul k+1. Daca pentru toate elementele multimii conditiile
interne nu sunt satisfacute, se va reveni la pasul anterior (k-1), în care
se va renunta la valoarea 
aleasa si se
va cauta alegerea unei alte valori.
Algoritmul poate fi prezentat în doua versiuni: o versiune recursiva si una nerecursiva. Din considerente de eficienta a implementarii, vom opta pentru prezentarea versiunii nerecursive a algoritmului, studentii fiind incurajati, totusi, sa caute sa realizeze si versiunea recursiva, aceasta din urma fiind mai convenabila din punct de vedere a scrierii codului.
Procedure Backtracking(n:integer)
Var v,k:integer
Begin procedure
k
while (k > 0)
v
while (mai exista o valoare t Sk netestata and (v==0))
xk t;
if F(x1,x2,.,xk) then v
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 nerecursiva de backtracking
Enunt: Sa se gaseasca toate solutiile posibile de asezare pe tabla de sah de n linii si n coloane a n dame, astfel încât sa nu existe doua dame pe aceasi linie, coloana sau diagonala.
Rezolvare: Se ia un vector 
unde 
reprezinta
coloana pe care se va aseza dama de pe linia i. Conform enuntului, se
observa ca pe fiecare linie a tablei de sah trebuie sa se
aseze o singura dama. Conditia ca damele sa nu se afle
pe aceasi coloana este ca 
pentru 
. Conditia ca damele sa nu se afle pe aceasi
diagonala este: 
pentru 
.
Program C:
#include <stdio.h>
#include <math.h>
int main()
if (v==0) k--;
else if (k==n) else
Enunt: Sa se determine toate modalitatile în care un cal poate parcurge în întregime o tabla de sah, de dimensiuni nxn, astfel încât sa treaca prin fiecare câmp o singura data.
Rezolvare: Se va considera asezarea calului pe tabla, la pasul k în pozitia (i,j). Din aceasta pozitie, mutarile posibile sunt în urmatoarele pozitii: (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 mutari, se va verifica daca exista posibilitati de continuare, în caz contrar, revenindu-se la alegerea unei alte mutari. Aceasta problema exemplifica varianta recursiva de backtracking, care faciliteaza o scriere rapida a codului.
Program C:
#include <stdio.h>
int a[] = ;
int b[] = ;
int x[30][30], n;
void aseaza(int k, int i, int j)
} else
for (t=0;t<8;t++)
x[i][j] = 0; /* reface pozitia alterata */
int main()
Este o metoda înrudita cu backtracking însa apar diferente în ceea ce priveste ordinea de parcurgere a spatiului starilor si 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 spatiului solutiilor care trebuie parcurs. Initial lista vârfurilor active este vida, iar cautarea porneste 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 generati descendentii si se memoreaza acesti descendenti în lista vârfurilor active ale arborelui. Cautarea se opreste la gasirea unei solutii, si anume în momentul când se ajunge la o frunza a arborelui spatiului solutiilor.
Se aplica problemelor de optim în care solutia poate fi privita ca si rezultatul unui sir de decizii secventiale dependente de cele luate anterior, fiecare decizie respectând principiul optimalitatii. Astfel, daca d1, d2, . dn este un sir de decizii optime care transforma starea s0 în starea finala sn trecând prin starile intermediare s1, s2, ., sn-1, atunci pentru orice i = 1,.,n-1, rezulta ca d1, d2, ., di este un sir de decizii optime pentru perechea de stari (s0,si) si di+1,.,dn este un sir de decizii optime pentru perechea de stari (si, sn).
Exemplu: determinarea drumurilor cele mai scurte într-un graf. Fie un graf orientat cu n vârfuri, reprezentat prin matricea de adiacenta. Astfel, în matricea de adiacenta elementul de pe pozitia (i,j) indica lungimea drumului direct de la nodul i la nodul j. Daca în graf nu exista arc de la i la j atunci elementul (i, j) este nul. Se cere sa se determine lungimea drumului minim de la i la j.
Solutie. Presupunem ca drumul minim de la i la j trece prin nodul k. atunci, conform principiului optimalitatii, drumurile de la i la k si de la k la j sunt minime. Initial, matricea C contine lungimile drumurilor directe de la un element i la un nod j. Vom construi matricea A (nxn) care va contine în final toate drumurile minime între 2 noduri i si j. Initial, A(i,j) = C(i,j). pentru fiecare k, k=1,n, se verifica daca A(i,j) > A(i,k) + A(k,j), pentru orice i si 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.
Metoda consta în împartirea repetata a unei probleme în doua sau mai multe subprobleme de acelasi tip, solutia problemei initiale obtinându-se prin combinarea solutiilor subproblemelor.
Exemplu: cautare binara: Se da un sir ordonat A, cu n elemente, si o valoare x. sa se determine daca valoarea x se afla între elementele sirului A. Problema se rezolva în felul urmator. Se identifica elementul de la mijlocul sirului A. Daca x este mai mic decât acest element, atunci cautarea continua în subsirul din stânga elementului median, în caz contrar, cautarea continua în subsirul din dreapta.
Exemplu: Sortarea prin partitionare (quicksort)
1. Colorarea grafurilor. Se da un graf neorientat, si un numar de m culori. Sa se determine toate modalitatile de colorari posibile ale grafului, astfel încât oricare doua vârfuri adiacente sa fie colorate diferit.
2. Se da o tabla de sah de 8x8 si 5 dame. Sa se determine toate posibilitatile de a aseza damele astfel încât orice câmp al tablei sa fie controlat de cel putin o dama.
3. Se da un graf conex în care fiecarui arc i se asociaza un cost pozitiv. Sa se determine toate ciclurile hamiltoniene care pleaca dintr-un vârf dat al grafului. Un ciclu este hamiltonian daca trece exact o singura data prin fiecare vârf al grafului.
|
