Kruskal syn algoritme - de bou fan in optimale kader

Yn de iere 19e ieu geometer Jakob Steiner út Berlyn set de taak fan hoe't te ferbinen trije doarpen sadat harren lingte wie de koartste. Letter, hy gearfette it probleem: it is nedich te finen fan in punt yn in tastel, de ôfstân fan it oan n oare punten wiene de leechste. Yn de 20e ieu, it giet om wurkjen oan dit ûnderwerp. Der waard besletten om in pear punten en ferbine har op sa'n wize dat de ôfstân tusken harren wie de koartste. Dit alles is in spesjaal gefal fan it probleem wurdt bestudearre.

"Gierig" algoritme

Kruskal syn algoritme ferwiist nei it "gierig" algoritme (ek neamd gradient). De essinsje fan harren - de heechste winst op elke stap. Net altyd, "gierig" algoritmen biede de bêste oplossing foar it probleem. Der is in teory, sjocht dat der yn harren applikaasje ta spesifike taken se jouwe de optimale oplossing. Dit is de teory fan matroids. Kruskal syn algoritme ferwiist nei sokke problemen.

It finen fan in minimum karkas gewicht

Besjoen algoritme Constructs in optimale frame telle. It probleem dêrfan is as folget. Dan undirected grafyk sûnder parallelle rânen en loops, en de dea fan 'e rânen wurdt jûn it gewicht funksje w, dy't kieze it oantal nei eltse rand e - gewicht rib - w (e). It gewicht fan eltse bepaald berik fan mearfâldichheid fan ribben is de som fan de gewichten fan syn rânen. Nedich te finen it skelet fan in lyts gewicht.

beskriuwing

Kruskal syn algoritme wurket. Earst, alle rânen fan de oarspronklike grafyk oardere binne yn oprinnende folchoarder fan de gewichten. Yn it earstoan, it frame befettet gjin ribben stean, mar ek alle hoekpunten. Nei't de folgjende stap fan de algoritme nei it al konstruearre diel fan 'e ies, dat is in spanning bosk, ien râne wurdt tafoege. It wurdt net keazen willekeurich. Alle rânen fan de grafyk, net heart ta it frame, kin neamd wurde read en grien. De boppekant fan elk reade rânen binne yn deselde komponint yn oanbou bosk Konnektivität, en de griene toppen - oars. Dêrom, as jo tafoegje oan de reade râne, der is in syklus, en as it grien - lykas krigen nei dizze stap it hout ferbûn komponinten sille wêze minder as ien. Sa, de resultearjende konstruksje kin net tafoegje gjin reade râne, mar eltse farnear kin tafoege wurde om it bosk. En heakket der in griene râne mei in minimum gewicht. It resultaat is in ramt fan minimum gewicht.

útfiering

Tsjutten de hjoeddeiske bosk F. It ferdielt de set fan hoekpunten op it mêd fan Konnektivität (harren uny foarmen F, en hja binne disjoint). By beide rânen fan de reade hoekpunten se lizze yn ien stik. Diel (x) - de funksje dy't foar eltse vertex x jout in part fan de namme, is it heart x. Unite (x, y) - in proseduere dy't bout in nije ôfskieding, besteande út kombinearjen parten fan x en y en alle oare ûnderdielen. Lit n - tal rânen. Al dizze begripen binne opnaam yn Kruskal syn algoritme. útfiering:

1. Regeljen al de rânen fan de grafyk fan de 1e oant n-th oprinnende gewichten. (Ai, bi - i mei apex râne nûmer).

2. foar i = 1 oant n dwaan.

3. x: = Part (ai).

4. y: = Part (bi).

5. As x docht net gelyk y dan Unite (x, y), op te nimmen mei de skerpte F i nûmer.

correctness

Lit T - frame fan de orizjinele grafyk oanlein mei help fan de Kruskal algoritme en S - syn willekeurige frame. Wy hawwe bewize dat w (T) is net grutter as w (S).

Lit M - mearfâldichheid fan finnen S, P - in mearfâldichheid fan Fins T. As S is net gelyk oan 't, dan is der in frame rib et T, net dy't ta S. S. et adjoin' e syklus, dat hjit C. C fuortsmite út alle râne es, hearrend S. Wy krije in nije frame, omdat de rânen en hoekpunten is itselde. Syn gewicht is net grutter as w (S), sûnt w (et) net mear w (es) yn in macht Kruskal algoritme. Dizze aksje (ynfaller T S ribben op ribben) werhelle wurde salang as ûntfange T. It gewicht fan elk folgjend ûntfongen frame is net grutter as de foarige gewicht, dat ymplisearret dat w (T) is net grutter as w (S).

It robustness fan Kruskal syn algoritme folget út 'e stelling fan Rado-Edmonds op matroids.

Applikaasje Foarbylden Kruskal algoritme

Dan grafyk mei knopen a, b, c, d, e en ribben (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). De gewichten fan de rânen wurde toand yn de tabel en yn 'e figuer. Ynearsten, bou bosk F befettet alle hoekpunten fan de grafyk en befettet gjin ribben. Algoritme Kruskal earst foegjen rib (a, e), sûnt it gewicht hie it leechste, en de hoekpunten a en e binne yn ferskillende ûnderdielen timber Konnektivität F (rib (a, e) is grien), dan de rib (c, d), omdat dat op syn minst dit râne gewicht fan grafyk rânen, net heart ta F, en it is grien, dan foar deselde redenen accrue râne (a, b). Mar de râne (b, e) wurdt trochjûn, ek al hy en de minimum gewicht fan 'e oerbleaune rânen, want it is read: de hoekpunten b en e hearre ta deselde komponint fan bosk ferbining F, dat is, as wy tafoegje oan F de râne (b, e), wurdt foarme syklus. Doe tafoege farnear (b, c), wurdt trochjûn reade râne (c, e), en dan d, e. Sa, rânen wurde tafoege sequentially (a, e), (c, d), (a, b), (b, c). Ut nihera optimale frame en bestiet út de orizjinele grafyk. Dus yn dit gefal it wurket in algoritme Kruskal. In foarbyld wurdt sjen litten.

De figuer toant in grafyk, dy't bestiet út twa oansletten komponinten. It fet linen wize op de optimale frame ribben (grien) konstruearre mei help fan de Kruskal algoritme.

De top byld jout de orizjinele grafyk, en de boaiem - in skelet fan minimaal gewicht, boud foar him troch mei de algoritme.

De folchoarder fan 'e tafoege ribben (1.6); (0,3), (2,6) of (2,6), (0,3) - is net wichtich; (3,4); (0,1), (1,6) of (1,6), (0,1), ek soarch (5,6).

Kruskal syn algoritme fynt praktyske tapassing, bygelyks, te optimalisearjen fan de pakking kommunikaasje, diken yn nijbouwyk bûtens Localities yn elk lân, likegoed as yn oare gefallen.