GRAFURI PONDERATE

GRAFURI PONDERATE

l. Dr. Ing. erban RaduDepartamentul de CalculatoareFacultatea de Automatic i Calculatoare

Introducere

n afar de direcie, muchiile unui graf pot avea o pondere

Dac vrfurile unui graf ponderat reprezint orae, ponderile muchiilor pot reprezenta distanele ntre orae, costurile deplasrii cu avionul sau numrul curselor de autobuze efectuate ntre orae

Definirea structurii de graf ponderat

typedef struct {

int n,

m;

// nr de noduri i nr de arce

int **c;

// matrice de

ponderi (costuri)

} GrafP;

Funcii cu grafuri ponderate//

funcie de

adugare a

arcului

(v,w) la graful ponderat g

void addArc (GrafP

& g, int v,

int w,

int cost) {g.c[v][w]

=

cost;

g.m++;}// funcie care ntoarce costul arcului (v,w)int cost_arc (GrafP

g, int v, int w) {

return g.c[v][w];}

Arborele minim de acoperire al unui graf ponderat

Crearea arborelui minim de acoperire este mai dificil ntr-un graf ponderat, dect ntr-unul neponderat

Cnd se presupune c toate muchiile au lungimi egale, este simplu pentru algoritm s aleag una dintre muchii i s o adauge la arborele de acoperire

Arborele minim de acoperire

Un graf conex are mai muli arbori de acoperire, numrul acestor arbori fiind cu att mai mare cu ct numrul de cicluri din graful iniial este mai mare

Pentru un graf conex cu n

vrfuri, arborii de acoperire au exact n-1

muchii

Pentru un graf dat, trebuie gsit

arborele de acoperire de

cost total minim sau unul

dintre acetia, dac

sunt mai muli


Cnd muchiile au lungimi diferite, trebuie s efectum anumite calcule, nainte de a alege muchia potrivit

Presupunem c dorim s instalm o linie de televiziune prin cablu, care s conecteze ase orae

Cele ase orae vor fi conectate prin cinci legturi


Costurile de conectare difer pentru fiecare pereche de orae, deci trebuie ales traseul care minimizeaz costul global

Presupunem c avem un graf ponderat cu ase vrfuri, reprezentnd oraele:

Ajo,

Bordo, Colina, Danza, Erizo i Flor

Formularea problemei

Fiecare muchie are asociat o pondere, care reprezint costul pentru instalarea unei legturi prin cablu ntre dou orae

Se observ c unele dintre aceste legturi sunt nepractice, din cauza costurilor prea mari

Cum se poate alege un traseu care minimizeaz costul de instalare al reelei de cabluri ?

Soluia problemei

Se obine calculnd un arbore minim de acoperire

Acesta va avea cinci legturi, va conecta toate cele ase orae i va minimiza costul total al instalrii acestor legturi

Observaii

n cazul grafurilor, algoritmii ncep parcurgerea cu un anumit vrf i se deplaseaz din aproape n aproape, examinnd mai nti vrfurile mai apropiate i apoi pe cele mai deprtate de punctul de pornire

Observaii

Presupunem c nu cunoatem de la nceput toate costurile de instalare a cablului ntre oricare dou orae

Culegerea acestor informaii necesit timp i se efectueaz pe parcurs

ncepem din Ajo

Din Ajo, exist dou orae la care putem ajunge direct: Bordo i Danza

Se creeaz o list cu costurile legturilor, introduse n ordinea cresctoare a costului

Ajo-Danza 4

Ajo-Bordo 6

Stabilirea legturii Ajo-Danza

Trebuie mai nti s adugm un vrf la arbore i abia apoi s ncercm s determinm ponderile muchiilor care pleac din acel vrf

Stabilirea legturii Ajo-Bordo

Dup ce se stabilete legtura Ajo-Danza, se inspecteaz toate oraele adiacente

oraului Danza: Bordo, Colina i Erizo

Ajo-Bordo 6

Danza-Bordo 7

Danza-Colina 8

Danza-Erizo 12

Observaii

Legtura Ajo-Danza nu mai apare n list deoarece s-a instalat deja cablul

Rutele pe care s-a instalat deja cablul sunt terse din list

Regul:

alegem ntotdeauna din list muchia cea mai scurt (sau cea mai ieftin)

Observaii

La orice moment din procesul de construcie a reelei de cabluri, exist trei tipuri de orae:

1. Orae care sunt deja n arborele minim de acoperire

