Articolul tratează problema construirii unui arbore minim se întinde (problema minimă deschizătoare-tree). La începutul acestui articol, vom da o descriere generală a problemei și istoria abordărilor la soluționarea ei. Următoarele descrie algoritmul de bază și unele informații teoretice despre arborele minim se întinde. La sfârșitul articolului prezintă algoritmul de bază (Kruskal, Prim, Borůvka).
Declarația problemei
În cazul general, problema poate fi formulată după cum urmează. Să presupunem că avem un grafic conectat, neorientat cu greutăți pe marginile G (V. E), unde V - un set de noduri (contact) și E - setul de conexiuni posibile (muchii) perechi. Să presupunem că fiecare nervură este unic număr real determinată w (U v.) (U v.) - greutatea (lungimea sau costul compusului). w () se numește funcția de ponderare. Sarcina este de a găsi o astfel de subgraf conectat aciclic T ⊂ G. care conține toate nodurile care greutatea totală a marginilor sale vor fi minime.
Deoarece T este conectat și nu conține cicluri, este numit un arbore de acoperire, sau (arbore de acoperire) se întinde copac. Un arbore de acoperire T. a cărui combinată greutatea marginilor sale w (T) = Σ (u. V) ∈ T w (u. V) este minimă se numește arborele minim se întinde sau acoperirea minimă (arbore minim se întinde).
Fig. 1. copac minim Spanning. greutate Rezumat lemn este 37. Acest minim arbore de acoperire nu este unic: margini îndepărtarea (c, d) și adăugarea de margine (a, b) obținerea unui nou arbore minim se întinde.
Din moment ce noi considerăm doar copaci, putem presupune toate marginile pozitive (pentru a adăuga greutate suficient pentru toate marginile unor constante relativ mari pozitive). În caz contrar, în cazul în care valoarea unei conexiuni între două noduri este egal cu un număr negativ, le puteți conecta în mod repetat, în paralel, pentru a reduce subgraful totală se întinde în greutate.
Figura 2-a. arbore de acoperire minimă.
Greutatea totală este egală cu 3.
Figura 2-B. subgrafic minimă de acoperire.
Greutatea totală este egală cu 0.
De asemenea, noi credem că caracteristicile lor de greutate vor fi diferite pentru fiecare pereche de nervuri. Acest lucru asigură unicitatea de a construi un arbore de acoperire minim. De exemplu, dacă toate marginile au greutatea unitară, orice arbore de acoperire va fi minimă (cu o greutate totală de v-1 unde v -. Numărul de noduri din grafic).
Figura 3. Toate posibil arbore de acoperire minim pentru un grafic.
În acest caz, oricare dintre algoritm pentru a construi copaci minime care acoperă. O modalitate de realizare a rezoluției ambiguitate este de a modifica algoritmul muchiilor comparație în greutate, de exemplu:
Shorter-EDGE (i, j, k, l)
1: dacă w (i j.)
3: if min (i j.)
5: dacă max (i j.)
aplicații
informații istorice
În sarcina de a construi un copac minim se întinde este istorie lungă și bogată. Graham și Iad, în articolul său „Istoria problema construirii unui copac minim se întinde“ [2] începe să numere istoria problemelor cu munca Chekanovskii (Czekanowski) 1909. Primul și probabil cel mai simplu algoritm merge înapoi la Borůvka (Boruvka), care în 1926, cu mult înainte de apariția primelor calculatoare, și chiar mai devreme decât a fost creat teoria grafurilor structurale, a prezentat soluția la această problemă. Puțin mai târziu, în 1938, Choquet (Choquet), și apoi Florek (Florek), Lukasiewicz (Lukaziewicz), percale (Perkal), Steinhaus (Stienhaus) și Zubzhitsky (Zubrzycki) în 1951 și Sollin (Sollin) la începutul anilor șaizeci din nou redescoperi algoritm.
Un alt algoritm cunoscut de a construi un arbore minim se întinde înapoi la Adalbert Jarnik (Vojtech Jarnik) [1930]. El este mai bine cunoscut sub numele de algoritmul lui Prim (Robert Prim). R.Prim indiferent de Jarnik sa inventat în 1956 și a prezentat mai detaliat și descrierea detaliată decât descoperitorului. Încă o dată, acest algoritm a deschis Edsger Dijkstra (Edsger Wybe Dijkstra) în 1958, dar numele a blocat pentru a accepta, deoarece la Dijkstra algoritm a fost deja la numele său (căutarea celor mai scurte trasee într-un grafic direcționat). Acest algoritm poate fi atribuit grupului de algoritmi construite pe construirea arborelui: există doar o componentă de bază non-triviale (altele sunt un singur nod) și este incrementat treptat, prin adăugarea de margini „sigure“. Timpul Algoritmul Dzharnika Prima poate ajunge la O (E + V log V) folosind un grămezile Fibonacci.
În ultimii ani (din 1980), a fost întrebat o mulțime de abordări diferite pentru a optimiza și de a îmbunătăți viteza algoritmilor cunoscute. În cazul în care numărul de muchii din grafic este suficient de mare, punerea în aplicare algoritmul Prim folosind un grămezi Fibonacci dă O estimare temporară (E). Pentru grafice rare (grafice sparser) Fredman și Tarjan (Fredman, Tarjan, 1987) a propus un algoritm care funcționează cu o eficiență de O (ElogV), care combină ideile algoritmilor și Prima Borůvka folosind structuri de date suplimentare. Ceva mai târziu Gabov, Galil, Spencer și Tarjan acest algoritm îmbunătățit, realizând evaluarea timpului O (E loglog V) (HN Gabow, Z. Galil, T. Spencer și RE Tarjan. 1986. algoritmi eficienți pentru a găsi copaci minime se întind în neorientat și grafice direcționate. Combinatorica 6, 109 -122).
O abordare interesantă pentru a reduce timpul de funcționare de a construi un copac minim se întinde oferit San Chung și A. Condon într-un articol cu privire la punerea în aplicare în paralel a algoritmului Borůvka pe mai multe procesoare de mare viteză. [3] Ei au arătat că, prin schimbul de subactivități pentru mai multe centre de date și optimizarea mecanismului de sincronizare, puteți obține o ușoară creștere a performanței în comparație cu versiunea de bază a algoritmului.
Un mod fundamental diferit de rulează algoritmul din timp O (E # 945; „(E. V), în care # 945; „- inversul funcției Ackermann, a sugerat Chazel [4]. deoarece # 945; „crește foarte încet, în timp ce lucrarea este aproape de linia. Spre deosebire de toate cele anterioare, acest algoritm nu ar trebui să fie strategia greedy, cu toate acestea, folosind Borůvka algoritm pentru grafic preprocesare.
Mulți algoritmi dedicate problemei legate de verificare se întinde de copac (care acoperă problema de verificare copac). putem formula problema după cum urmează. Să presupunem că avem un grafic G și arborele său se întinde. Acesta trebuie să verifice dacă este sau nu copacul este minim.
Construcția arborele de acoperire minim
Luați în considerare schema generală de algoritmi pentru construirea unui arbore minim se întinde folosind strategia greedy. Deci, să presupunem că se dă un graf conectat neorientat G (V; E) c n noduri și w funcție de greutate. E → R.
Căutând schelet este construit treptat. Algoritmul foloseste unele subgrafic este graf aciclic G. O sursă intermediară numită o pădure se întinde. Inițial G este format din n noduri componente care nu sunt conectate între ele (n arbori de la un nod). La fiecare pas, se adaugă o nouă muchie la A. Un grafic este întotdeauna un subgraf al unui copac minim se întinde. O alta a adăugat o muchie e = (U v.) Este selectat astfel încât să nu deranjeze această proprietate: A ∪
Aici este un algoritm general pentru construirea unui arbore minim se întinde:
MST-GENERIC (G, w)
1: A ← 0
2: în timp ce (până) A nu este coloana vertebrală
3: găsesc o margine în condiții de siguranță (U v.) ∈ E la A
4: A ← A ∪
5: întoarcere A
A. Prin definiție, ar trebui să fie un subgraf al unui copac minim se întinde după orice număr de iterații. Desigur, întrebarea principală este cum să găsească o margine în condiții de siguranță la pasul 3. Este clar că o astfel de margine este întotdeauna acolo, dacă A nu este încă un arbore minim se întinde (orice margine a miezului, nu sunt incluse în A). Rețineți că, deoarece A nu poate conține cicluri, apoi conectați diferitele conexiuni componente pe fiecare pas de margine (inițial toate nodurile din componentele individuale, după A - un component). Astfel, bucla este executata (n-1) ori.
Ceea ce urmează este regula generală de a găsi un margini în condiții de siguranță. Pentru a face acest lucru, vom dovedi o teorema care ajută la găsirea margini sigure. În primul rând vom dovedi a fi o mică Lema:
Lema. lasa T - arbore minim se întinde. Apoi, orice margine e de T - în condiții de siguranță.
Dovada. în T - (n-1) de margine. La fiecare pas al Generic-MST am adăugat o margine de siguranță. Total efectuate (n-1) trepte, astfel, toate marginile din T - în condiții de siguranță prin definiție.
Teorema. Fie G (V; E) - conectat graf neorientat și un set E funcție de greutate definită w. Fie A - unele subgraf al lui G, care este în același timp un subgraf al unui spanning T. minim copac Să considerăm o K componentă conectată de A. Să considerăm setul E (K) de marginile G, doar un capăt care se află în K. Apoi marginea minimă de greutate în E (K) va fi în siguranță.
Dovada. Să e = (u v.) - muchia greutate minimă în E (K). Lăsați arborele minim se întinde T nu conține e (altfel afirmația este evident din lema de mai sus). pentru că T este conectat, există unele (doar) un aciclic drum p de la u la v. e și se închide într-o buclă. Ca unul dintre capete e constă în K. și altul în V \ K. călătoresc p există cel puțin o margine e „= (x. Y), care are aceeași proprietate. Această margine nu este ca A. în A nu are margini între K și V \ K. Eliminăm din T coaste e „și adăugați e. Deoarece w (e ') w (e), obținem un arbore de acoperire T'. greutatea totală este mai mică decât greutatea totală a T. Astfel, T nu este un copac minim se întinde. Contradicția. De aceea, T cuprinde e.
În legătură cu această teoremă introducem următoarele
Definiția. Safe margine e cu privire la o componentă conectată de A K se numește margine cu greutate minima, exact un capăt care se află în K.
Borůvka algoritm
Deci, presupunem că avem un graf neorientat conectat G (V, E) și este dat o funcție de greutate. Să presupunem că A - o pădure care acoperă intermediar pentru grafic V. Primul pas A este compus din toate vârfurile vidă G și coaste. La începutul următoarei faze a algoritmului Borůvka, pentru fiecare intermediar pădurea care acoperă componenta conectată este selectat lider ( «conducător» nod, Erickson [7]) sau rădăcină - vertex, atribuind fiecărei componente. Acest lucru se poate face în cel mai simplu caz printr-un by-pass O adâncime: nod, care începe următoarele componente de by-pass și va fi liderul acesteia. Algoritmul este responsabil pentru această procedură ALEGE-LIDERI. Liderul pentru vârful este stocat în variabila lider v (v).
Odată ce liderii selectate, pentru fiecare componentă conectată este muchie sigură substanțial de forță brută. Acesta este un loc de muncă procedură FIND-SAFE_EDGES. margine sigură pentru un lider v „este stocat într-un seif variabilă (v“). Odată ce toate aceste margini selectate, ele sunt adăugate A. Acest proces continuă atâta timp cât A este prezentă în mai mult de o componentă conectată.
MST-BORUVKA (G. w)
1: A ← (V, 0)
2: componente în timp ce (încă) în mai multe A conectat
3: do ALEGE-LEADERS (A)
4: FIND-SAFE-MARGINI (G)
5: foreach (pentru fiecare), un lider v '
6: adăugați în condiții de siguranță (v „) în A
7: O întoarcere
Aici este o formă posibilă simplă a procedurilor de cautare sigure Coaste:
FIND-SAFE-MARGINI (G)
1: foreach (pentru fiecare), un lider v '
2: în condiții de siguranță (v „) ← ∞
3: foreach (pentru fiecare) a nervurii (u v.) ∈ E
4: u „← lider (u)
5: v „← conducător (v)
6: dacă u '≠ v' atunci
7: dacă w (u v.) W (în condiții de siguranță (u „)), atunci
8: (. U v) în condiții de siguranță (u „) ←
9: dacă w (u v.) W (în condiții de siguranță (v „)), atunci
10: în condiții de siguranță (v „) ← (u v.)
Schema algoritmului prezentat în figurile B1-B5.
Fig. B1. Faza inițială. cherestea minimă de acoperire cuprinde toate vârfurile și marginile setului gol.
Fig. B2. Pentru fiecare componentă conectată (pentru fiecare nod) găsi margini sigure. Acestea sunt marcate prin săgeți pe componentele de-a lungul marginilor în siguranță.
Fig. B3. Adăugați coaste pentru a fixa pădurea minimă se întinde.
Fig. K8. Coaste cu o greutate de 17, 19 și 25 - nu sunt sigure. Capetele lor sunt în aceeași componentă conectată. O margine cu o greutate de 21 - în condiții de siguranță, așa că am adăuga. copac minimă se întinde este construit.
Calculăm timpul algoritmului. Presupunem că metoda este utilizată pentru a clasifica combinarea și comprimarea căi ([1]. 21.3) pentru stocarea seturi disjuncte, ca Este cel mai rapid mod cunoscut până în prezent. Inițializarea ia timp O (V), ordonarea muchiilor în linia 4 - O (E log E). Următoarea este O (E) operații, ia în mod colectiv timp O (E # 945; „(E. V)), în care # 945; „- funcție inversă a funcției Ackermann (a se vedea [1], 21.4.). ca # 945; „(E. V) = o (log E), timpul total algoritmul Kruskal este O (E log E) (timpul necesar pentru sortare).
Algoritmul lui Prim
Deoarece algoritmul lui Kruskal, algoritmul lui Prim urmează schema generală a algoritmului pentru construirea unui arbore minim se întinde: la fiecare pas, vom adăuga la coloana vertebrală fiind construit margine în condiții de siguranță. Algoritmul lui Prim se referă la gruparea construi algoritmul minim se întinde arbore: la fiecare pas, nu există mai mult de un non-triviale (nu constă dintr-un singur nod) componente conectate, și fiecare nervură se adaugă la acesta cel greutate, conectarea cu alte componente ale nodurilor nodurilor. Prin teorema unei margini este sigur.
Atunci când punerea în aplicare trebuie să fie în măsură, la fiecare pas pentru a selecta rapid o margine în condiții de siguranță. Este convenabil de a utiliza coada de prioritate (heap). Algoritmul are ca date de intrare un grafic G și R rădăcină - sus, care va fi majorat arborele minim se întinde. G. Toate partea de sus nu este chiar ajuns la copac, stocate într-o coadă cu prioritate # 937;. Prioritate vârf v valoarea cheii determinată [v]. este egală cu greutatea minimă a marginilor care unesc vârfurile v arborelui minim Spanning. Câmpul p [v] pentru nodurile punctelor de copac la mamă, iar nodurile punctelor de coadă la un nod de arbore, în care muchia de ghidare cu cheia de greutate [v] (una dintre aceste margini, dacă există mai multe).
Apoi, algoritmul Prima este după cum urmează:
MST-PRIM (G. w. R)
1: # 937; ← V [G]
2: foreach (pentru fiecare) vertex u ∈ # 937;
3: a face tasta [u] ← ∞
4: tasta [r] ← 0
5: p [r] = NIL
6: în timp ce (încă) # 937; ≠ 0
7: do u ← EXTRACT-MIN (# 937;)
8: foreach (pentru fiecare) din vertex v ∈ Adj (u)
9: în cazul în care v ∈ do # 937; și w (u. v) v] atunci
10: p [v] ← u
11: Tasta [v] ← w (u v.)
La desene P1-P8 Diagrama Prim algoritm funcționează cu rădăcină r.
Fig. P1. Faza inițială. cherestea minimă de acoperire constă dintr-o rădăcină și marginile setului gol.
Fig. P2. Edge cu greutatea de 6 este marginea minimă care unește rădăcină cu celelalte vârfuri. Adăugați-l la copacul minim Spanning.
Fig. P8. Coaste cu o greutate de 17, 19 și 25 - nu sunt sigure. Capetele lor sunt în aceeași componentă conectată. O margine cu o greutate de 21 - în condiții de siguranță, așa că am adăuga. copac minimă se întinde este construit.
Programul de lucru Algoritmul Prim depinde de modul în care coada de prioritate pusă în aplicare # 937;. Dacă utilizarea binar movilă de inițializare în liniile 1-4 se poate face în timpul O (V). Apoi se efectuează ciclul | V | ori, și fiecare operațiune EXTRACT-MIN ia timp O (V log V). pentru ciclul se realizează în rândurile 8-11, un total de O (E), din moment ce suma gradelor de noduri este egal cu 2 | E |. Testele de membru în linia 9 poate fi realizată în O (1) în cazul în care starea de magazin, de asemenea, coada ca un vector de biți de mărime | V |. Atribuirea la linia 11 presupune cheie de reducere a funcționării (SCĂDEREA-KEY), pentru care un heap binar poate fi realizată într-un timp O (log V). Astfel numai obținem O (V log V + E log V) = O (E log V).
O estimare mai bună poate fi obținută prin utilizarea heap Fibonacci. Folosirea grămezile Fibonacci poate efectua operație EXTRACT-MIN pentru timpul de înregistrare O (log V) și operarea DECREASE-KEY - o contabilitate pentru timp O (1). În acest caz, timpul total al algoritmului Prim va fi O (E + V log V).
Lista literaturii second-hand
visualizers
Multumesc pentru articol. Dar, chiar mai mult decât desenele! O astfel de teorie etanșă la aer, fără tragere aproape nu sunt percepute de mine (