Date post: | 04-Nov-2015 |
Category: |
Documents |
Upload: | lavinia-constanda |
View: | 16 times |
Download: | 2 times |
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