2. Orae pentru care se cunoate costul de conectare cu cel puin un ora care se afl deja n arborele minim;

acestea se numesc

orae de frontier

3. Orae despre care nu cunoatem nc nimic

Observaii

Ajo, Danza i Bordo fac parte din prima categorie

Colina i Erizo din a doua categorie

Flor din ultima categorie

Pe msur ce algoritmul avanseaz, oraele din categoria a treia trec n cea de-a doua, iar cele de aici trec n prima

Stabilirea legturii Bordo-Erizo

Lista conine urmtoarele costuri:

Bordo-Erizo 7

Danza-Colina 8

Bordo-Colina 10

Danza-Erizo 12

Observaii

Legtura Danza-Bordo exista n vechea list, dar nu mai exist acum, deoarece nu are sens s lum n considerare legturi ntre orae deja conectate, chiar printr-o rut indirect

Din lista actual, legtura cea mai ieftin este Bordo-Erizo, cu costul 7

Stabilirea legturii Erizo-Colina

Din Erizo, costul este 5 spre Colina i 7 spre Flor

Legtura Danza-Erizo trebuie tears din list, deoarece Erizo este acum un ora

conectat

Coninutul actualizat al listei

Erizo-Colina 5

Erizo-Flor 7

Danza-Colina 8

Bordo-Colina 10

Cea mai ieftin dintre aceste legturi este Erizo-Colina

Legtura Colina-Flor

Dup tergerea oraelor deja conectate, lista conine doar legturile:

Colina-Flor 6

Erizo-Flor 7

Se stabilete ultima legtur, Colina-Flor, cu costul 6

Rutele obinute reprezint cea mai ieftin soluie de conectare a tuturor oraelor

Coada cu prioriti

O list n care putem selecta n mod repetat elementul cu valoarea minim sugereaz utilizarea unei cozi cu prioriti

Paii algoritmului

ncepem cu un vrf, pe care-l introducem n arbore

Repetm urmtorii pai:

1. Determinm toate muchiile, de la cel mai recent vrf ctre alte vrfuri, care nu aparin arborelui; aceste muchii se insereaz n coada cu prioriti

2. Alegem muchia cu ponderea minim, iar aceasta se adaug (mpreun cu vrful de destinaie) la arborele de acoperire

Observaii

Aceti pai se repet, pn cnd toate vrfurile sunt n arbore

n pasul 1, prin cel mai recent

se nelege nodul cel mai recent adugat n arbore

Muchiile necesare sunt gsite n matricea de adiacen

Dup pasul 1, lista va conine toate muchiile cu originea n vrfuri din arbore i destinaia n vrfuri de pe frontier

Observaii

n procesul de meninere a listei de legturi, o problem este de a terge legturile care au destinaia n oraul (vrful) cel mai recent conectat (adugat n arborele de acoperire)

Fr aceast operaie, este posibil s instalm legturi prin cablu care nu mai sunt necesare

Observaii

Trebuie s ne asigurm c n coada cu prioriti nu exist muchii a cror destinaie s fie un nod aflat deja n arbore

Putem parcurge coada, cutnd i eliminnd toate muchiile de acest fel, de fiecare dat cnd adugm un vrf nou n arbore

Observaii

Este mai simplu s memorm n coad, la un moment dat, o singur muchie de la un vrf din arbore ctre fiecare nod de frontier dat

Coada trebuie sa conin o singur muchie ctre fiecare vrf din categoria a doua

Cutarea duplicatelor n coada cu prioriti

De fiecare dat cnd adugm o muchie n coad, ne asigurm c nu mai exist o alt muchie cu aceeai destinaie

Dac mai exist astfel de muchii, o pstrm numai pe cea cu ponderea minim

Aceast operaie necesit cutarea secvenial prin coada cu prioriti

Algoritmul lui Prim

Algoritmul folosete o coad

cu prioriti de arce care leag

vrfuri din

arborele

minim de acoperire

cu alte vrfuri (coada se modific

pe msur

ce algoritmul

evolueaz)

Algoritmul lui Prim

Algoritmul se bazeaz

pe observaia urmtoare: fie S

o submulime a vrfurilor

grafului i R

submulimea de vrfuri care nu sunt n S

Muchia de cost minim care unete vrfurile din S

cu vrfurile din R

face parte

din

arborele minim de acoperire

Algoritmul lui Prim

Se poate folosi noiunea de tietur

n graf: se taie toate arcele care leag

