Kruskal algoritm - ehitus optimaalse raamistiku

In 19. sajandi alguses geometer Jakob Steiner Berliini seatud ülesande, kuidas ühendada kolm küla, nii et nende pikkus oli lühim. Hiljem ta kokku probleemiga: see on vajalik leida punkti tasapinnal, kaugus seda n teiste punktide olid madalaim. 20. sajandil, see jätkab tööd selle teema. Otsustati võtta paar punkti ja ühendada neid nii, et nendevaheline kaugus oli lühim. See kõik on erijuhtum probleemi uuritakse.

"Ahne" algoritm

Kruskal algoritm viitab "ahned" algoritmi (nimetatakse ka gradient). Sisuliselt need - kõrgeim võit iga samm. Mitte alati, "ahne" algoritme pakkuda parimat lahendust. On teooria, mis näitab, et nende taotlus konkreetsed ülesanded nad annavad parima lahenduse. See on teooria matroids. Kruskal algoritm viitab sellistele probleemidele.

Leidmine minimaalse rümbamassiga

Vaadatud algoritmi konstruktide optimaalse raami arvu. Probleem on järgmine. Dan graa s ilma paralleelse servad ja silmuseid ja servade hulk on antud kaalufunktsioon w, mis loovutab igale serva e - kehakaalu ribi - w (e). Kaalu iga alamhulga ribisid on masside summa selle servadest. Nõutav leida skelett väike kaal.

kirjeldus

Kruskal algoritm töötab. Esiteks kõik servad esialgse graafik on paigutatud tõusvas järjekorras kaalu. Esialgu raami ei sisalda ribid vaid hõlmab kõiki tippe. Pärast järgmise algoritmi samm on juba ehitatud rümba osa, mis on täismetsa, üks serv on lisatud. See ei ole valitud meelevaldselt. Kõik servad graafik, mis ei kuulu raami, võib nimetada punane ja roheline. Ülemine iga punaste äärtega on sama komponendi valmimisel metsa ühenduvus ja roheline tops - erinevad. Seega, kui sa lisada punane serv on tsükli, ja kui roheline - nagu sai pärast seda sammu puidu ühendatud osad on vähem kui üks. Seega saadud ehitus ei saa lisada ei punane serv, kuid ühtegi rohelised serv võib lisada, et saada metsa. Ja lisab roheline serv minimaalse kaalu. Tulemuseks on raamistikus minimaalne kaal.

täitmine

Olgu praeguse metsa F. See jagab tippude valdkonnas ühenduvus (nende liit vormid F, ja nad on ümberasustatud). Mõlemast servast punase tipu need asuvad ühes tükis. Osa (x) - funktsioon, mis iga tipu x tagastab osa nimi, see kuulub x. Unite (x, y) - protseduur, mis ehitab uue sektsiooni, kuhu kuuluvad osade kombineerimise x ja y ja kõiki muid osi. Olgu n - servade arv. Kõik need mõisted sisalduvad Kruskal algoritm. rakendamine:

1. Korraldada kõik servad graafik alates 1. n-nda kasvavalt kaaluga. (Ai, bi - i tipuga serva number).

2. for i = 1 kuni n teha.

3. x: = Osa (ai).

4. y: = Osa (bi).

5. Kui x ei võrdu y seejärel Unite (x, y), lisada servaga F i number.

õigsuse

Olgu T - raami originaal graafik ehitatud Kruskali algoritm ja S - selle suvalise raami. Me peame tõestama, et w (T) ei ole suurem kui w (S).

Olgu M - ribidega S, P - arvukalt uimed T. Kui S ei ole võrdne T, siis on raami ribi et T, mis ei kuulu S. S. et avanevad tsükli, nimetatakse seda C. C eemalda ühestki servast es, mis kuulub S. Saame uue raami, sest servad ja tipud on sama. Selle massi ei ole suurem kui w (S), sest w (et) enam w (id) on võimu Kruskal algoritm. See operatsioon (asendaja T S ribisid ribid) korratakse niikaua saada T. kaal igal järgneval vastuvõetud kaadri vahel ei ole suurem kui eelmine massi, mis tähendab, et w (T) ei ole suurem kui w (S).

Stabiilsuses Kruskal algoritm tuleneb teoreemi Rado-Edmonds kohta matroids.

Taotlus Näited Kruskal algoritm

Dan graafikul sõlmedega a, b, c, d, e ja ribid (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) (d, e). Kaalud servad on toodud tabelis ja joonisel. Esialgu ehitus metsa F sisaldab kõiki tippe graafiku ja ei sisalda ühtegi ribid. Algoritm Kruskal esimese lisage ribi (a, e), kuna kaalu oli väikseim ning tippe e ja a on eri komponente puitu ühenduvus F (ribi (a, e) on roheline), siis ribi (c, d), sest et vähemalt selle serva kaalust graafikul servad, mis ei kuulu F, ja see on roheline, siis samadel põhjustel kogune serva (a, b). Aga serva (b, e) on möödas, kuigi tema ja minimaalne kaal ülejäänud servad, sest see on punane: tippude b ja e kuuluvad samasse osa metsa ühenduvus F, see tähendab, kui lisame F serva (b, e), on moodustatud tsükkel. Seejärel lisati roheline serv (b, c), lastakse punase servaga (c, e) ja seejärel d, e. Seega servad lisatakse järjestikku (a, e), (c, d), (a, b), (b, c). Alates nihera optimaalse raami ja koosneb esialgsest graafik. Nii et kui ta tegutseb algoritmi Kruskal. Üks näide on toodud.

Joonisel on kujutatud graafik, mis koosneb kahest ühendatud komponente. Rasvase jooned näitavad optimaalset raami ribid (roheline) konstrueerimiseks kasutati Kruskal algoritm.

Ülemine pilt näitab originaal graafik ja põhja - skelett minimaalne kaal, ehitatud teda kasutades algoritmi.

Järjestus lisati ribid (1,6); (0,3), (2,6) või (2,6), (0,3) - ei ole oluline; (3,4); (0,1), (1,6) või (1,6), (0,1), samuti hoolitseda (5,6).

Kruskal algoritm leiab praktilist rakendamist, näiteks optimeerida tihend side, teed uue elamurajoonides paikkonnad igas riigis, samuti muudel juhtudel.