Arborii Partiali de Cost Minim

Referat
8/10 (2 voturi)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 15 în total
Cuvinte : 3693
Mărime: 10.41KB (arhivat)
Cost: 4 puncte

Extras din document

Arbori partiali de cost minim

Fie G = <X, V> un graf neorientat conex, unde X este multimea varfurilor si U este multimea muchiilor.Un arbore este un asemenea graf ce nu are cicluri. Fiecare muchie are un cost pozitiv (sau o lungime pozitiva). Pentru a gasi un arbore se pune problema sa gasim o submultime A inclusa in U, astfel incat toate varfurile din X sa ramina conectate atunci cand sunt folosite doar muchii din A.Numim arbore partial de cost minim acel arbore ce are multimea varfurilor X si a muchiilor A iar suma lungimilor muchiilor din A este minima.Cautam deci o submultime A de cost total minim care sa lege printr-un drum oricare doua noduri din X. Aceasta problema se mai numeste si problema conectarii oraselor cu cost minim, avand numeroase aplicatii.

Problema conectarii oraselor de cost minim:Se dau n orase precum si costul conectarii anumitor perechi de orase.Se cere sa se eleaga acele muchii care asigura existenta unui drum intre oricare doua orase astfel incat costul total sa fie minim.

Graful partial <X, A> este un arbore si este numit arborele partial de cost minim al grafului G (minimal spanning tree). Un graf poate avea mai multi arbori partiali de cost minim si acest lucru se poate verifica pe un exemplu.Vom prezenta doi algoritmi greedy care determina arborele partial de cost minim al unui graf. In terminologia metodei greedy, vom spune ca o multime de muchii este o solutie, daca constituie un arbore partial al grafului G, si este fezabila, daca nu contine cicluri. O multime fezabila de muchii este promitatoare, daca poate fi completata pentru a forma solutia optima. O muchie atinge o multime data de varfuri, daca exact un capat al muchiei este in multime. Urmatoarea proprietate va fi folosita pentru a demonstra corectitudinea celor doi algoritmi.

Multimea initiala a candidatilor este V. Cei doi algoritmi greedy aleg muchiile una cate una intr-o anumita ordine, aceasta ordine fiind specifica fiecarui algoritm.

1 Algoritmul lui Kruskal

Arborele partial de cost minim poate fi construit muchie cu muchie, dupa urmatoarea metoda a lui Kruskal (1956): se alege intai muchia de cost minim, iar apoi se adauga repetat muchia de cost minim nealeasa anterior si care nu formeaza cu precedentele un ciclu. Alegem astfel X–1 muchii. Este usor de dedus ca obtinem in final un arbore. Este insa acesta chiar arborele partial de cost minim cautat?

Inainte de a raspunde la intrebare, sa consideram, de exemplu, graful din Figura 6.1.a. Ordonam crescator (in functie de cost) muchiile grafului: {1, 2}, {2, 3}, {4, 5}, {6, 7}, {1, 4}, {2, 5}, {4, 7}, {3, 5}, {2, 4}, {3, 6}, {5, 7}, {5, 6} si apoi aplicam algoritmul. Structura componentelor conexe este ilustrata, pentru fiecare pas, in Tabelul 1.

Figura 1 Un graf si arborele sau partial de cost minim.

Pasul.

Muchia considerata.

Componentele conexe ale

subgrafului <X, A>

Initializare. —. {1}, {2}, {3}, {4}, {5}, {6}, {7}

1. {1, 2}. {1, 2}, {3}, {4}, {5}, {6}, {7}

2. {2, 3}. {1, 2, 3}, {4}, {5}, {6}, {7}

3. {4, 5}. {1, 2, 3}, {4, 5}, {6}, {7}

4. {6, 7}. {1, 2, 3}, {4, 5}, {6, 7}

5. {1, 4}. {1, 2, 3, 4, 5}, {6, 7}

6. {2, 5}. respinsa (formeaza ciclu)

7. {4, 7}. {1, 2, 3, 4, 5, 6, 7}

Tabelul 1 Algoritmul lui Kruskal aplicat grafului din Figura1a.