un nod k

de

restul nodurilor din graf i se determin

arcul de cost minim dintre arcele tiate; acest arc va face parte din


i va

uni nodul k

cu


al grafului rmas dup

ndeprtarea nodului k

La fiecare pas se face o nou

tietur

n graful rmas i se determin

un alt arc din arborele

minim de acoperire

Algoritmul lui Prim

Fiecare tietur

n graf mparte mulimea nodurilor din graf n dou

submulimi:

S

(noduri incluse n

arborele minim de acoperire) R

(restul nodurilor)

Iniial,

S

=

{1},

dac

se pornete cu nodul 1, iar n final S va conine toate nodurile din graf

Exemplu

Se consider urmtorul graf neorientat,

cu 6 noduri,

cu

arcele

i costurile asociate:

(1,2)=6; (1,3)=1; (1,4)=5;

(2,3)=5; (2,5)=3;

(3,4)=5; (3,5)=6; (3,6)=4;

(4,6)=2;

(5,6)=6;

S Arce ntre S i R (arce tiate) Minim y

1 (1,2)=6;

(1,3)=1; (1,4)=5; (1,3)=1 3

1,3 (1,2)=6; (1,4)=5; (3,2)=5; (3,4)=5; (3,5)=6; (3,6)=4

(3,6)=4 6

1,3,6 (1,2)=6; (1,4)=5; (3,2)=5; (3,4)=5; (3,5)=6;

(6,4)=2; (6,5)=6

(6,4)=2 4

1,3,6,4 (1,2)=6; (3,2)=5; (3,5)=6; (6,5)=6

(3,2)=5 2

1,3,6,4,2 (2,5)=3; (3,5)=6; (6,5)=6 (2,5)=3 5

Soluia problemei

O mulime de arce, adic

un tablou

de perechi de noduri, sau dou

tablouri de

ntregi X i Y, cu semnificaia c

o pereche x[i]-y[i] reprezint

un arc din

arborele

minim de acoperire

Este posibil i folosirea unui tablou

de

ntregi pentru arborele minim de acoperire

Implementarea algoritmului

Se folosesc dou

tablouri:

p[i]

= numrul nodului din S,

cel mai

apropiat de nodul i din R

c[i]

= costul arcului dintre i i p[i]

La fiecare pas se caut

n tabloul c, pentru a gsi nodul k din R,

cel mai

apropiat de nodul i din S

Implementarea algoritmului

Pentru a nu mai folosi o mulime S, se atribuie lui c[k] o valoare foarte mare,

astfel ca nodul k s

nu mai fie luat n considerare n paii urmtori

Mulimea S este implicit mulimea nodurilor i,

cu c[i] foarte mare

Celelalte noduri formeaz

mulimea R

Implementarea algoritmului# define M 20 // nr maxim de noduri # define M1 10000 // un nr f mare (cost arc absent)# define M2 (M1+1)

// alt nr

f mare (cost arc folosit)

// algoritmul lui

