Referat Determinarea Arborelui Partial De Cost Minim
Mai jos puteti citi fragmente din
Referat Determinarea Arborelui Partial De Cost Minim si de asemenea puteti face
Download Referat Determinarea arborelui partial de cost minimCiteste fragmente din Referat Determinarea Arborelui Partial De Cost Minim
Arbori – Notiuni introductive
O categorie importanta de grafuri esteaceea in care muchiile sun niste
legaturi de tip parinte-fiu.Un astfel de graf se va numi ARBORE.
Definitie:
Se numeste arbore un graf conex si fara cicluri.
Un arbore cu n varfuri are n-1 muchii.
Proprietati caracteristice unui arbore:
Exista un nod in care nu intra nici un arc numit radacina arborelui.
Cu exceptia radacinii, fiecare nod are proprietatea ca in el intra un
singur arc.
Acesta leaga nodul respectiv de un alt nod numit numit predecesor sau
parinte.
Dintr-un nod pot iesi unul sau mai multe arce.Fiecare astfel de
arc,leaga nodul
Respectivd de un alt nod numit Succesor sau fiu al nodului.
* Nodurile sunt organizate pe nivele primul nivel fiind ocupat de
nodul radacina.
Nodurile de pe ultim nivel se caracterizeaza prin faptul ca din ele nu
mai iese nici un arc ,si se numesc noduri terminale
sau frunze.
Nodurile pot contine o asa informatie utila ,carte poate fi de orice
tip.
Exemplu:
Nodul 1 este radacina arborelui.
Frunzele arborelui sunt 3,8,9.
Algoritmul Prim (scris în 1957 si implementat în 1961 de catre
Dijkstra) elimina acest neajuns. Se opereaza cu datele din acelasi graf.
Se porneste initial, ca si în algoritmul lui Kruskal cu “nâ€Â
vârfuri izolati (adica de la cele “n†varfuri, dar fara a fi trasat
între aceste vârfuri vre-o muchie), urmând ca pe parcurs aceste
vârfuri sa fie legate între ele de arborele cu lungimea minima.
Fie G=(X,U) un graf neorientat si conex cu n varfuri.
Fiecare muchie se caracterizeaza printr-un numar intreg asociat ,numit
cost.
Graful este definit prin matricea costurilor, care fiind foarte
asemanatoare cu matricea de adiacenta o va inlocui pe aceasta din
urma.Notand matricea costurilor cu A , un element
Pentru acest graf matricea costurilor completa este:
Vom adauga pe rand varfurile grafului la arborele partial.Folosim cei
tre vectori
-vectorul S,numit vector caracteristic.In timpul constructiei arborelui
fiecare element S[i] are valoare 1 daca varful i a fost deja inclus in
arborele partial ,respectiv 0 in caz contrar.Asadar t initial toate
elementele vectorului sunt 0, iar in momentul includerii unui varf I in
arbore facem facem s[i]=1;
-vectorul T numit vectorul parintilor . Pentru fiecare i care se adauga
arborelui ,elementul T[i] va reprezenta varful parinte al lui i in
arbore.
-vectorul C, numit vectorul costurilor.Pentru fiecare varf i elementul
c[i] va avea valoarea costul muchiei care il leaga de parintele sau in
arbore.
Luam in considerare doar michiile care au varf in arborele deja
construit si celalat varf in afara arborelui. Dintre aceste muchii vom
alege una care are costul cel mai mic. “Legam†muchia aleasa in
arbore si actualizam vectorii S,T si C. Daca sunt mai multe astfel de
muchii care au costul minim, putem alege oricare ,de unde rezulta
observatia ca arborele partial de cost minim al unui graf nu este unic.
Pentru graful dat exemplu avem initial in arbore varful de start 1 deci
la primul pas se iau in considerare muchiile care trec prin varful 1.
Pasul 1: initializarea vectorului S[start]=1 start=1;
1 2 3 4 5
1 0 0 0 0
1 2 3 4 5
0 0 0 0 0
1 2 3 4 5
0 0 0 0 0
S= T= C=
Pasul 2: cautarea urmatoarei muchii:
(1,2) cu costul 13
(1,3) cu costul 16
(1,4) cu costul 13
Alegem muchia cu costul minim:muchia (1,2) pe care o legam in arbore.
Actualizam totodata vectorii caracteristici S,T,C.
In arbore a aparut varful 2 fapt pe care-l vom remarca in vectorul
caracteristic S[2]:=1.
Parintele varfului 2 este varful 1 , deci T[2]:=1.
Costul muchiei care leaga varful 2 de parintele sau varful 1 muchia
(1,2) deci C[2]:=13.
1 2 3 4 5
1 1 0 0 0
dfasfgasg
S=
1 2 3 4 5
0 1 0 0 0
T=
1 2 3 4 5
0 13 0 0 0
C=
Pasul 3:
La pasul al trei-lea alegem tot asa o muchie de cost minim cu o
extremitate in arborele deja creat si cealalta extremitate neinclusa
inca in arbore. Acum in arbore avem varfurile 1 si 2 deci vom cauta
printre muchiile care trec prin aceste varfuri ,â€Âvizitind†liniile 1
si 2 ale matricei costurilor. Intra in discutie muchiile (1,3) cu costul
16 , (1,4) cu costul 13,(2,3) cu costul 12, (2,5) cu costul 15.Atentie!
Muchia (1,2)nu o mai luam in considerare deoarece are ambele extremitati
deja in graful creat.Dintre aceste muchii o alegem pe cea cu costul
minim 12 si anume muchia (2,3).O legam in arbore si actualizam din nou
vectorii :S[3]:=1(marcam includerea varfului 3 in
arbore),T[3]:=2(parintele varfului mou inclus 3 este 2.),C[3]:=12
(costul muchiei alese (2,3)este 12).
1 2 3 4 5
1 1 1 0 0
S=
1 2 3 4 5
0 1 2 0 0
T=
1 2 3 4 5
0 13 12 0 0
C=
Analog lapasul urmator cautam printre muchiile grafului care au o
extremitate in multimea {1,2,3} a varfurilor deja incluse si cealalta
extremitate in afara.Acestea sunt (1,4),(2,5),(3,4)si (3,5).Doua dintre
ele si anume (1,4) si (3,5) au costul cel mai mic, 13.Alegem muchia
(1,4) caz in care arborele si vetorii vor arata astfel:
1 2 3 4 5
1 1 1 1 0
S=
1 2 3 4 5
0 1 2 1 0
T=
1 2 3 4 5
0 13 12 13 0
C=
In sfarsit la ultimul pas a mai ramas de adugat in arbore varful 5.In
final vom obtine arborele partial de cost minim si vectorii de mai jos:
1 2 3 4 5
1 1 1 1 1
S=
1 2 3 4 5
0 1 2 1 3
T=
1 2 3 4 5
0 13 12 13 13
C=
In continuare este prezentata procedura de formare a arborelui partial
de cost minim:
Pentru inceput se initializeaza cu 0 vectorii S,T si
C.Intr-un ciclu cu I=1,2,3,..,n atribuim la fiecare pas valoarea 0
elementelor S[i],T[i] si C[i]. Apoi prin S[start]:=1. Elementele
T[start] si C[start] nu se modifica ramanand cu valoarea initiala 0,
deoarece varful de plecare nu are parinte si ca atare nici muchie care
sa-l lege de un astfel de parinte.
In continuare vom aduga pe rand in arborre celelate n-1
varfuri. Pentru aceasta este suficient un singur ciclu for, in care
contorul k=1,2,3,..,n-1 nu are alt rol decat sa numere adugarile.La
fiecare pas adaugam un varf in arbore astfel.
Trebuie sa gasim o muchie de cost minim cu o extremitate in
arborele deja creat si cealalta extremitate in afara arborelui. Fie
aceasta muchie (n1,n2).Pentru a o gasi avem nevoie de o variabila
cost_min in care sa memoram costul minim.Initializam cost_min cu Maxint
si n1,n2 cu –1.
Cautarea muchie se face in matricea costurilor .Parcurgem
toata matricea in 2 cicluri for cu liniile i de la 1 la n si coloanele j
de la 1 la n.La fiecare pas, gasirea unei astfel de muchii ne obliga sa
facem trei testari:
-daca varful i este deja in arbore
(S[i]=1)si j nu este in arbore(S[j]=0)
-daca efectiv exista muchia (i,j)
(a[i,j]<>0).
-daca costul a[i,j] al acestei muchii
este mai mic decat costul minim pe care-l avem
in variabila cost_min.
In cazul in care toate cele trei conditii de mai sus sunt
indeplinte inseamna ca am gasit muchia (i,j) si memoram extremitatile
sale in n1 si n2.Contoarele i,j se modifica.
Urmeaza adaugarea in arborele existent a muchiei (n1,n2) gasite mai
inainte. Cu actualizarea vectorilor:
S[n2] :=1;
T[n2]:=n1
C[n2]:=a[n1,n2].
Matricea de adiancenta in cazul urmator este:
0 13 16 13 0
13 0 12 0 15
16 12 0 17 13
13 0 17 0 0
0 15 13 0 0
program arbore;
uses crt;
type vector=array [1..50]of integer;
var a:array[1..30,1..30]of integer;
n,i,j,k,start,cost_min,n1,n2:integer;
S,T,C:vector; {S=Vectorul caracteristic
T=Vectorul parintilor
C=vectorul costurilor}
f:text; {f=fisierul text din care se citeste matricea de
adiacenta}
procedure citire_matrice;{citeste matricea costurilor}
begin
assign (f, date.txt );
reset(f);
read(f,n);
for i:=1 to n do
for j:=1 to n do
read(f,a[i,j]);
close(f);
end;
procedure afisare_matrice;{adiseaza matricea costurilor}
begin
writeln ( matricea costurilor este: );
for i:=1 to n do
begin
for j:=1 to n do
write (a[i,j]:3);
writeln;
end;
writeln;
end;
procedure formare_arbore;{costruieste arborele partial de cost minim}
begin
for i:=1 to n do {initializeaza cu 0 vectorii S,T,C}
begin
s[i]:=0;
t[i]:=0;
c[i]:=0;
end;
write( dati varful de start: );{citeste varful de start care va fi
radacina arborelui,si il adauga in
arborele initial vid }
readln(start);
writeln;
s[start]:=1;
{intr-un ciclu se aduga pe rand in arbore celelalte n-1 varfuri;
contorul k nu are decat rolul de a numara modificarile facute}
for k:=1 to n-1 do
begin
{caut muchia de cost minim cu o extremitate in arbore si
cealata in afara;in n1 si n2 memorez extremitatile
muchiei}
n1:=-1;
n2:=-1;
cost_min:=maxint;
for i:=1 to n do
for j:=1 to n do
if (s[i]=1)and(s[j]=0)then
if (a[i,j]<>0) then
if a[i,j]
0) then
if a[i,j]0 then
begin
writeln( de la ,t[i], la ,i, de lungime ,c[i], si
cost ,c[i]*k);
cost:=cost+c[i]*k;
end;
writeln ( Costul total al investitiei este: ,cost);
end;
begin
clrscr;
citire;
afisare;
formare;
afis;
readkey;
end.
PAGE
PAGE 1
ì¥Â@
