Algoritmul lui Kruskal - construirea unui cadru optim

La începutul secolului al 19-lea geometru Jakob Steiner din Berlin, a stabilit sarcina de modul de conectare trei sate, astfel încât lungimea lor a fost cel mai scurt. Mai târziu, el a rezumat problema: este necesar pentru a găsi un punct într-un plan, distanța de la ea la n alte puncte au fost cele mai mici. În secolul 20, ea continuă să lucreze pe acest subiect. Sa decis să ia câteva puncte și de a le conecta astfel încât distanța dintre ele a fost cel mai scurt. Acest toate este un caz special al problemei studiate.

Algoritmul „Greedy“

Algoritmul lui Kruskal se referă la algoritmul „greedy“ (de asemenea, numit gradient). Esența celor - cel mai mare câștig de pe fiecare pas. Nu întotdeauna, „lacomi“ algoritmi de a oferi cea mai bună soluție la această problemă. Există o teorie, care arată că, în aplicarea lor la sarcini specifice care le dau soluția optimă. Aceasta este teoria matroids. Algoritmul lui Kruskal se referă la astfel de probleme.

Găsirea o greutate minimă a carcasei

Algoritmul Privite construiește un număr optim cadru. Problema este după cum urmează. Dan neorientat grafic, fără margini paralele și bucle, iar setul de muchii este dată funcția w greutate, care atribuie numărul la fiecare margine e - rib greutate - w (e). Greutatea fiecărui subset din multitudinea de nervuri este egală cu suma ponderilor muchiilor sale. Necesar pentru a găsi scheletul o greutate mică.

descriere

Algoritmul lui Kruskal funcționează. În primul rând, toate muchiile graficului inițial sunt aranjate în ordinea greutăților ascendentă. Inițial, rama nu conține nervuri, ci include toate nodurile. După următoarea etapă a algoritmului părții deja construite din carcasă, care este o pădure se întinde, se adaugă o margine. Nu este ales în mod arbitrar. Toate marginile graficului, nu aparțin cadrului, poate fi numit roșu și verde. Partea superioară a fiecărei margini roșii sunt în aceeași componentă sub conectivității forestiere de construcție, iar vârfurile verzi - diferite. Prin urmare, dacă adăugați la marginea roșie, există un ciclu, iar în cazul în care verde - primit după această etapă componentele lemnoase conectate va fi mai mică decât unu. Astfel, construcția rezultată nu poate adăuga nici o margine rosie, dar orice margine verde pot fi adăugate pentru a obține pădure. Și adaugă o margine verde, cu greutate minimă. Rezultatul este un cadru de greutate minimă.

punerea în aplicare

Notăm pădurea curentă F. împarte setul de noduri în domeniul conectivității (formele lor de sindicat F, și ei sunt disjuncte). La ambele margini ale vârfurilor roșii acestea se află într-o singură bucată. Partea (x) - funcția pe care, pentru fiecare nod x returnează o parte a numelui, aparține de x. Unite (x, y) - o procedură care construiește o nouă partiție, care constă din combinarea părți x și y și toate celelalte părți. Fie n - numărul de muchii. Toate aceste concepte sunt incluse în algoritmul lui Kruskal. Implementare:

1. Aranja toate marginile graficului de la 1 la greutăți ascendente n-lea. (Ai, bi - i cu numărul de margine apex).

2. pentru i = 1 la n do.

3. x: = Partea (ai).

4. y: = partea (bi).

5. Dacă x nu y egal apoi Unite (x, y), pentru a include cu numărul marginii F i.

corectitudine

Fie T - cadru a graficului original, construit folosind algoritmul Kruskal și S - cadrul său arbitrar. Trebuie să dovedească faptul că w (T) nu este mai mare decât W (S).

Fie M - pluralitate de aripioare S, P - o multitudine de aripioare T. Dacă S nu este egal cu T, atunci există un et cadru coaste T, care nu aparțin S. S. și învecina ciclului, este numit C. C scoate din orice es margine, aparținând S. Obținem un cadru nou, deoarece marginile și nodurile este aceeași. Greutatea sa nu este mai mare decât w (S), deoarece w (et) nu mai w (es) într-o putere Kruskal algoritm. Această operațiune (substitut coaste T S de pe coaste) va fi repetată atâta timp cât primesc T. Greutatea fiecărui cadru primit ulterior nu este mai mare decât greutatea anterioară, ceea ce implică faptul că w (T) nu este mai mare decât w (S).

Robustețea algoritmului lui Kruskal rezultă din teorema lui Rado-Edmonds pe matroids.

Exemple de aplicații Kruskal algoritm

Dan grafic cu noduri, b, c, d, e și coaste (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). Ponderile marginile sunt prezentate în tabel și în figură. Inițial, pădure de construcții F conține toate nodurile graficului și nu conține coaste. Algoritmul Kruskal adaugă mai întâi nervură (a, e), deoarece greutatea a avut cea mai mică, iar nodurile unei și e sunt în diferite componente de conectivitate lemn F (nervură (a, e) este verde), atunci nervura (c, d), deoarece că cel puțin această greutate margine muchiilor grafuri, care nu aparțin F, și este verde, atunci pentru aceleași motive acumulați muchie (a, b). Dar muchia (b, e) este trecut, chiar dacă el și greutatea minimă a marginilor rămase, deoarece este de culoare roșie: vârfuri b și e aparțin aceleiași componente de conectivitate de pădure F, adică, dacă vom adăuga la F marginea (b, e), este format ciclu. Apoi se adaugă margine verde (b, c) margine roșie, este trecut (c, e), și apoi d, e. Astfel, se adaugă secvențial margini (a, e), (c, d), (a, b), (b, c). Din nihera cadru optim și este format din graficul original. Deci, în acest caz, funcționează un algoritm Kruskal. Un exemplu este prezentat.

Figura prezintă un grafic, care este format din două componente conectate. Liniile îngroșate indică nervurile optimale cadru (verde) construite folosind algoritmul Kruskal.

Imaginea de sus arată graficul inițial, iar în partea de jos - un schelet de greutate minimă, construit pentru el, prin utilizarea algoritmului.

Secvența nervurilor adăugate (1,6); (0,3), (2,6) sau (2,6), (0,3) - nu este important; (3,4); (0,1), (1,6) sau (1,6), (0,1), de asemenea, de îngrijire (5,6).

Algoritmul lui Kruskal găsește aplicarea în practică, de exemplu, pentru a optimiza comunicațiile garniturii, iar drumurile din localități noi locuințe din fiecare țară, precum și în alte cazuri.