Multimea A este initial vida si se completeaza pe parcurs cu muchii acceptate (care nu formeaza un ciclu cu muchiile deja existente in A). In final, multimea A va contine muchiile {1, 2}, {2, 3}, {4, 5}, {6, 7}, {1, 4}, {4, 7}. La fiecare pas, graful partial <X, A> formeaza o padure de componente conexe, obtinuta din padurea precedenta unind doua componente. Fiecare componenta conexa este la randul ei un arbore partial de cost minim pentru varfurile pe care le conecteaza. Initial, fiecare varf formeaza o componenta conexa. La sfarsit, vom avea o singura componenta conexa, care este arborele partial de cost minim cautat (Figura 1b).Ceea ce am observat in acest caz particular este valabil si pentru cazul general.

In vectorul V vom sorta in ordine crescatoare numarul muchiilor in ordine crescatoare in functie de costul fiecareia.In vectorul X vom retine pentru fiecare nod numarul componenetei din care face parte acesta si care se schimba o data ce adaugam o noua muchie.Modificarea acestuia se face in functie de apartenenta uneia dintre extremitati la un arbore cu mai mult de un nod.In multimea B se retin numerele de ordine ale muchiilor ce apartin arborelui de cost minim.

procedure sortare; {se face sortarea intr-un vector v a muchiilor in ordine

var i,k,min:integer; crescatoare a costurilor muchiilor}

c:vector;

begin

c:=a;k:=0;

repeat

min:=maxint;

for i:=1 to m do

if (c[i].cost<min) and (c[i].cost<>0) then

begin

min:=c[i].cost;

j:=i;

end;

inc(k);

v[k]:=j;

c[j].cost:=0;

until k=m;

end;

procedure kruskal;

Preview document

Arborii Partiali de Cost Minim - Pagina 1
Arborii Partiali de Cost Minim - Pagina 2
Arborii Partiali de Cost Minim - Pagina 3
Arborii Partiali de Cost Minim - Pagina 4
Arborii Partiali de Cost Minim - Pagina 5
Arborii Partiali de Cost Minim - Pagina 6
Arborii Partiali de Cost Minim - Pagina 7
Arborii Partiali de Cost Minim - Pagina 8
Arborii Partiali de Cost Minim - Pagina 9
Arborii Partiali de Cost Minim - Pagina 10
Arborii Partiali de Cost Minim - Pagina 11
Arborii Partiali de Cost Minim - Pagina 12
Arborii Partiali de Cost Minim - Pagina 13
Arborii Partiali de Cost Minim - Pagina 14
Arborii Partiali de Cost Minim - Pagina 15

Conținut arhivă zip

  • Arborii Partiali de Cost Minim.doc

Alții au mai descărcat și

Arbori

1.1.ASPECTE GENERALE LEGATE DE TEMA LUCRARII . DOMENIUL (N CARE SE (NCADREAZA LUCRAREA (n momentul de fata prelucrarea informatiilor de orice...

Algoritmi GREEDY

Pusi in fata unei probleme pentru care trebuie sa elaboram un algoritm, de multe ori "nu stim cum sa incepem". Ca si in orice alta activitate,...

Arhitectura Calculatoarelor - Intel vs AMD

Rezultatele din testul 3DS Max 7 SPECapc Test Testul alaturat consta in crearea modelelor 3D, modificarea si randarea scripturilor. Conform...

Aplicatii cu Arbori Binari - Evaluarea Arborilor Asociati Expresiilor

Obiective In urma parcurgerii acestui laborator, studentul va fi capabil: - sa inteleaga notiunea de arbore si structura unui arbore binar; - sa...

Elemente de Teoria Grafurilor

ELEMENTE DE TEORIA GRAFURILOR SI ANALIZA DRUMULUI CRITIC •Concepte fundamentale.Modelarea prin grafuri a proceselor economice. •Drumuri de...

Structuri de Date și Algoritmi

Curs 1 Structuri de date Structurile de date erau definite în limbajul C drept organizarea datelor primare. În limbajul C++, acestea reprezinta o...

Structuri de Date

Structuri (continuare).Lucrul cu fisiere. Declaratia de tip Ne amintim declaratia de structura : Struct NumeStructura { <instructiuni de...

Structuri de Date - Liste

3. Structuri elementare de date Inainte de a elabora un algoritm, trebuie sa ne gandim la modul in care reprezentam datele. In acest capitol vom...

Ai nevoie de altceva?