Kruskalov algoritam - izgradnja optimalnog kostura

Početkom 19. stoljeća, geometri iz Berlina, Jacob Steiner, postavili su zadatak kako povezati tri sela tako da njihova dužina bude najkraća. Nakon toga, generalizirao je ovaj problem: potrebno je pronaći točku na ravnini tako da je udaljenost od nje do n drugih točaka bila najmanja. U 20. stoljeću nastavlja se rad na ovoj temi. Odlučeno je uzeti nekoliko točaka i povezati ih na takav način da je udaljenost između njih bila najkraća. Ovo je poseban slučaj problema koji se istražuje.

Pohlepni algoritmi

Algoritam Kruskal odnosi se na "pohlepni" algoritmi (oni su također nazvani gradijentni algoritmi). Bit onih - najveća pobjeda na svakom koraku. Ne uvijek "pohlepni" algoritmi daju najbolje rješenje zadatku. Postoji teorija koja pokazuje, kada se primjenjuju na specifične probleme, oni pružaju optimalno rješenje. Ovo je teorija matroida. Kruskalov algoritam se odnosi na takve probleme.

Pronalaženje kostura minimalne težine

Algoritam koji se razmatra konstruira optimalni kostur grafikona. Problem je u tome što slijedi. Prikazan je neizravni grafikon bez višestrukih rubova i petlji, a na njemu se nalazi rubna funkcija w koja svakom rubu dodjeljuje broj - težinu ruba - w (e). Težina svakog podskupa skupova rubova određuje se zbrojem težina njegovih rubova. Potrebno je pronaći kostur od najmanje težine.

opis

Kruskalov algoritam ovako funkcionira. Prvo, svi rubovi izvornog grafikona su poredani po porastu težine. U početku, okvir ne sadrži rubove, ali uključuje sve vrhove grafikona. Nakon sljedećeg koraka algoritma, jedan rub se dodaje već izgrađenom dijelu okvira, koji je šumska širina. Nije odabrano samovoljno. Svi rubovi grafikona koji ne pripadaju kosturu mogu se nazvati crveno i zeleno. Vrhovi svake crvene rebra nalaze se u jednoj komponenti povezanosti šume koja se konstruira, a vrhovi zelenog su u različitim komponentama. Stoga, ako dodate crvenu rubu, pojavit će se ciklus i ako se zeleni pojavi u rezultatu šumskog koraka, povezana komponenta će biti manja za jedan. Dakle, ne može se dodati crveni rub u dobivenu konstrukciju, ali se može dodati bilo koji zeleni rub kako bi se dobila šuma. I dodaje se zeleni rebro s minimalnom težinom. Rezultat je okvir najmanja težina.

izvršenje

Označavamo trenutnu šumu F. Podjeljuje skup vertica grafikona u povezane domene (njihovi sindikalni oblici F, a ne presijecaju se u parovima). Crveni rubovi imaju oba vrha u jednom dijelu. Dio (x) je funkcija koja vraća naziv dijela kojem x pripada za svaki vrh x. Unite (x, y) je postupak koji gradi novu particiju koja se sastoji od sjedinjenja dijelova x i y i svih ostalih dijelova. Neka n bude broj rubova grafikona. Svi ti pojmovi su uključeni u algoritam Kruskal. provedba:

1. Rasporedi sve rubove grafikona od prvog do nultih uzlaznih utega. (Ai, bi su vrhovi ruba s indeksom i).

2. Za i = 1 do n učiniti.

3. X: = Dio (ai).

4. Y: = Dio (bi).

5. Ako x nije jednak y, zatim Unite (x, y), uključite rub s brojem i u F.

ispravnost

Neka T bude kostur izvornog grafikona konstruiranog korištenjem algoritma Kruskal, i neka S bude njegov proizvoljni kostur. Potrebno je dokazati da w (T) ne prelazi w (S).

Neka M bude skup rubova S i P skup bridova T. Ako S nije jednak T, onda postoji rub et T-a koji ne pripada S. Mi pridružujemo et do S. Izrađujemo ciklus, mi ga nazivamo C. Uklanjamo iz C bilo kojeg ruba koji pripadaju S. Dobit će novi okvir jer su oba ruba i vrhovi istih. Njegova težina ne prelazi w (S), budući da w (et) nije veći od w (s) po Kruskalovom algoritmu. Ova operacija (zamjena rubova S prema rubovima T) će se ponoviti sve dok ne dobijemo T. Težina svakog sukcesivnog kostura nije veća od težine prethodne, od koje slijedi da w (T) iznosi najviše w (S).

Također, ispravnost Kruskalovog algoritma slijedi iz Rado-Edmondsovog teorema na matroidima.

Primjeri primjene algoritma Kruskal

Grafikon s vrhovima a, b, c, d, e i rubovima (a, b), (a, e), (b, c), (b, e), (c, d), , (D, e). Težine rubova prikazane su u tablici i na slici. U početku, izgrađena šuma F sadrži sve vrhove grafikona i ne sadrži niti jedan rub. Kruskalov algoritam najprije dodaje rub (a, e), budući da je njezina težina najmanja, a vertices a i e su u različitim komponentama povezivanja šume F (rub (a, e) zelen), zatim rub (c, d) Da ovaj rub ima najmanju težinu od rubova grafikona koji ne pripada F, a zelen je, a iz istih je razloga dodan i rub (a, b). Međutim, rub (b, e) se preskače, iako ima najmanje težine preostalih rubova jer je crvena: vrhovi b i e pripadaju istoj povezanoj komponenti šume F, to jest, ako dodamo rub (b, e) na F, ciklus. Zatim se dodaje zeleni rub (b, c), crveni rub (c, e) se preskače, a zatim d, e. Tako se sukcesivno dodaju rubovi (a, e), (c, d), (a, b), (b, c). Iz nje se sastoji od optimalnog kostura izvornog grafa. Tako algoritam radi u ovom slučaju Obojio sam se. Primjer pokazuje ovo.

Slika prikazuje graf koji se sastoji od dvije komponente povezivanja. Podebljane linije prikazuju rubove optimalnog okvira (zelene), konstruirane pomoću algoritma Kruskal.

Gornja slika prikazuje početni grafikon, a na donjem - kostur minimalne težine, konstruiran za njega uz pomoć razmatranog algoritma.

Redoslijed dodanih rubova: (1.6); (0,3), (2,6) ili (2,6), (0,3) - nije bitno; (3.4); (0,1), (1,6) ili (1,6), (0,1), također je indiferentan (5,6).

Kraskalov algoritam pronalazi praktičnu primjenu, na primjer, kako bi optimizirao komunikacijske ploče, ceste u novim mikrorazinama u lokalitetima svake zemlje, kao iu drugim slučajevima.