Kruskalio algoritmas - optimalaus skeleto konstrukcija

XIX a. Pradžioje geometras iš Berlyno Jacob Steinernustatyti, kaip prijungti tris kaimus taip, kad jų ilgis būtų trumpiausias. Vėliau jis apibendrino šią problemą: reikia rasti tašką plokštumoje taip, kad atstumas nuo jo iki n kitų taškų būtų mažiausias. XX a. Darbas šioje temoje tęsėsi. Buvo nuspręsta paimti kelis taškus ir prijungti juos taip, kad atstumas tarp jų būtų trumpiausias. Tai yra ypatingas nagrinėjamos problemos atvejis.

Godus algoritmai

Kruskalio algoritmas reiškia "godingas" algoritmus(jie taip pat vadinami gradientu). Šių esmė - didžiausia pergalė kiekviename žingsnyje. Geriausias užduoties sprendimas yra ne visada "godus" algoritmai. Yra teorija, rodanti, kad taikant konkrečias problemas jie teikia optimalų sprendimą. Tai matroidų teorija. Kruskalio algoritmas susijęs su tokiomis problemomis.

Rasti minimalaus svorio skeleto

Nagrinėjamas algoritmas sukuria optimaliągrafiko skeletas. Problema yra tokia. Pateikiama nenukreipta grafika be daugialypių kraštų ir kilpų, o jo kraštų rinkinyje yra svorio funkcija w, kuri kiekvienam kraštui priskiria skaičių - krašto svorį - w (e). Kiekvieno krašto rinkinio pogrupio svoris nustatomas pagal jo kraštų svorių sumą. Reikia rasti mažiausio svorio skeletą.

Aprašymas

Kruskalio algoritmas veikia taip. Pirma, visi pradinio grafiko kraštai yra išdėstyti pagal svorio didinimo tvarką. Iš pradžių, rėmas nėra jokių šonkaulių, bet apima visus viršūnių. Po sekančio žingsnio algoritmo prie jau pastatyto dalį skerdenos, kuri yra apimanti miškų, vienas kraštas yra pridėta. Jis nėra pasirinktas savavališkai. Visi diagramoje kraštai, o ne, priklausanti prie rėmo, gali būti vadinamas raudonos ir žalios. Kiekvieno raudonais kraštais viršuje yra toje pačioje komponento statomas miško ryšį, o žali marškinėliai - skirtingi. Todėl, jei jūs įtraukiate į raudoną kraštą, yra ciklas, ir jei žalia - kaip gavo po šio žingsnio medienos prijungti komponentai bus mažiau nei vienas. Taigi, gautas statybos negalite pridėti ne raudoną kraštą, tačiau bet koks žalias kraštas gali būti pridėta gauti į mišką. Ir pridedamas žalias šonkaulis su minimaliu svoriu. Todėl gaunamas mažiausio svorio skeletas.

Įgyvendinimas

Apibūdinkite dabartinį mišką F. Jis suskaido grafiko viršūnių rinkinį į prijungtus domenus (jų sąveikos formos F, o jie nesikerta poromis). Raudoni kraštai turi abi dalis viršutine dalimi. Dalis (x) - tai funkcija, kuri grąžina tos dalies, kurios x priklauso kiekvienai vertei x, pavadinimą. Unite (x, y) yra procedūra, kuri sukuria naują skaidinį, susidedantį iš dalių x ir y bei visų kitų dalių sąjungos. Leiskite n būti grafiko kraštų skaičiumi. Visos šios sąvokos yra įtrauktos į Kruskal algoritmą. Įgyvendinimas:

1. Išdėstykite visus grafiko kraštus nuo 1 iki n-ojo didėjimo svorio. (ai, bi yra krašto viršūnės su indeksu i).

2. jei i = 1 iki n padaryti.

3. x: dalis (ai).

4. y: = dalis (bi).

5. Jei x nėra lygus y, tada Unite (x, y), įtraukite kraštą su numeriu i F

Teisingumas

Tegul T yra originalaus grafiko skeletas, sukonstruotas naudojant Kruskalio algoritmą, o S - savavališkas skeletas. Būtina įrodyti, kad w (T) neviršija w (S).

Tegul M - kraštų rinkinys S, P kraštų rinkinysT. Jei S yra nėra lygus T, tada yra kraštas et karkasas, T, o ne priklausanti S. S. et šlietis ciklą, tai yra vadinamas C. C pašalinti nuo bet kokių krašto es, priklausanti S. Mes gauti naują rėmo, nes kraštų ir smailių tai, kaip daug. Jo svoris yra ne didesnis nei W (S), nes w (ET) ne ilgiau W (-ai) į elektros Kruskal algoritmu. Ši operacija (pakaitiniai T S briaunų briaunų) bus kartojama tol, kol gauna T. kiekvieno vėlesnio gauta rėmo svoris yra ne didesnis nei ankstesniais masės, o tai reiškia, kad w (T), yra ne didesnis nei W (S).

Be to, algoritmo Kruskalui teisingumas kyla iš Rado-Edmondso teoremo matroiduose.

Kruskalio algoritmo taikymo pavyzdžiai

Atsižvelgiant į grafiką su viršūnėmis a, b, c, d, e ir kraštais (a,b), (a, e), (b, c), (B, E), (c, d), (c, e), (D, E). Briaunų svarsčiai rodomi lentelėje ir paveikslėlyje. Iš pradžių miško "F" statyboje yra visi grafiko viršūniai ir nėra vieno krašto. Algoritmas Kruskal pirmasis pridėti šonkaulio (A, E), nes svoris buvo mažiausias, o viršūnių A ir E yra skirtingų komponentų medienos Ryšiai F (šonkaulio (A, E) yra žalia), tada šonkaulio (C, D), nes , kad ne mažiau kaip šis kraštas svoris diagramoje kraštų, o ne priklausanti F, ir jis yra žalias, tada dėl tų pačių priežasčių kaupti briauną (a, b). Bet kraštas (B, E) yra perduodama, nors jis ir minimalus svoris likusių kraštų, nes ji yra raudona: viršūnių B ir E priklauso prie tos pačios sudedamosios miško ryšio F, tai yra, jei mes pridėti F kraštą (B, E), yra suformuotas ciklas. Tada pridedamas žalias kraštas (b, c), praleistas raudonas kraštas (c, e), o tada d, e. Tokiu būdu, kraštai yra iš eilės pridėta (A, E), (c, d), (a, b), (b, c). Iš jo sudaryta optimali pradinio grafiko skeletė. Tokiu būdu algoritmas veikia Aš dažytos Tai rodo pavyzdys.

Skaičius pateiktas grafikas, parodantis, kuri sudaryta iš dviejų sujungtų sudėtinių dalių. Drąsus linijos rodo optimalias rėmo šonkaulius (žalias) apskaičiuota naudojant Kruskal algoritmą.

Viršutinis paveikslėlis rodo pradinį grafiką, o apatiniame - minimalaus svorio skeletas, kuris buvo sukurtas pagal nagrinėjamą algoritmą.

Papildomų kraštų seka: (1.6); (0,3), (2,6) arba (2,6), (0,3) - nesvarbu; (3.4); (0,1), (1,6) arba (1,6), (0,1), taip pat yra abejingi (5,6).

Kruskalio algoritmas randa praktinį pritaikymą, pavyzdžiui, siekiant optimizuoti komunikacijos blokus, kelius naujose vietovėse kiekvienos šalies vietovėse ir kitais atvejais.