Algoritmu Kruskal - l-kostruzzjoni ta 'qafas aħjar

Fis-geometer bidu tas-seklu 19 Jakob Steiner minn Berlin tistabbilixxi l-kompitu ta 'kif jgħaqqdu tliet irħula b'tali mod li t-tul tagħhom kien l-iqsar. Aktar tard, huwa fil-qosor il-problema: huwa meħtieġ biex isibu punt fi pjan, id-distanza minnha Li n punti l-oħra kienu l-aktar baxx. Fis-seklu 20, hija tkompli taħdem fuq dan is-suġġett. Ġie deċiż li tieħu ftit punti u qabbad lilhom b'tali mod li d-distanza bejniethom kienet l-iqsar. Dan kollu huwa każ speċjali tal-problema qed jiġu studjati.

"Greedy" Algoriżmu

algoritmu Kruskal jirreferi għall- "greedy" Algoriżmu (imsejħa wkoll gradjent). L-essenza ta 'dawk - l-ogħla rebħa fuq kull pass. Mhux dejjem, "greedy" algoritmi jipprovdu l-aħjar soluzzjoni għall-problema. Hemm teorija, li turi li fl-applikazzjoni tagħhom għal kompiti speċifiċi li jagħtu s-soluzzjoni ottimali. Dan huwa l-teorija ta 'matroids. algoritmu Kruskal jirreferi għal problemi bħal dawn.

Sib piż minimu tal-karkassa

algoritmu Viewed constructs l-għadd qafas ottimali. Il-problema ta 'dan huwa kif ġej. Dan undirected graff mingħajr truf paralleli u loops, u s-sett tat-trufijiet tingħata l-funzjoni piż w, li tassenja n-numru għal kull tarf e - kustilja piż - w (e). Il-piż ta 'kull subsett tal-pluralità ta' kustilji hija s-somma tal-piżijiet tat-trufijiet tagħha. Meħtieġa biex isibu l-iskeletru ta 'piż żgħir.

deskrizzjoni

algoritmu Kruskal s xogħlijiet. L-ewwel, truf kollha tal-graff inizjali huma rranġati axxendenti ordni tal-piżijiet. Inizjalment, il-qafas ma fiha ebda kustilji iżda jinkludi vertiċi kollha. Wara l-pass li jmiss tal-algoritmu għall-parti diġa mibni tal-karkassa, li tkun foresta jifirxu, tarf wieħed huwa miżjud. Mhuwiex magħżul b'mod arbitrarju. Il-truf tal-graff, li ma jappartjenux għall-qafas, jistgħu jiġu msejħa aħmar u aħdar. Il-quċċata ta 'kull truf aħmar huma fl-istess komponent taħt konnettività kostruzzjoni tal-foresti, u l-uċuħ aħdar - differenti. Għalhekk, jekk inti żid mat-tarf aħmar, hemm ċiklu, u jekk l-aħdar - kif akkwistat wara dan il-pass l-komponenti injam konnessi tkun inqas minn wieħed. Għalhekk, il-kostruzzjoni jirriżultaw ma jistgħux iżidu l-ebda tarf aħmar, iżda kwalunkwe tarf aħdar jistgħu jiġu miżjuda biex jiksbu l-foresti. U żżid tarf aħdar bil-piż minimu. Ir-riżultat huwa qafas ta 'piż minimu.

implimentazzjoni

Jindikaw l-foresti attwali F. Hija taqsam is-sett ta 'vertiċi fil-qasam tal-konnettività (forom unjoni tagħhom F, u dawn huma disjoint). Fiż-żewġ truf tal-punti aħmar dawn jaqgħu f'biċċa waħda. Parti (x) - il-funzjoni li għal kull vertiċi x prospetti porzjon tal-isem, li tappartjeni x. Unite (x, y) - proċedura li tibni partizzjoni ġdida, li tikkonsisti tgħaqqad partijiet ta 'xuy u l-partijiet l-oħra. Ħalli n - numru ta 'truf. Kollha dawn il-kunċetti huma inklużi fil algoritmu Kruskal s. implimentazzjoni:

1. Irranġa l-truf tal-graff mill-1 sal-piżijiet axxendenti-n th. (Ai, bi - i bin-numru tarf quċċata).

2. għal i = 1 sa n tagħmel.

3. x: = Parti (ai).

4. y: = Parti (bi).

5. Jekk x ma tkunx daqs y allura Unite (x, y), li tinkludi n-numru tarf F i.

korrettezza

Ħalli T - qafas ta 'l-graff oriġinali mibni bl-użu algoritmu Kruskal u S - qafas arbitrarja tagħha. Irridu jipprova li w (T) ma tkunx akbar minn w (S).

Ħalli - pluralità ta 'xewk S, P - pluralità tax-xewka T. Jekk S mhuwiex ugwali għal T, allura hemm qafas kustilja et T, li ma jappartjenux għall S. S. et ħdejn iċ-ċiklu, huwa msejjaħ C. Ċ tneħħi minn kwalunkwe es tarf, li jappartjenu S. Aħna jiksbu qafas ġdid, minħabba li l-truf u l-punti huwa l-istess. piż tagħha ma tkunx akbar minn w (S), peress w (et) m'għadux w (i) fil-poter Kruskal algoritmu. Din l-operazzjoni (sostitut kustilji T S fuq kustilji) se jiġi ripetut sakemm jirċievu T. Il-piż ta 'kull qafas riċevuti sussegwenti ma tkunx akbar mill-piż ta' qabel, li jimplika li w (T) ma tkunx akbar minn w (S).

Ir-robustezza ta algoritmu Kruskal ssegwi mill-teorema ta Rado-Edmonds fuq matroids.

Applikazzjoni Eżempji Kruskal algoritmu

Dan graff ma 'punti strateġiċi ta', b, c, d, e u kustilji (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) (d, e). Il-piżijiet tat-trufijiet huma murija fit-tabella u fil-figura. Inizjalment, il-kostruzzjoni tal-foresti F fiha l-punti ta 'l-graff u ma fiha ebda kustilji. Algoritmu Kruskal ewwel żid kustilja (a, e), peress li l-piż kienet l-aktar baxx, u l-punti ta 'u l-e huma fil-komponenti differenti konnettività injam F (kustilja (a, e) hija ħadra), allura l-kustilja (c, d), minħabba li mill-inqas dan il-piż tarf wieħed mix-xfar graff, li ma jappartjenux għall-F, u huwa aħdar, imbagħad għall-istess raġunijiet jakkumulaw tarf (a, b). Iżda l-tarf (b, e) ikun għadda, anke jekk hu u l-piż minimu tat-truf li jifdal, minħabba li huwa aħmar: l-punti b ue jappartjenu għall-istess komponent ta 'konnettività foresta F, jiġifieri, jekk aħna żid sa F-tarf (b, e), hija furmata ċiklu. Imbagħad miżjud tarf aħdar (b, c) tarf aħmar, hija mgħoddija (c, e), u mbagħad d-e. sekwenzjalment Għalhekk, truf huma miżjuda (a, e), (c, d), (a, b), (b, c). Mill qafas ottimali nihera u tikkonsisti tal-graff oriġinali. Allura f'dan il-każ hija topera algoritmu Kruskal. Eżempju huwa muri.

Il-figura turi graff, li jikkonsisti f'żewġ komponenti konnessi. Il-linji skuri jindikaw il-ottimali kustilji qafas (aħdar) mibnija bl-użu algoritmu Kruskal.

L-istampa ta 'fuq turi l-graff oriġinali, u l-qiegħ - iskeletru ta' piż minimu, mibnija għalih billi tuża l-algoritmu.

Is-sekwenza tal-kustilji miżjud (1.6); (0,3), (2,6) jew (2,6), (0,3) - mhix importanti; (3,4); (0,1), (1,6) jew (1,6), (0,1), il-kura wkoll (5,6).

algoritmu Kruskal isib applikazzjoni prattika, per eżempju, biex jottimizzaw il-komunikazzjonijiet siegla, toroq fil-lokalitajiet ġodda estates tad-djar f'kull pajjiż, kif ukoll f'każijiet oħra.