Algoritmul Kruskal - construirea scheletului optim

La începutul secolului al XIX-lea, geometrul de la Berlin, Jacob Steiner, a stabilit sarcina de a conecta cele trei sate astfel încât lungimea lor să fie cea mai scurtă. Ulterior, el a generalizat această problemă: este necesar să se găsească un punct pe plan astfel încât distanța de la ea la n alte puncte să fie cea mai mică. În secolul XX, au continuat lucrările pe această temă. Sa decis să luăm mai multe puncte și să le conectăm astfel încât distanța dintre ele să fie cea mai scurtă. Acesta este un caz special al problemei studiate.

Algoritmi greoi

Algoritmul lui Kruskal se referă la algoritmi "lacomi" (se mai numesc și algoritmi de gradient). Esența celor - cea mai mare victorie la fiecare pas. Nu întotdeauna algoritmii "lacomi" dau cea mai bună soluție pentru sarcină. Există o teorie care arată că atunci când se aplică unor probleme specifice, acestea oferă soluția optimă. Aceasta este teoria matroidelor. Algoritmul Kruskal se referă la astfel de probleme.

Găsirea scheletului cu greutatea minimă

Algoritmul considerat construiește scheletul optim al graficului. Problema despre aceasta 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. Este necesar să găsiți scheletul cu cea mai mică greutate.

descriere

Algoritmul Kruskal funcționează astfel. Mai întâi, toate margini ale graficului original sunt aranjate în ordinea greutăților în creștere. Inițial, cadrul nu conține margini, ci include toate vârfurile graficului. După următoarea etapă a algoritmului, se adaugă o muchie la partea deja construită a cadrului, care este o pădure care se întinde. Nu este ales arbitrar. Toate margini ale graficului care nu aparțin scheletului pot fi denumite roșu și verde. Vârfurile fiecărei nervuri roșii se află într-o componentă a legăturii pădurii care se construiește, iar vârfurile verde sunt în diferite componente. Prin urmare, dacă adăugați o margine roșie acolo, apare un ciclu, iar dacă cel verde - în pasul forestier rezultat, componenta de conectivitate va fi mai mică cu una. Astfel, nu se poate adăuga margini roșii la construcția rezultată, dar orice margine verde poate fi adăugată pentru a obține pădurea. Și se adaugă o coaste verde cu o greutate minimă. Ca rezultat, se obține scheletul cu cea mai mică greutate.

punerea în aplicare

Semnăm pădurea curentă F. Se împarte setul de vârfuri ale graficului în domenii conexe (formele lor de uniune F și nu se intersectează în perechi). Marginile roșii au ambele vârfuri într-o parte. Partea (x) este o funcție care returnează numele părții la care aparține x pentru fiecare vârf x. Unite (x, y) este o procedură care construiește o nouă partiție care constă în unirea părților x și y și toate celelalte părți. Fie n numărul de margini al graficului. Toate aceste concepte sunt incluse în algoritmul Kruskal. Implementare:

1. Aranjați toate margini ale graficului de la prima la cea de-a cincea greutate ascendentă. (ai, bi sunt vârfurile marginii cu indexul i).

2. pentru i = 1 până la n.

3. x: = Partea (ai).

4. y: = Partea (bi).

5. Dacă x nu este egal cu y, atunci Unite (x, y), include marginea cu numărul i în F.

corectitudine

Fie T scheletul grafului original construit folosind algoritmul Kruskal și S este scheletul său arbitrar. Este necesar să se demonstreze că w (T) nu depășește 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).

De asemenea, corectitudinea algoritmului Kruskal rezultă din teorema lui Rado-Edmonds despre matroizi.

Exemple de aplicare a algoritmului Kruskal

Dan grafic cu noduri, b, c, d, e și coaste (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). Greutățile marginilor 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 aceasta, scheletul optim al graficului original constă. Acesta este modul în care funcționează algoritmul Crascal în acest caz. Un exemplu arată acest lucru.

Figura prezintă un grafic compus din două componente de conectivitate. Linile îndrăznețe arată marginile cadrului optim (verde), construite folosind algoritmul Kruskal.

Figura superioară prezintă graficul original, iar pe cel inferior - scheletul greutății minime, construit pentru el cu ajutorul algoritmului considerat.

Secvența marginilor adăugate: (1,6) - (0,3), (2,6) sau (2,6), (0,3) - nu contează (3,4) - (0,1) (1.6) sau (1.6), (0.1) este de asemenea indiferent (5.6).

Algoritmul lui Kruskal găsește o aplicație practică, de exemplu, pentru a optimiza tampoanele de comunicare, drumurile din cartierele noi în localitățile fiecărei țări, dar și în alte cazuri.