L'algoritme de Kruskal - la construcció d'un marc òptim

Al geòmetra principis del segle 19 Jakob Steiner de Berlín imposat la tasca de com connectar tres llogarets de manera que la seva longitud era el més curt. Més tard, es resumeix el problema: cal trobar un punt en un pla, la distància des d'ella a n altres punts van ser els més baixos. Al segle 20, es continua treballant en aquest tema. Es va decidir prendre alguns punts i connectar-los de tal manera que la distància entre ells era el més curt. Tot això és un cas especial del problema que s'està estudiant.

algoritme "cobdiciós"

l'algoritme de Kruskal es refereix a l'algorisme de "cobdiciós" (també anomenat gradient). L'essència dels - el premi més alt de cada pas. No sempre, els algoritmes de "cobdiciosos" proporcionen la millor solució al problema. Hi ha una teoria, mostrant que en la seva aplicació a les tasques específiques que donen la solució òptima. Aquesta és la teoria de la matroides. l'algoritme de Kruskal es refereix a aquest tipus de problemes.

Trobar un pes mínim en canal

Vist algoritme construeix un recompte de fotogrames òptima. El problema d'això és la següent. Dan no dirigits gràfic sense vores paral·leles i bucles, i el conjunt de vores es dóna la funció de pes w, que assigna el nombre a cada vora i - costella pes - w (i). El pes de cada subconjunt de la pluralitat de nervis és la suma dels pesos de les seves vores. Requerit per trobar l'esquelet d'un petit pes.

descripció

l'algoritme de Kruskal funciona. En primer lloc, totes les vores de la gràfica inicial estan disposades en ordre dels pesos ascendent. Inicialment, el marc no conté cap costella, sinó que inclou tots els vèrtexs. Després que el següent pas de l'algorisme a la part ja construïda de la carcassa, que és un bosc d'expansió, s'afegeix una vora. No es tria arbitràriament. Totes les vores de la gràfica, que no pertany al marc, poden ser cridats vermell i verd. La part superior de cada un de les vores vermells estan en la mateixa component de baix connectivitat bosc construcció, i les tapes verdes - diferent. Per tant, si s'agrega a la vora vermell, hi ha un cicle, i si el verd - com es va rebre després d'aquest pas els components de fusta connectades seran menys d'un. Per tant, la construcció resultant no pot afegir cap vora vermella, però qualsevol vora verda pot ser afegit per obtenir el bosc. I afegeix una vora verda amb un pes mínim. El resultat és un marc de pes mínim.

implementació

Denotar el bosc actual F. Es divideix el conjunt de vèrtexs en el camp de la connectivitat (la seva unió constitueix F, i que són disjunts). En ambdós vores dels vèrtexs de color vermell que es troben en una sola peça. Part (x) - la funció que per a cada vèrtex x retorna una part del nom, pertany x. Unite (x, i) - un procediment que construeix una nova partició, que consisteix en la combinació de parts de x i y i totes les altres parts. Sigui n - nombre d'arestes. Tots aquests conceptes s'inclouen en l'algoritme de Kruskal. implementació:

1. Organitzar totes les vores de la gràfica de la primera als pesos ascendents n-èsim. (Ai, Bi - i amb el nombre de tall àpex).

2. per a i = 1 a n faig.

3. x: = Part (ambdós inclosos).

4. i: = Part (bi).

5. Si x no és igual a i després Unite (x, y), per incloure amb el número vora F i.

exactitud

Sigui T - bastidor del gràfic original construït usant l'algoritme de Kruskal i S - seu marc arbitrari. Hem de demostrar que w (t) no és més gran que w (S).

Sigui M - pluralitat d'aletes S, P - una pluralitat d'aletes T. Si S no és igual a T, llavors hi ha una costella marc et T, no pertanyent a S. S. et confronten el cicle, es diu C. C eliminar de qualsevol és de vora, que pertany S. Obtenim un nou marc, pel fet que les vores i vèrtexs és el mateix. El seu pes no és més gran que w (S), ja que w (et) ja no w (és) en un algoritme de Kruskal poder. Aquesta operació (substitueixi costelles T S a costelles) es repeteix mentre rebre T. El pes de cada trama rebuda posterior no és més gran que el pes anterior, cosa que implica que w (T) no és més gran que w (S).

La robustesa de l'algorisme de Kruskal segueix del teorema de Rado-Edmonds en matroides.

Exemples d'aplicació de l'algoritme de Kruskal

gràfic Dan amb els nodes A, B, C, D, E i nervadures (a, b), (a, e), (b, c), (b, e), (c, d), (c, i) , (d, e). Els pesos de les vores es mostren a la taula i en la figura. Inicialment, bosc construcció F conté tots els vèrtexs de la gràfica i no conté cap costelles. Algorisme de Kruskal Primer Afegir costella (a, e), ja que el pes tenia el més baix, i els vèrtexs A i E estan en diferents components de connectivitat fusta F (costella (a, e) és de color verd), llavors el nervi (c, d), perquè que almenys aquest pes vora de les vores del gràfic, que no pertanyen a F, i és de color verd, a continuació, per les mateixes raons s'acumulen vora (a, b). Però es passa la vora (B, E), tot i que ell i el pes mínim de les vores restants, ja que és de color vermell: els vèrtexs B i E pertanyen a la mateixa component de connectivitat bosc F, és a dir, si afegim a F la vora (B, E), està formada cicle. Llavors afegit vora verda (b, c) de vora vermella, es passa (c, e) i, a continuació d, e. seqüencialment Per tant, s'afegeixen vores (a, e), (c, d), (a, b), (b, c). De nihera marc òptim i consisteix en el gràfic original. Així que en aquest cas s'opera un algoritme Kruskal. es mostra un exemple.

La figura mostra un gràfic, que consta de dos components connectats. Les línies en negreta indiquen les costelles òptimes de marc (verd) van construir utilitzant l'algoritme de Kruskal.

El quadre superior mostra el gràfic original, i la part inferior - un esquelet d'un pes mínim, construït per a ell mitjançant l'ús de l'algoritme.

La seqüència de les nervadures afegides (1,6); (0,3), (2,6) o (2,6), (0,3) - no és important; (3,4); (0,1), (1,6) o (1,6), (0,1), també tenir cura (5,6).

l'algoritme de Kruskal troba aplicació pràctica, per exemple, per optimitzar les comunicacions de les juntes, les carreteres en els nous habitatges localitats a cada país, així com en altres casos.