Kruskal ya algorithm - ujenzi wa mfumo mojawapo

Mapema karne ya 19 pimapima Jakob Steiner kutoka Berlin kuweka kazi ya jinsi ya kuunganisha vijiji vitatu ili urefu wao ilikuwa fupi. Baadaye, muhtasari tatizo: ni unahitajika ili kupata uhakika katika ndege, umbali kutoka kwa pointi n wengine walikuwa chini. Katika karne ya 20, ni inaendelea kufanya kazi juu ya mada hii. Iliamuliwa kuchukua pointi chache na kuungana nao kwa namna ambayo umbali kati yao alikuwa mfupi. Haya yote ni kesi maalum ya tatizo kuwa alisoma.

"Tamaa" algorithm

algorithm Kruskal unahusu "tamaa" algorithm (pia huitwa gradient). kiini cha hiyo - kushinda juu ya kila hatua. Si mara zote, "tamaa" mipangilio kutoa suluhisho bora kwa tatizo. Kuna nadharia, kuonyesha kwamba katika maombi yao kwa kazi maalum wao kutoa ufumbuzi optimum. Hii ni nadharia ya matroids. algorithm Kruskal unahusu matatizo kama hayo.

Kupata kiwango cha chini mzoga uzito

Kutazamwa algorithm anajenga mojawapo frame kuhesabu. tatizo la ni kama ifuatavyo. Dan undirected graph bila kingo sambamba na mizunguko, na seti ya kingo anapewa uzito kazi w, ambayo anayepeana idadi ya kila makali e - uzito ubavu - w (e). uzito wa kila subset ya wingi wa mbavu ni jumla ya uzito wa kingo zake. Unahitajika ili kupata mifupa ya uzito mdogo.

maelezo

algorithm Kruskal ya kazi. Kwanza, kila pembe za graph ya awali katika mpangilio wa kupanda utaratibu wa uzito. Awali, sura haina mbavu yeyote lakini ni pamoja na vipeo vyote. Baada ya hatua ya pili ya algorithm sehemu tayari ujenzi wa mzoga, ambayo ni msitu Guinea, makali moja ni aliongeza. Si waliochaguliwa kiholela. kingo zote za graph, si mali ya sura, anaweza kuitwa nyekundu na ya kijani. juu ya kila pembe nyekundu ni katika sehemu moja chini ya kuunganishwa ujenzi misitu, na vilele ya kijani - tofauti. Kwa hiyo, kama wewe kuongeza makali nyekundu, kuna mzunguko, na kama kijani - kama kupokea baada ya hatua hii mbao uhusiano vipengele itakuwa chini ya moja. Hivyo, kusababisha ujenzi hawezi kuongeza hakuna makali nyekundu, lakini yeyote makali ya kijani inaweza kuongezwa kwa kupata misitu. Na kuongeza makali ya kijani na uzito kiwango cha chini. Matokeo yake ni mfumo wa uzito kiwango cha chini.

utekelezaji

Kuashiria misitu sasa F. Ni hugawanya seti ya vipeo katika uwanja wa kuunganishwa (muungano fomu zao F, na ni disjoint). Pembezoni zote mbili za vipeo nyekundu wao uongo kwa kipande kimoja. Sehemu ya (x) - kazi kuwa kwa kila kipeo x anarudi sehemu ya jina, ni mali x. Unite (x, y) - utaratibu kwamba hujenga kizigeu mpya, yenye kuchanganya maeneo ya x na y na sehemu zote nyingine. Hebu n - idadi ya kingo. dhana hizi zote ni pamoja na katika algorithm Kruskal ya. utekelezaji:

1. Panga kingo zote za graph kutoka 1 hadi kupaa uzito n-th. (Ai, bi - i na kilele simu makali).

2. kwa i = 1 kwa n kufanya.

3. x: = Sehemu (ai).

4. y: = Sehemu (bi).

5. Kama x hana y sawa kisha Unite (x, y), ni pamoja na pamoja na idadi makali F i.

usahihi

Hebu T - sura ya graph ya awali yalijengwa kwa kutumia Kruskal algorithm na S - sura yake kiholela. Tuna kuthibitisha kuwa w (T) si zaidi ya w (S).

Hebu M - wingi wa mapezi S, P - wingi wa mapezi T. Kama S si sawa na T, kisha kuna sura ubavu et T, si mali ya S. S. et paka mzunguko, inaitwa C. C kuondoa kutoka es yoyote makali, mali S. Sisi kupata sura mpya, kwa sababu ya kingo na vipeo ni sawa. uzito wake ni mkubwa kuliko w (S), tangu w (et) tena w (ni) kwa nguvu Kruskal algorithm. Operesheni hii (badala T S mbavu juu ya mbavu) kitarudiwa mradi kupokea T. uzito wa kila sura inayofuata kupokea si zaidi ya uzito wa awali, ambayo ina maana kwamba w (T) si zaidi ya w (S).

robustness ya algorithm Kruskal ya ifuatavyo kutoka theorem ya Rado-Edmonds juu matroids.

Maombi Mifano Kruskal algorithm

Dan graph na michoro, b, c, d, e na mbavu (b), (, e), (b, c), (b, e), (c, d), (c, e) , (d, e). uzito wa kingo ni umeonyesha katika meza na katika takwimu. Awali, ujenzi msitu F lina vipeo vyote vya graph na haina mbavu yoyote. Algorithm Kruskal kwanza kuongeza ubavu (, e), kwa vile uzito na chini, na vipeo na e ni katika vipengele mbalimbali mbao kuunganishwa F (ubavu (, e) ni kijani), kisha ubavu (c, d), kwa sababu kwamba angalau huu makali uzito wa kingo graph, si mali ya F, na ni ya kijani, basi ni kwa sababu moja inaingia makali (b). Lakini makali (b, e) ni kupita, hata kama yeye na uzito chini ya kingo iliyobaki, kwa sababu ni nyekundu: vipeo b na e ni wa sehemu hiyo ya kuunganishwa msitu F, yaani, kama sisi kuongeza F makali (b, e), ni sumu mzunguko. Kisha aliongeza makali ya kijani (b, c), ni kupita nyekundu makali (c, e), na kisha d, e. Hivyo, kingo ni aliongeza sequentially (, e), (c, d), (b), (b, c). Kutoka nihera mojawapo frame na lina graph ya awali. Hivyo katika kesi hii ni kazi algorithm Kruskal. mfano ni umeonyesha.

takwimu inaonyesha graph, ambalo lina sehemu mbili kushikamana. mistari ujasiri zinaonyesha mojawapo frame mbavu (kijani) yalijengwa kwa kutumia Kruskal algorithm.

picha juu inaonyesha graph ya awali, na chini - mifupa ya uzito ndogo, kujengwa kwa ajili yake kwa kutumia kanuni duni.

mlolongo wa mbavu imeongezwa (1.6); (0,3), (2,6) au (2,6), (0,3) - si muhimu; (3,4); (0,1), (1,6) au (1,6), (0,1), pia huduma (5,6).

algorithm Kruskal ya anaona matumizi halisi, kwa mfano, kuongeza gasket mawasiliano, barabara katika mpya ya makazi maeneo katika kila nchi, na pia katika hali nyingine.