Kruskal-algoritmi - optimaalisen luuran rakentaminen

1800-luvun alkupuolella Berliinissä toimiva geometri Jacob Steiner asetti tehtävän yhdistämään kolme kylää siten, että niiden pituus oli lyhyin. Tämän jälkeen hän yleisti tämän ongelman: sen on löydettävä piste tasossa siten, että etäisyys siitä n: n muihin pisteisiin oli pienin. 1900-luvulla jatkettiin työtä tämän aiheen parissa. Päätettiin ottaa muutamia pisteitä ja liittää ne siten, että niiden välinen etäisyys oli lyhyin. Tämä on erityinen tapa tutkittava ongelma.

Greedy algoritmit

Kruskal-algoritmi viittaa "ahneisiin" algoritmeihin (niitä kutsutaan myös gradienttialgoritmiksi). Niiden ydin - suurin voitto jokaisessa vaiheessa. Ei aina "ahne" algoritmeja anna parhaan ratkaisun tehtäväksi. On olemassa teoria, joka osoittaa, että kun niitä sovelletaan tiettyihin ongelmiin, ne tarjoavat optimaalisen ratkaisun. Tämä on matroidin teoria. Kruskal-algoritmi liittyy tällaisiin ongelmiin.

Vähimmäispainon luuston luonti

Tarkasteltava algoritmi rakentaa graafin optimaalisen luuranon. Ongelma siitä on seuraava. Annet- taan suuntaamaton kaavio, jossa ei ole useita reunoja ja silmukoita, ja sen reunaryhmälle annetaan painotoiminto w, joka antaa jokaiselle reunalle e-numeron - reunan painon - w (e). Reunojen sarjan kunkin osajoukon paino määräytyy reunojen painojen summan mukaan. Sen on löydettävä pienimmän painon luusto.

kuvaus

Kruskalin algoritmi toimii näin. Ensin kaikki alkuperäisen kaavion reunat on järjestetty lisääntyvien painojen mukaan. Aluksi kehys ei sisällä reunoja, mutta siinä on kaikki kaavion vertikaalit. Algoritmin seuraavan vaiheen jälkeen yksi reunus lisätään jo kehitettyyn osaan kehyksestä, joka on kattava metsä. Sitä ei ole valittu mielivaltaisesti. Kaavion kaikki reunat, jotka eivät kuulu luurankoon, voidaan kutsua punaiseksi ja vihreiksi. Jokaisen punaisen kylkiluudun kärjet ovat yhteen rakennetun metsän kytkennän komponenttina ja vihreän pisteet ovat eri komponentteina. Siksi, jos lisäät punaisen reunan, sykli ilmestyy, ja jos vihreä näkyy tuloksena olevassa metsävaiheessa, liitetty laite vähenee vähemmän. Näin ollen ei saa lisätä punaista reunaa tuloksena olevalle rakenteelle, mutta kaikki vihreät reunat voidaan lisätä metsän saamiseksi. Ja lisätään vihreä, vähimmäispainoinen rinta. Tuloksena on pienin paino.

täytäntöönpano

Me tarkoitamme nykyistä metsää F. Se jakaa kaavion vertikaaliryhmän kytkettyihin verkkotunnuksiin (niiden liittymismuodot F ja ne eivät leikkaa toisiaan pareittain). Punainen reunat molemmat huippupisteet sijaitsevat yhdessä osassa. Osa (x) on funktio, joka palauttaa sen osan nimen, johon x kuuluu kullekin kärhistölle x. Unite (x, y) on menettely, joka rakentaa uuden osion, joka koostuu osista x ja y ja kaikista muista osista. Olkoon n kaavion reunojen lukumäärä. Kaikki nämä käsitteet sisältyvät Kruskal-algoritmiin. toteutus:

1. Järjestä kaavion kaikki reunat ensimmäisestä nostamaan nousevaan painoon. (Ai, bi ovat reunan vertikaaleja indeksillä i).

2. I = 1 n: lle.

3. X: = osa (ai).

4. Y: = osa (bi).

5. Jos x ei ole yhtä suuri kuin y ja sitten Unite (x, y), sisällytä reunus, jonka numero on F.

oikeellisuutta

Anna T olevan Kruskal-algoritmin avulla konstruoidun alkuperäisen graafin luusto ja anna S olevan sen mielivaltainen luuranko. On osoitettava, että w (T) ei ylitä w (S).

Olkoon M sarjan S reunojen joukko ja P sarja T: n reunoja. Jos S ei ole yhtä kuin T, niin olemassa on T: n reuna, joka ei kuulu S: hen. Liitymme S: ksi. Muodos- tamme sykliä, me kutsumme sitä C. Poistamme C: stä kaikki reunat, jotka kuuluvat S. Uusi kehys saadaan, koska siinä molemmat reunat ja pisteet ovat samat. Sen paino ei ylitä w (S), koska w (et) ei ole suurempi kuin w (t) Kruskal-algoritmilla. Tämä toimenpide (S: n reunojen korvaaminen T: n reunoilla) toistetaan, kunnes saadaan T. Kunkin myöhemmän luuran paino ei ole suurempi kuin edellisen paino, josta seuraa, että w (T) on enimmillään w (S).

Myös Kruskalin algoritmin oikeellisuus seuraa matroideja Rado-Edmondsin lauseesta.

Esimerkkejä Kruskal-algoritmin soveltamisesta

(A, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (D, e). Reunojen painot on esitetty taulukossa ja kuvassa. Alun perin rakennettu metsä F sisältää kaavion kaikki pisteet ja ei sisällä yhtä reunaa. Kruskal-algoritmi tuo ensin reunan (a, e), koska sen paino on pienin ja vertikaalit a ja e ovat metsän F eri liitäntäkomponenteissa (reunus (a, e) vihreä), sitten reunan (c, d) Että tämä reuna on pienin paino kaavion reunasta, joka ei kuulu F: hen, ja se on vihreä, ja samasta syystä lisätään reunus (a, b). Mutta reuna (b, e) ohitetaan, vaikka jäljellä olevilla reunoilla on pienin paino, koska se on punainen: vertikaalit b ja e kuuluvat samaan metsän F kytkettyyn komponenttiin, eli jos lisäämme reunan (b, e) F: sykli. Tällöin vihreää reunaa (b, c) lisätään, punaista reunaa (c, e) ohitetaan ja sitten d, e. Siten reunat (a, e), (c, d), (a, b), (b, c) lisätään peräkkäin. Sieltä alkuperäisen graafin optimaalinen luuranko koostuu. Näin algoritmi toimii tässä tapauksessa Värjäisin. Esimerkki osoittaa tämän.

Kuvassa on kaavio, joka koostuu kahdesta liitetystä osasta. Lihavilla linjoilla näkyy optimaalisen kehyksen (vihreä) reunat, jotka on rakennettu Kruskal-algoritmilla.

Ylemmässä kuvassa näkyy alustava kaavio ja alempi - vähimmäispainon luuranko, joka on rakennettu sille harkitun algoritmin avulla.

Lisättyjen reunojen järjestys: (1.6); (0,3), (2,6) tai (2,6), (0,3) - ei ole väliä; (3,4); (0,1), (1,6) tai (1,6), (0,1), on myös välinpitämätön (5,6).

Kraskalin algoritmilla on käytännön sovellus esim. Tiedonsiirtotyyppien optimoimiseksi, uusien maakunnallisten alueiden teille kussakin maan paikkakunnalla sekä muissa tapauksissa.