Metoda Greedy

Trimis la data: 2010-12-09 Materia: Electronica Nivel: Facultate Pagini: 7 Nota: / 10 Downloads: 0
Autor: Elisa Floresci Dimensiune: 24kb Voturi: Tipul fisierelor: doc Acorda si tu o nota acestui seminar: 1 2 3 4 5 6 7 8 9 10
vezi mai multe detalii vezi mai putine detalii
Raporteaza o eroare
Dintre solutii aleg una care optimizeaza o functie p:P(A)R data.
Metoda urmareste evitarea parcurgerii tuturor submultimilor (ceea ce ar necesita un timp de calcul exponential), mergandu-se "direct" spre solutia optima. Nu este insa garantata obtinerea unei solutii optime; de aceea aplicarea metodei Greedy trebuie insotita neaparat de o Distingem doua variante generale de aplicare a metodei Greedy:
Referate similare: Nu exista seminarii similare

Fie G=(V,M) un graf neorientat cu muchiile etichetate cu costuri strict pozitive. Se cere determinarea unui graf partial de cost minim. Ca exemplificare, sa consideram n orase initial nelegate intre ele. Pentru fiecare doua orase se cunoaste costul conectarii lor directe (consideram acest cost egal cu + daca nu este posibila conectarea lor). Constructorul trebuie sa conecteze orasele astfel incat din oricare oras sa se poata ajunge in oricare altul. Ce legaturi directe trebuie sa aleaga constructorul astfel incat costul total al lucrarii sa fie minim?

Este evident ca graful partial cautat este un arbore (daca ar exista un ciclu, am putea indeparta orice muchie din el, cu pastrarea conexitatii si micsorarea costului total).Vom aplica metoda Greedy: adaug mereu o muchie de cost minim dintre cele nealese si care nu formeaza un ciclu cu precedentele muchii alese. Acest algoritm poarta numele de algoritmul lui Kruskal. Ca de obicei, fie |V|=n, |M|=m. Vor fi alese deci n-1 muchii. Construim o matrice mat cu m linii si n coloane. Pe fiecare linie apar extremitatile i si j ale unei muchii, precum si costul acestei muchii.

Incepem prin a ordona liniile matricii crescator dupa ultima coloana (a costurilor muchiilor).Conform algoritmului lui Kruskal, vor fi alese in ordine muchiile:(1,2), (1,4), (4,5), (3,4) cu costul total egal cu 10. Muchia (1,5) nu a fost aleasa deoarece formeaza cu precedentele un ciclu.Dificultatea principala consta in verificarea faptului ca o muchie formeaza sau nu cu precedentele un ciclu. Plecand de la observatia ca orice solutie partiala este o padure, vom asocia fiecarui varf i un reprezentant ri care identifica componenta conexa (arborele) din care face parte varful in solutia partiala. Atunci:

o muchie (i,j) va forma un ciclu cu precedentele ri=rj;la alegerea (adaugarea) unei muchii (i,j) vom pune rkrj pentru orice varf k cu rk=ri (unim doi arbori, deci varfurile noului arbore trebuie sa aiba acelasi reprezentant). In algoritmul care urmeaza metoda descrisa, l este numarul liniei curente din matricea mat, nm este numarul de muchii alese, iar cost este costul muchiilor alese.

  • pag. 1
  • pag. 2
  • pag. 3
  • pag. 4
  • pag. 5
  • pag. 6
  • pag. 7

Nota explicativa
Referatele si lucrarile oferite de Referate.ro au scop educativ si orientativ pentru cercetare academica.

Iti recomandam ca referatele pe care le downloadezi de pe site sa le utilizezi doar ca sursa de inspiratie sau ca resurse educationale pentru conceperea unui referat nou, propriu si original.

Referat.ro te invata cum sa faci o lucrare de nota 10!
Linkuri utile
Programeaza-te online la salonul favorit Descarca gratuit aplicatiile pentru iOS si Android Filmulete haioase Filme, poante si cele mai tari faze Jocuri Cele mai tari jocuri de pe net Referate scoala Resurse, lucrari, referate materiale pentru lucrari de nota 10
Toate imaginile, textele sau alte materiale prezentate pe site sunt proprietatea referat.ro fiind interzisa reproducerea integrala sau partiala a continutului acestui site pe alte siteuri sau in orice alta forma fara acordul scris al referat.ro. Va rugam sa consultati Termenii si conditiile de utilizare a site-ului. Informati-va despre Politica de confidentialitate. Daca aveti intrebari sau sugestii care pot ajuta la dezvoltarea site-ului va rugam sa ne scrieti la adresa webmaster@referat.ro.
Confidentialitatea ta este importanta pentru noi

Referat.ro utilizeaza fisiere de tip cookie pentru a personaliza si imbunatati experienta ta pe Website-ul nostru. Te informam ca ne-am actualizat politica de confidentialitate pentru a integra cele mai recente modificari privind protectia persoanelor fizice in ceea ce priveste prelucrarea datelor cu caracter personal. Inainte de a continua navigarea pe Website-ul nostru te rugam sa aloci timpul necesar pentru a citi si intelege continutul Politicii de Cookie. Prin continuarea navigarii pe Website-ul nostru confirmi acceptarea utilizarii fisierelor de tip cookie conform Politicii de Cookie. Nu uita totusi ca poti modifica in orice moment setarile acestor fisiere cookie urmarind instructiunile din Politica de Cookie.


Politica de Cookie
Am inteles