Algoritmul lui Prim

Algoritmul Prim este un algoritm greedy care calculează un copac minim se întinde într - un grafic conectat ponderate și neorientată. Cu alte cuvinte, acest algoritm găsește un subset de muchii care formează un copac pe setul de vârfuri ale graficului inițial și astfel încât suma greutăților acestor margini este minimă. Dacă graficul nu este conectat, atunci algoritmul determină un copac minim care se întinde pe o componentă conectată a graficului.

Istoric

Algoritmul a fost dezvoltat în 1930 de matematicianul ceh Vojtech Jarnik , apoi redescoperit și republicat de Robert C. Prim și Edsger Dijkstra în 1959. Astfel, este uneori menționată ca DJP algoritm , algoritmul lui Jarník , Prim - Jarník algoritm , sau Prim - Algoritmul Dijkstra .

Principiu

Algoritmul constă în creșterea unui copac dintr-un vârf. Începem cu un subset care conține un singur vârf. La fiecare iterație, acest subset este mărit luând marginea incidentă la acest subset de cost minim. Într-adevăr, dacă luăm o margine ale cărei două capete aparțin deja copacului, adăugarea acestei margini ar crea o a doua cale între cele două vârfuri din arborele în construcție și rezultatul ar conține un ciclu.

Exemplu

În dreapta, oferim un exemplu de execuție a algoritmului lui Prim.

Pseudo cod

Pseudo-codul algoritmului lui Prim este similar cu cel al algoritmului lui Dijkstra și folosește coada de prioritate de tip abstract .

fonction prim(G, s) pour tout sommet t cout[t] := +∞ pred[t] := null cout[s] := 0 F := file de priorité contenant les sommets de G avec cout[.] comme priorité tant que F ≠ vide t := F.defiler pour toute arête t--u avec u appartenant à F si cout[u] >= poids de l'arête entre les sommets t et u pred[u] := t cout[u] := poids de l'arête entre les sommets t et u F.notifierDiminution(u) retourner pred

La început, toate vârfurile sunt în coada de prioritate. Prioritatea este dată de cost [.]. Cu alte cuvinte, vârful cu cea mai mică valoare din cost [.] Array va ieși din coadă mai întâi. Pe rând, vârfurile cozii de prioritate sunt eliminate. Matricea pred [.] Conține predecesorul unui vârf din arborele aflat în construcție. Algoritmul returnează matricea pred care reprezintă arborele întins cu greutate minimă.

Complexitate

Efectuăm de derulare operațiuni și reduce prioritare operațiuni , în cazul în care este numărul de noduri în grafic și este numărul de arce din grafic. Dacă ne uităm la complexitatea acestor două operații cu trei posibilități de cozi prioritare, obținem complexitățile de mai jos: $| V |$ ${\ displaystyle 2 | E |}$ $| V |$ $| E |$

Coadă prioritară	Grafic	Complexitatea timpului
listă sau tabel	matricea de adiacență	${\ displaystyle O (\| V \| ^ {2})}$
heap min binar	listă de adiacență	${\ displaystyle O ((\| V \| + \| E \|) \ log \| V \|) = O (\| E \| \ log \| V \|)}$
Heap Fibonacci	listă de adiacență	${\ displaystyle O (\| E \| + \| V \| \ log \| V \|)}$

Dovada corectării

Fie G un grafic conectat ponderat. Cu fiecare iterație a algoritmului lui Prim, găsim o margine care conectează un vârf dintr-un subgraf la un vârf din afara subgrafului. Deoarece G este conectat, va exista întotdeauna o cale către toate vârfurile. Ieșirea Y a algoritmului lui Prim este un copac , deoarece fiecare vârf (cu excepția primului) este conectat la exact un predecesor.

Fie A i mulțimea primelor i margini adăugate la arborele Y de algoritmul lui Prim și A 0 = {} . Vom arăta că, pentru fiecare dintre A i , există un arbore de acoperire minim de G care conține A i . Apoi , va exista un arbore minim Spanning care conțin Y și , prin urmare , va Y . Pentru a face acest lucru, să presupunem că există un prim set A k astfel încât nici un copac minim să nu conțină A k . Fie e muchia care aparține lui A k dar nu aparține lui A k-1 , fie Y 1 un arbore minim de întindere a graficului G care conține toate muchiile lui A k-1 și fie S setul de vârfuri conectat prin marginile lui A k-1 . Un capăt al muchiei e se află în mulțimea S, iar celălalt nu. Deoarece arborele Y 1 este un arbore de acoperire a graficului G , există o cale în arborele Y 1 care unește cele două capete ale e . Când unul se deplasează de-a lungul traseului, trebuie să îndeplinească o creastă f care se alătură un nod O la un nod care nu este în setul S . Apoi, la iterația în care muchia e a fost adăugată la arborele Y , ar putea fi adăugată și muchia f și ar fi adăugată în loc de e dacă greutatea sa ar fi mai mică decât cea a lui e și, deoarece marginea f nu a fost adăugată, concluzionăm că

${\ displaystyle w (f) \ geq w (e).}$

Fie Y 2 arborele obținut prin îndepărtarea muchiei f și adăugarea marginii e la arborele Y 1 . Este ușor de a arăta că arborele Y 2 este un copac care acoperă și greutatea totală a marginilor sale nu este mai mare decât cea a arborelui Y 1 și Y 2 conține toate marginile A k . Ajungem la o contradicție, pentru că am presupus că există o mulțime A k astfel încât niciun copac întins cu greutate minimă să nu conțină marginile lui A k . Prin urmare, presupunerea făcută este falsă.

Note și referințe

" O jistém Problému minimálním. (Z dopisu panu O. Borůvkovi) ” , pe dml.cz (accesat la 26 decembrie 2015 )
RC Prim , „ Shortest connection networks and some generalizations ”, Bell System Technical Journal , The , vol. 36,1 st noiembrie 1957, p. 1389-1401 ( ISSN 0005-8580 , DOI 10.1002 / j.1538-7305.1957.tb01515.x , citit online , accesat la 26 decembrie 2015 )
Seth Pettie și Vijaya Ramachandran , „ Un algoritm optim minim de copac ”, J. ACM , vol. 49,1 st ianuarie 2002, p. 16–34 ( ISSN 0004-5411 , DOI 10.1145 / 505241.505243 , citit online , accesat la 26 decembrie 2015 )
(în) Robert Sedgewick și Kevin Daniel Wayne , Algoritmi , Upper Saddle River, Addison-Wesley Professional,1 st ianuarie 2011, 955 p. ( ISBN 978-0-321-57351-3 , notificare BnF n o FRBNF44524965 , prezentare online )
(în) Kenneth Rosen , Matematica discretă și aplicațiile sale ediția a VII-a , Știința McGraw-Hill14 iunie 2011( citește online )
D. Cheriton și R. Tarjan , „ Finding Minimum Spanning Trees ”, SIAM Journal on Computing , vol. 5,1 st decembrie 1976, p. 724-742 ( ISSN 0097-5397 , DOI 10.1137 / 0205051 , citit online , accesat la 26 decembrie 2015 )
(en) S. Dasgupta, CH Papadimitriou și UV Vazirani, Algoritmi

Vezi și tu

Bibliografie

J.-F. Hêche, ROSO-EPFL, Curs de cercetare operațională: unele probleme clasice în teoria graficelor
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest și Clifford Stein , Introducere în algoritmică , Dunod ,2002[ detaliul ediției ]

Legături interne