PowerPoint Presentation

Metode de rezolvare a problemelor cutare n spaiul soluiilorGreedyBacktracking????

Spaiul soluiilorGreedy metoda optimului localMetod rapid, de complexitate redus, pentru obinerea unei soluii acceptabile (nu neaprat cea mai bun)La fiecare pas se alege cea mai bun cale n contextul local, ignornd contextul generalUneori soluia poate fi cea mai puin dezirabil

Este folosit atunci cnd gsirea celei mai bune soluii este prea costisitoare

Greedy metoda optimului local

Greedy metoda optimului local

Greedy metoda optimului local

Greedy metoda optimului local

Cum se alege un element candidat?Cum se verific acceptabilitatea elementului candidat?Variant: prelucrare iniial a mulimii A (sortare)Greedy metoda optimului local

Exemple de probleme rezolvate prin algoritmi de tip Greedy:Determinarea arborelui parial de cost minim (soluia este ntotdeauna optim)Algoritmul lui Kruskal, algoritmul lui PrimProblema rucsaculuintreagcontinuInterclasarea optim a n vectoriSuma maxim dintr-o mulime de numerePlata unei sume (cu bancnot unitate)Problema pazniculuiDeterminarea unui produs de transpoziiiAlgoritmul DijkstraEnunuri complete n manualProblema rucsacului (continu)

// I: capacitate totala (q), nr. obiecte (n), capacitate ocupata (c),// [ cistig (v) ]// E: solutia xvoid Rucsac_c(float q, int n, float* c, float* x){ float qr; int i,j;

qr=q; for(i=0; i0; i++) if(qr>=c[i]) { x[i]=1; qr-=c[i]; //qr-=c[i]*x[i] } else { x[i]=qr/c[i]; qr=0; //qr-=c[i]*x[i] for(j=i+1;j