Prim pentru arbore minim de acoperire void prim (GrafP

g, int x[ ], int y[ ]){

int c[M], cmin; int p[M], i,

j,

k;

int n

=

g.n;

// n = nr de vrfurifor(i =

2;

i

Implementarea algoritmuluifor

(i

=

2;

i

Observaii

Sunt

necesare dou

constante mari: M1 arat

c

nu exist

un arc ntre dou

noduri, iar M2

arat

c

acel arc a fost inclus n


i c

va fi ignorat n continuare

Tabloul p

folosit n programul anterior

corespunde reprezentrii unui arbore printr-un singur tablou, de predecesori

Evoluia tablourilor c

i p

pentru exemplul dat este urmtoarea:

c[2] p[2] c[3] p[3] c[4] p[4] c[5] p[5] c[6] p[6] k

6 1 1 1 5 1 M1 1 M1 1 3

5 3 M2 1 5 1 6 3 4 3 6

5 3 M2 1 2 6 6 3 M2 3 4

5 3 M2 1 M2 6 6 3 M2 3 2

M2 3 M2 1 M2 6 3 2 M2 3 5

M2 3 M2 1 M2 6 M2 2 M2 3

Determinarea drumului de lungime minim

O aplicaie frecvent a grafurilor orientate i ponderate este determinarea drumului cel mai scurt dintre dou vrfuri date

Dorim s determinm ruta cea mai ieftin de la un ora

la

un

alt ora

Observaii

Muchiile grafului sunt orientate

Acestea reprezint calea ferat, pe care se circul ntr-un singur sens

Dei n acest caz suntem interesai de minimizarea unui cost, numele algoritmului este problema drumului minim

Observaii

Prin drum minim

nu se nelege neaprat drumul cel mai scurt, din punct de vedere fizic

Poate fi vorba de drumul cel mai ieftin, cel mai rapid sau cel mai bun, dintr-un alt punct de vedere

Costuri minime

ntre oricare dou orae exist mai multe drumuri posibile

Problema drumului minim presupune determinarea, pentru un punct de pornire dat i o destinaie precizat, a traseului cel mai ieftin

Graf orientat i ponderat

Reeaua de cale ferat cuprinde numai linii unidirecionale

Aceast situaie poate fi modelat printr-un graf orientat i ponderat

Algoritmul lui Dijkstra

Soluia la problema drumului minim este numit algoritmul lui Dijkstra, dup numele lui Edsger Dijkstra, care l-a descoperit n 1959

Algoritmul se bazeaz pe reprezentarea grafului cu ajutorul matricei de adiacen

Algoritmul permite determinarea att a drumului minim

dintre un vrf precizat i

altul, ct i a drumurilor minime, de la vrful precizat la toate celelalte vrfuri

Prezentarea algoritmului

Dorim s determinm cel mai ieftin mod de a cltori de la Ajo pn la orice alt ora

Algoritmul trebuie s examineze numai o singur informaie la un moment dat

Regul:

ntotdeauna se merge n oraul pentru care costul total calculat din punctul de pornire (Ajo) este minim

Trei tipuri de orae

1. Orae prin care am trecut deja;

acestea sunt n arbore

2. Orae pentru care tim costurile de cltorie;

acestea sunt pe frontier

3. Orae necunoscute

Observaii

Ajo i Bordo sunt de tipul 1

Oraele de tipul 1 formeaz un arbore, care const din drumurile care ncep cu acelai punct de pornire, fiecare terminndu-se cu un alt vrf, diferit de destinaie

Danza i Colina sunt orae de tipul 2 (de frontier)

Observaii

Oraele se vor deplasa de la tipul 3 (necunoscute), n cel de-al doilea tip (de frontier), iar de aici n arbore, pe msur ce algoritmul avansez

Observaii

Cnd se cunosc costurile cltoriei din Ajo pn n oricare alt ora, algoritmul se termin

Pasul 5 indic rutele cele mai ieftine, din Ajo pn n toate celelalte orae

Ideile algoritmului lui Dijkstra

1. De fiecare dat cnd ne aflm ntr-un ora nou, actualizm lista de costuri

n list reinem numai drumul de cost minim (cunoscut pn n momentul curent) dintre punctul de pornire i un alt ora

precizat

2. Mergem ntotdeauna n oraul care are calea cea mai ieftin fa de punctul de pornire

Detalii de implementare

Se consider

ca nod surs

i nodul 1 i se determin

lungimile drumurilor minime

d[2],

d[3],...,

d[n] pn

la nodurile 2,

3,..., n

Pentru memorarea nodurilor de pe un drum minim se folosete un tablou

P, cu

p[i] =

nodul precedent lui i pe drumul minim de la 1 la i (mulimea drumurilor minime formeaz

un arbore, iar tabloul

P

reprezint

acest arbore de ci n graf)


Se folosete un tablou

D,

unde

d[i] este distana minim

de la 1 la i, dintre drumurile care trec

prin noduri deja selectate

O variabil

S

de tip mulime memoreaz

numerele nodurilor cu distan

minim

fa

de nodul 1, gsite pn

la un moment dat

Iniial,

S={1} i d[i]=cost[1][i], adic

se consider arcul direct de la 1 la i ca drum minim ntre 1 i i

Pe msur

ce algoritmul evolueaz, se actualizeaz

D i S

Pseudocod algoritm Dijkstra

S =

{1}

// S =

mulime noduri pentru

care s-a //determinat distana minim

fa

de nodul 1

repet

ct timp S conine mai puin de n noduri {gsete muchia (x,y) cu x

S i y

S care

minimizeaz

d[x]

+

cost(x,y)adaug

y la S

d[y] = d[x] + cost(x,y)}


La fiecare pas din algoritmul Dijkstra:

1) Se gsete dintre nodurile jS acel nod "jmin" care are distana minim

fa

de nodurile

din S

2) Se adaug

nodul "jmin" la mulimea S

