Kruskal er reiknirit - byggingu hagkvæmustu ramma

Í upphafi 19. aldar geometer Jakob Steiner frá Berlin setja verkefni um hvernig á að tengja þrjá þorpum þannig að þeirra lengd var stysta. Síðar, í stuttu máli er hann vandamál: það er nauðsynlegt til að finna punkt í flugvél, fjarlægð frá henni til n önnur atriði voru lægst. Á 20. öld, það heldur áfram að vinna um þetta efni. Það var ákveðið að taka nokkur stig og tengja þá þannig að fjarlægðin milli þeirra var stystur. Þetta allt er sérstakt tilfelli af vandamálinu sé rannsakað.

"Greedy" reiknirit

reiknirit Kruskal er átt við "gráðugur" reiknirit (einnig kallað stigull). Kjarni þeirra - sem er hæsta vinna á hverju skrefi. Ekki alltaf, "gráðugur" reiknirit veita bestu lausn á því vandamáli. Það er kenning, sem sýnir að í umsókn sinni til sérstakra verkefna þeir gefa bestu lausn. Þetta er kenningin um matroids. reiknirit Kruskal er átt við slík vandamál.

Finndu lágmarks dilkum

Skoðað reiknirit býr hagkvæmustu ramma telja. Vandinn við það er eins og hér segir. Í ljósi undirected línurit án lykkjur og margar brúnir, og setja af sínum brúnir sett vægi virka W, sem úthlutar hver brún e-númer - þyngd rifinu - m (e). Vægi hvers hlutmengi í fjölda af rifjum er summa þungi jöðrum þess. Þarf að finna beinagrind af litlu þyngd.

Lýsing

reiknirit Kruskal virkar. Í fyrsta lagi allar hliðar á fyrstu línurit er raðað í vaxandi röð af þyngd. Upphaflega, ramma hjartarskinn ekki innihalda allir rif en felur í sér allar hornpunkta. Eftir næsta skref reiknirit til þegar byggt hluta skrokknum, sem er spannar skógur, einn brún er bætt við. Það er ekki valið af handahófi. Allar brúnir á myndinni, ekki tilheyra ramma, má kallast rautt og grænt. Efst á hverri rauðum brúnum eru í sömu hluti undir byggingu skógur tengsl, og græna boli - öðruvísi. Því ef þú bætir við rauða brún, það er hringrás, og ef græna - eins og tekið var eftir þetta skref viður tengdur hluti mun vera minna en einn. Þannig leiðir byggingu getur ekki bætt engin rauð brún, en allir grænn brún má bæta við að fá skóginn. Og bætir grænt brún með lágmarks þyngd. Niðurstaðan er rammi lágmarksþyngd.

framkvæmd

Að tákna núverandi skóginn F. Það skiptir mengi hornpunkta á sviði tengingu (union form þeirra F, og þeir eru disjoint). Á báðum brúnum rauðum hornum sem þeir liggja í heilu lagi. Hluti (x) - fall að fyrir hvern hornpunkt x skilar hluta af nafni, tilheyrir það x. Sameina (x, y) - aðferð sem byggir til nýja sneið, sem samanstendur af sameina hluta af X og Y og alla aðra hluta. Látum n - fjöldi brúnir. Öll þessi hugtök eru í reiknirit Kruskal er. framkvæmd:

1. Raða öllum brúnir línuritinu frá 1. til hækkandi lóðum n-ta. (Ai, bi - ég með Apex brún númer).

2. fyrir i = 1 til n gera.

3. x: = Hluti (Ai).

4. Y: = Part (BI).

5. Ef X er ekki jafn y þá Unite (x, y), til að fela í sér með brún F i númer.

rétttrúnaður

Látum T - ramma upprunalegu myndinni smíðaður með Kruskal reiknirit og S - handahófi ramma þess. Við verðum að sanna að m (t) er ekki meiri en m (S).

Látum M - fjölda ugga S, P - af fjölda ugga T. Ef S er ekki jafn T, þá er ramma rif et T, ekki tilheyra S. S. et legið um hringrás, það er kallað C. C fjarlægja úr hvaða brún ES, sem tilheyrir S. Við fá nýjan ramma, vegna þess að brúnir og hornpunkta er sú sama. Þyngd hennar er ekki meiri en m (S), þar sem W (et) ekki lengur m (ES) í krafti Kruskal reiknirit. Þessi aðgerð (varamaður T S rifflur til varnar á rif) verður endurtekin eins lengi og taka á móti T. The þyngd þeirra og þyngd síðari berast rammanum er ekki hærri en þau gömlu þyngd, sem felur í sér að W (T) er ekki meira en W (S).

Styrkur reiknirit Kruskal er leiðir af setningu af Rado-Edmonds á matroids.

Dæmi um notkun Kruskal algrím

Dan línurit með hnúta a, b, c, D, E og rifflur (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). Vægi brúnir eru sýnd í töflunni og á myndinni. Upphaflega, smíði skógur F inniheldur allt hornpunkta línurit og inniheldur ekki rif. Reiknirit Kruskal fyrst að bæta skurðinn (a, e), þar sem þyngd var lægst, og hornpunkta A og E eru í mismunandi þættir timbur tengingu F (skurðinn (a, e) er grænn), þá skurðinn (c, d), vegna þess að að minnsta kosti þetta brún þyngd línurit brúnir, ekki tilheyra F, og það er grænt, þá sömu ástæðum safnar brún (a, b). En brún (b, e) er liðinn, jafnvel þótt hann og lágmarks þyngd af hinum brúnir, því það er rautt: hornpunkta b og e tilheyra sömu hluti skógur tengsl F, það er, ef við bætum við F brún (b, e), er mynduð hringrás. Síðan bætti grænt brún (b, c), er liðin rauður brún (c, e), og síðan d, e. Þannig fætur bæta brúnir (a, e), (c, d), (a, b), (b, c). Frá nihera ákjósanlegur ramma og samanstendur af upprunalegu myndinni. Þannig að í þessu tilfelli að það rekur reiknirit Kruskal. Sem dæmi má nefna sýnd.

Myndin sýnir línurit, sem samanstendur af tveimur tengdum þáttum. Feitletruðu línurnar gefa til kynna ákjósanlegur rammi rifbeinunum (grænt) smíðaðir með Kruskal reiknirit.

Efsta myndin sýnir upprunalega línurit, og botn - beinagrind af lágmarks þyngd, byggt fyrir hann með því að nota reiknirit.

Röð af the added rif (1,6); (0,3), (2,6) eða (2,6), (0,3) - er ekki mikilvægt; (3,4); (0,1), (1,6) eða (1,6), (0,1), einnig sjá (5,6).

reiknirit Kruskal er finnur beitingu, til dæmis, til að hámarka gasket fjarskipti, vegi í nýjum húsnæði bú stöðum í hverju landi, eins og í öðrum tilvikum.