Kruskal algoritem - gradnja optimalnega okvira

V začetku geometer 19. stoletja Jakob Steiner iz Berlina določi nalogo, kako povezati tri vasi, tako da je bila njihova dolžina najkrajša. Kasneje je povzel problem: to je potrebno, da bi našli mesto na letalu, so bili od njega, da n drugih točkah najnižja. V 20. stoletju, je še vedno delo na to temo. Sklenjeno je bilo, da se nekaj točk in jih povezati tako, da je razdalja med njima najkrajša. Vse to je poseben primer problema pa so jih raziskali.

"Požrešen" algoritem

Kruskal algoritem se nanaša na "požrešen" algoritem (imenovan tudi gradient). Bistvo tistih - najvišji dobitek na vsakem koraku. Ne vedno, "požrešen" algoritmi zagotavljajo najboljšo rešitev problema. Obstaja teorija, ki kaže, da pri njihovi uporabi za posebne naloge, ki jih dajejo optimalno rešitev. To je teorija matroids. Kruskal algoritem se nanaša na takšne probleme.

Iskanje minimalno težo trupa

Ogledov algoritem gradi optimalno število sličic. Problem tega je, kot sledi. Dan neusmerjeno graf brez vzporednih robov in zank, ter niz robov je podan funkcijo Masa, ki ustrezno število za vsako robno e - mas rebro - w (e). Masa vsak podniz množice reber je seštevek mas njegovih robov. Zahteva, da bi našli okostje majhno težo.

opis

Kruskal algoritem deluje. Prvič, vsi robovi začetne grafu so razvrščeni v naraščajočem vrstnem redu glede na uteži. Sprva je okvir ne vsebuje nobenih reber, ampak vključuje vse tocke. Po naslednjem koraku algoritma za že zgrajene del trupa, ki je zajema gozd, je dodal še en rob. Ni izbrana samovoljno. Vsi robovi grafa, ki ne sodijo v okvir, se lahko imenuje rdeča in zelena. Na vrhu vsakega rdečimi robovi so iste komponente v okviru gradnje gozdne povezljivost in zeleni vrhovi - drugačna. Torej, če dodate na rdeči rob, da je cikel, in če je zeleno - kot ga je prejel po tem koraku bo les povezane komponente biti manj kot eno. Tako je nastala gradnja ne more dodati nobene rdeče prednost, ampak vse zeleni rob se lahko doda, da se gozd. In dodaja zelen rob z minimalno težo. Rezultat je okvir za minimalno težo.

izvajanje

Označuje trenutno gozd F. To ločuje niz vozlišč na področju povezljivosti (njihove sindikalne oblike F, in so Disjunktan). Na obeh robovih rdeče tock ležijo v enem kosu. Del (x) - funkcija, ki za vsako tocko x vrne del imena, pripada x. Unite (x, y) - postopek, ki gradi novo particijo, ki sestoji iz kombiniranja delov X in Y ter vse ostale dele. Naj bo n - število robov. Vsi ti pojmi so vključeni v algoritem Kruskal je. izvajanje:

1. Razporedi vse robove grafu od 1. do n-ti naraščajočimi uteži. (Ai, dvo - i z vrha številom robov).

2. za i = 1 do n narediti.

3. X: = del (ai).

4. Y: = del (dvakrat).

5. Če je X ne enaka y nato združimo (x, y), da se vključi s številom The Edge F i.

pravilnost

Naj T - okvir prvotnega grafa zgrajena z uporabo Kruskal algoritem in S - njegova samovoljna okvirja. Moramo dokazati, da w (T) ni večja od w (I).

Naj M - množica plavuti S, P - množico plavuti T. Če S ni enako T, potem je okvir rebro et T, ki ne pripadajo S. S. et mejijo cikel, ki se imenuje C, C odstrani iz enega od robov es, ki spada S. dobimo nov okvir, saj robove in oglišča je isto. Njena teža ni večja od w (S), saj w (et) ni več w (e) v moči Kruskal algoritma. Ta operacija (nadomestnih rebra tS o mnenju) ponovi, dokler prejemajo T. maso vsakega naslednjega prejeto okvir ni večja od prejšnjega teže, kar pomeni, da w (T) ni večja od w (I).

Robustnost algoritma Kruskal je razvidno iz izreka Rada-Edmonds na matroids.

Primeri uporabe Kruskal algoritem

Dan graf z vozlišči a, b, c, d, e in rebri (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) (d, e). Uteži robovi so prikazani v tabeli in na sliki. Sprva, gradnja gozd F vsebuje vse tocke na grafu in ne vsebuje nobenih reber. Algoritem Kruskal najprej dodati rebro (a, e), saj je imela težo najnižja, in tocke A in E sta v različnih komponent povezljivost lesa F (rebro (a, e) je zelene barve), nato pa je rebro (c, d), saj da vsaj ta masa rob grafov robov, ki ne pripadajo F, in je zelena, nato pa iz istega razloga pripada rob (a, b). Vendar pa je rob (b, e) opravili, čeprav on in minimalna teža preostalih robov, ker je rdeča: oglišči b in e pripadajo isti priključene komponente gozdnega F, ki je, če temu dodamo F rob (b, e), ki je nastala cikel. Nato dodamo zeleno rob (b, c), ki se prenaša rdeč rob (C, E) in potem d, e. Tako se doda robovi zaporedoma (a, e), (c, d), (a, b), (b, c). Od nihera optimalnega okvirja in je sestavljen iz prvotnega grafa. Torej, v tem primeru deluje algoritem Kruskal. Primer je prikazan.

Na sliki je graf, ki je sestavljen iz dveh povezanih komponent. Krepke črte kažejo optimalne rebra okvirja (zelena), zgrajene z uporabo Kruskal algoritem.

Zgornja slika prikazuje prvotni graf, in dno - okostje minimalno težo, zgrajena zanj z uporabo algoritma.

Zaporedje dodanih reber (1.6); (0,3), (2,6) ali (2,6), (0,3) - ni pomembno; (3,4); (0,1), (1,6) ali (1,6), (0,1), prav tako skrbi (5,6).

Kruskal algoritem najde praktično uporabo, na primer, za optimizacijo komuniciranja tesnilo, ceste v novih stanovanjskih sosesk krajev v vsaki državi, kot tudi v drugih primerih.