Kruskal algoritms - optimālā skeleta konstrukcija

19. gadsimta sākumā ģeometrs no Berlīnes Jacob Steiner noteica uzdevumu, kā savienot trīs ciemus tā, lai to garums būtu īsākais. Pēc tam viņš vispārināja šo problēmu: ir nepieciešams atrast punktu plaknē tā, ka attālums no tā uz n citiem punktiem bija mazākais. 20. gadsimtā darbs pie šī temata turpinājās. Tika nolemts paņemt dažus punktus un savienot tos tādā veidā, ka attālums starp tiem bija īsākais. Tas viss ir īpašs pētāmās problēmas gadījums.

Mantkārie algoritmi

Kruskal algoritms attiecas uz "mantkārīgiem" algoritmiem (tos sauc arī par gradienta algoritmiem). Šo būtību - lielākā uzvara katrā solī. Vislabākais uzdevuma risinājums ne vienmēr ir "mantkārīgs" algoritms. Pastāv teorija, kas parāda, ka, pielietojot īpašas problēmas, tie nodrošina optimālu risinājumu. Šī ir matroīdu teorija. Kruskal algoritms attiecas uz šādām problēmām.

Minimālā svara skeleta atrašana

Apskatāmais algoritms konstruē optimālo diagrammas skeletu. Problēma par to ir šāda. Noregulēts grafs bez vairākām malām un cilpām, un tā malu komplektā tiek dota svara funkcija w, kas piešķir katrai malai e skaitli - malas svars - w (e). Katras malu komplekta apakšgrupas svars tiek noteikts pēc tā malu kopsummas. Ir nepieciešams atrast mazākā svara skeletu.

Apraksts

Kruskal algoritms darbojas tāpat kā tas. Pirmkārt, visas sākotnējā grafika malas ir sakārtotas svaru palielināšanas kārtībā. Sākumā sistēma nesatur nekādas malas, bet ietver visas diagrammas virsotnes. Pēc algoritma nākamā posma jau izveidotajai struktūrai tiek pievienota viena mala, kas ir aptverošs mežs. To neizvēlas patvaļīgi. Visas grafika malas, kas nepieder pie skeleta, var saukt par sarkanu un zaļu. Katras sarkanas ribas virsmas atrodas vienā veidotā meža savienojuma komponentā, un zaļās virsmas ir dažādās sastāvdaļās. Tāpēc, ja tajā pievienojat sarkanu malu, parādās cikls un, ja zaļā krāsā parādās iegūtajā meža posmā, piesaistītajam komponentam būs mazāk par vienu. Tādējādi iegūto konstrukciju nevar pievienot sarkanās malas, bet meža ieguvei var pievienot jebkuru zaļo malu. Un tiek pievienota zaļa riba ar minimālo svaru. Rezultāts ir mazākā svara struktūra.

Īstenošana

Mēs apzīmējam pašreizējo mežu F. Tas sadala grafu virsotņu kopu saistītajos domēnos (to savienojošās formas F, un tās nepāršķēš pa pāriem). Sarkanajās malās vienā pusē ir abas virsas. Daļa (x) ir funkcija, kas atdod tās daļas nosaukumu, uz kuru x pieder katrai virsotnei x. Unite (x, y) ir procedūra, kas izveido jaunu nodalījumu, kas sastāv no x un y daļas un visām pārējām daļām. Ļaujiet n būt grafu malu skaits. Visi šie jēdzieni ir iekļauti Kruskal algoritmā. Īstenošana:

1. Sakārtojiet visas diagrammas malas no 1. līdz n. Augošā svara. (Ai, bi ir malas virsotnes ar indeksu i).

2. Ja i = 1 līdz n darīt.

3. X: = daļa (ai).

4. Y: daļa (bi).

5. Ja x nav vienāds ar y, tad savienojumā Unite (x, y) iekļaujiet malu ar numuru i F

Pareizība

Ļaujiet T ir sākotnējā grafika skelets, kas izveidots, izmantojot Kruskal algoritmu, un S ir tā patvaļīgs skelets. Ir nepieciešams pierādīt, ka w (T) nepārsniedz w (S).

Ļaujiet, lai M ir malu kopums S, un P ir malu kopums T. Ja S nav vienāds ar T, tad pastāv maliņa et of T, kas nepieder pie S. Mēs pievienojam et ar S. Mēs veidojam ciklu, to saucam C. Mēs izņemam no C jebkuru malu, kas pieder S. Tiek iegūts jauns rāmis, jo tajā ir gan vienas, gan otra malas un virsotnes. Tās svars nepārsniedz w (S), jo w (et) nav lielāks par w (es) ar Kruskal algoritmu. Šī operācija (S malu aizstāšana ar T malām) tiks atkārtota, līdz iegūstam T. Katra nākamā skeleta svars nav lielāks par iepriekšējā svara svaru, no kura izriet, ka w (T) ir ne vairāk kā w (S).

Arī Kruskala algoritma pareizība izriet no Rado-Edmonda teorēmas par matroīdiem.

Kruskal algoritma piemēri

Diagramma ar virsotnēm a, b, c, d, e un malām (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (D, e). Malu svars ir redzams tabulā un attēlā. Sākotnēji uzbūvētais mežs F satur visas diagrammas virsotnes un nesatur nevienu malu. Kruskal algoritms vispirms pievieno malu (a, e), jo tās svars ir mazākais, un virsotnes a un e atrodas dažādās meža F savienojamības komponentēs (maliņa (a, e) ir zaļa), tad mala (c, d), jo Šī mala ir vismazāk svara no grafa malām, kas nav F, un tā ir zaļa, tad to pašu iemeslu dēļ tiek pievienota mala (a, b). Taču mala (b, e) tiek izlaista, lai gan tai ir mazākais atlikušo malu svars, jo tā ir sarkana: virsotnes b un e pieder tai pašai savienotajai meža F sastāvdaļai, tas ir, ja mēs pievienojam malu (b, e) līdz F Cikls. Tad pievieno zaļo malu (b, c), tiek izlaista sarkanā mala (c, e), un pēc tam d, e. Tādējādi secīgi tiek pievienotas malas (a, e), (c, d), (a, b), (b, c). No tā izveidojas sākotnējā grafika optimālais skelets. Tādā veidā algoritms darbojas šajā gadījumā Es krāsoju Piemērs parāda to.

Attēlā redzams grafiks, kas sastāv no diviem saistītiem komponentiem. Dziļās līnijas parāda optimālās sistēmas (zaļas) malas, kas izveidotas, izmantojot Kruskal algoritmu.

Augšējā figūra parāda sākotnējo diagrammu, bet apakšējā - minimālā svara skeletu, kas šim nolūkam izveidots ar aplūkotā algoritma palīdzību.

Pievienoto malu secība: (1.6); (0,3), (2,6) vai (2,6), (0,3) - nav nozīmes; (3.4.); (0,1), (1,6) vai (1,6), (0,1), arī ir vienaldzīgi (5,6).

Kraskala algoritms atrod praktisku pielietojumu, piemēram, lai optimizētu sakaru spilventiņus, ceļus jaunos mikrorajonos katras valsts vietās, kā arī citos gadījumos.