3) Se recalculeaz

distanele de la nodul 1 la nodurile care nu fac parte din S, pentru c

distanele la nodurile din S rmn neschimbate

4) Se reine n p[j] numrul nodului precedent cel mai apropiat de nodul j (de pe drumul minim de la 1 la j)

Exemplu

Se consider

un graf orientat cu urmtoarele costuri de arce:

(1,2)=5; (1,4)=2; (1,5)=6;

(2,3)=3;

(3,2)=4; (3,5)=4;

(4,2)=2; (4,3)=7; (4,5)=3;

(5,3)=3;

Exemplu

Drumurile posibile ntre 1 i 3 i costul lor:

1-2-3 = 8

1-4-3 = 9

1-4-2-3 = 7

1-4-5-3 = 8

1-5-3 = 9

Exemplu

Drumurile minime de la 1 la celelalte noduri din

graf:

1-4-2 cu costul 4

1-4-2-3 cu costul 7

1-4 cu costul 2

1-4-5 cu costul 5

Observaii

ntr-un drum minim,

fiecare drum parial este minim

n drumul 1-4-2-3, drumurile pariale 1-4-2 i 1-4 sunt i ele minime

Evoluia tablourilor

D i S pentru acest graf,

n cazul algoritmului

lui

Dijkstra:

S d[2] d[3] d[4] d[5] Nod

1 5 M 2 6 4

1,4 4 9 2 5 2

1,4,2 4 7 2 5 5

1,4,2,5 4 7 2 5 3

Observaii

Tabloul P va arta astfel:

Funcie Dijkstra

void dijkstra (GrafP

g,int p[]) {int d[M],

s[M];

// s

= noduri pentru

care se tie distana minimint dmin;int jmin,

i,

j;

for (i =

2;

i

Funcie Dijkstra

for (i =

2;

i

Funcie Dijkstra

s[jmin]

=

1;

// adaug

nodul jmin la Sfor (

j

=

2;

j

d[jmin] + cost_arc(g,

jmin,

j) ) {

d[j] =

d[jmin] + cost_arc(g,

jmin,

j);p[j] =

jmin;

// predecesorul lui j pe drumul minim}

}}

Observaii

Valoarea constantei MARE, folosit

pentru a marca n matricea de costuri absena unui arc, nu poate fi mai mare ca jumtate din valoarea maxim

pentru tipul ntreg,

deoarece la nsumarea costurilor a dou drumuri se poate depi cel mai mare

ntreg (se pot folosi pentru costuri i numere reale foarte mari)

GRAFURI PONDERATEIntroducereDefinirea structurii de graf ponderatFuncii cu grafuri ponderateArborele minim de acoperire al unui graf ponderatArborele minim de acoperireArborele minim de acoperireArborele minim de acoperireSlide Number 9Slide Number 10Formularea problemeiSoluia problemeiObservaiiObservaiincepem din AjoStabilirea legturii Ajo-DanzaStabilirea legturii Ajo-BordoObservaiiObservaiiObservaiiSlide Number 21Stabilirea legturii Bordo-ErizoObservaiiStabilirea legturii Erizo-ColinaConinutul actualizat al listeiLegtura Colina-FlorSlide Number 27Coada cu prioritiPaii algoritmuluiObservaiiObservaiiObservaiiObservaiiSlide Number 34Cutarea duplicatelor n coada cu prioritiAlgoritmul lui PrimAlgoritmul lui PrimAlgoritmul lui PrimAlgoritmul lui PrimExempluSlide Number 41Soluia problemeiImplementarea algoritmuluiImplementarea algoritmuluiImplementarea algoritmuluiImplementarea algoritmuluiObservaiiSlide Number 48Determinarea drumului de lungime minimSlide Number 50ObservaiiObservaiiCosturi minimeGraf orientat i ponderatAlgoritmul lui DijkstraPrezentarea algoritmuluiSlide Number 57Slide Number 58Slide Number 59Trei tipuri de oraeObservaiiObservaiiSlide Number 63Slide Number 64Slide Number 65Slide Number 66Slide Number 67ObservaiiIdeile algoritmului lui DijkstraDetalii de implementareDetalii de implementarePseudocod algoritm DijkstraDetalii de implementareExempluExempluExempluObservaiiSlide Number 78ObservaiiFuncie DijkstraFuncie DijkstraFuncie DijkstraObservaii

GRAFURI PONDERATE

Documents

Transcript of GRAFURI PONDERATE