Kruskal algoritmo - la konstruo de optimuma kadron

En la frua 19-a jarcento geometriisto Jakob Steiner de Berlino metita la taskon kiel konekti tri vilaĝoj por ke ilia longo estis la plej mallonga. Poste, ĝi resumis la problemon: ĝi estas bezonata por trovi punkton en ebeno, la distanco de ĝi al n aliaj punktoj estis la plej malalta. En la 20-a jarcento, ĝi daŭre laboras pri tiu temo. Estis decidis preni kelkajn punktoj kaj konekti ilin en tia maniero, ke la distanco inter ili estis la plej mallonga. Ĉio estas speciala kazo de la problemo studita.

"Avidaj" algoritmo

Kruskal algoritmo rilatas al la "avidaj" algoritmo (ankaŭ nomita gradiento). La esenco de tiuj - la plej alta gajno sur ĉiu paŝo. Ne ĉiam, "avidaj" algoritmojn provizas la plej bona solvo por la problemo. Estas teorio, montrante ke en lia apliko al specifaj taskoj ili donas la optimuman solvon. Ĉi tiu estas la teorio de matroids. Kruskal algoritmo rilatas al tiaj problemoj.

Trovi minimuman kadavro pezo

Vidita algoritmo konstruas optimuman kadro grafo. La problemo de ĝi estas jena. Dan nedirektita grafeo sen paralelajn laterojn kaj ciklojn, kaj la aro de randoj estas donita la peza funkcio w, kiu asignas la nombron al ĉiu rando e - pezo ripo - w (kaj). La pezo de ĉiu subaro de la pluralidad de ripoj estas sumo de la pezoj de ĝiaj randoj. Bezonata por trovi la skeleton de malgranda pezo.

priskribo

Kruskal algoritmo laboras. Unue, ĉiuj randoj de la komenca grafeo estas aranĝitaj en supreniranta ordon de la pezoj. Komence, la kadro ne enhavas ajnan ripoj sed inkluzivas ĉiujn verticojn. Post la sekva paŝo de la algoritmo al la jam konstruita parto de la kadavro, kiu estas ampleksanta arbaro, unu rando estas aldonita. Oni ne elektis arbitre. Ĉiuj lateroj de la grafikaĵo, ne apartenanta al la kadro, povas esti nomata ruĝa kaj verda. Supre ruĝaj randoj estas en la sama komponento konstruataj arbaro conectividad kaj la verdaj suproj - malsamaj. Tial, se vi aldonas al la ruĝa rando, estas ciklo, kaj se la verda - kiel ricevis post tiu paŝo la ligno koneksaj komponantoj estos malpli ol unu. Tiel, la rezultanta konstruo ne povas aldoni jam ruĝa rando, sed neniun verdan rando povas esti aldonita por akiri la arbaro. Kaj aldonas verda rando kun minimuma pezo. La rezulto estas kadro de minimuma pezo.

efektivigo

Signifi la aktualan arbaro F. Ĝi dividas la aron de verticoj en la kampo de conectividad (ilia unio formoj F, kaj ili estas disa). Ĉe ambaŭ randoj de la ruĝaj verticoj kuŝas en unu peco. Parto (x) - la funkcio kiu por ĉiu vertico x revenas parton de la nomo, ĝi apartenas x. Unite (x, y) - proceduro kiu konstruas novan vando, kiu konsistas de kombinado partoj de x kaj kaj kaj ĉiuj aliaj partoj. Lasu n - nombro de randoj. Ĉiuj ĉi tiuj konceptoj estas inkluzivita en Kruskal algoritmo. efektivigo:

1. Aranĝi ĉiuj randoj de la grafeo de la 1-a ĝis na suprenira pezoj. (Aj, bi - i kun ápice rando nombro).

2. por mi = 1 al n fari.

3. x: = Parto (ai).

4. y: = Parto (bi).

5. Se x ne egalas y tiam Unite (x, kaj), por inkludi la rando F i numeron.

ĝustecon

Lasu T - kadro de la originala grafikaĵo konstruita uzante la Kruskal algoritmo kaj S - ĝia arbitra kadro. Ni devas pruvi, ke w (T) estas ne pli granda ol c (S).

Estu M - plureco de naĝiloj S, P - pluralidad de naĝiloj T. Se S estas ne egala al T, tiam estas kadro ripo et T, ne apartenanta al S. S. et adjoin la ciklo, ĝi nomiĝas C. C forigi de ajna rando es, apartenanta S. Ni akiras nova kadro, ĉar la randoj kaj verticoj estas la samaj. Lia pezo ne estas pli granda ol c (S), pro tio w (et) ne plu w (es) en potenco Kruskal algoritmo. Tiu operacio (anstataŭaĵo T S ripoj sur ripoj) estos ripetita dum ricevi T. La pezo de ĉiu posta ricevita kadro ne estas pli granda ol la antaŭa pezo, kiu implicu ke w (T) estas ne pli granda ol c (S).

La robustez de Kruskal algoritmo sekvas de la teoremo de Rado-Edmonds sur matroids.

Apliko Ekzemploj Kruskal algoritmo

Dan grafeo kun nodoj a, b, c, d, e kaj ripoj (a, b), (a, e), (b, c), (b, e), (c, d), (c, d) , (d, e). La pezoj de randoj estas montritaj en la tabelo kaj en la figuro. Komence, konstruo arbaro F enhavas ĉiujn verticojn de la grafeo kaj ne enhavas ajnan ripoj. Algoritmo Kruskal unua aldonu ripo (a, e), ĉar la pezo havis la plej malalta, kaj la verticoj a kaj e estas en malsamaj komponantoj ligno conectividad F (ripo (a, e) estas verda), tiam la ripo (c, d), ĉar ke almenaŭ ĉi rando pezo de grafeo randoj, ne apartenanta al F, kaj estas verdaj, poste pro la samaj kialoj accrue randon (a, b). Sed la rando (b, d) estas pasita, kvankam li kaj la minimuma pezo de la ceteraj randoj, ĉar ĝi estas ruĝa: la verticoj b kaj e apartenas al la sama komponanto de arbaro conectividad F, tio estas, se ni aldonas al F la rando (b, e), estas formita ciklo. Poste aldonis verdan randon (b, c), estas pasita ruĝa rando (c, d), kaj tiam d, kaj. Tiel, randoj estas aldonitaj sinsekve (a, e), (c, d), (a, b), (b, c). El nihera optimuma kadro kaj konsistas el la origina grafeo. Do en ĉi tiu kazo ĝi funkcias algoritmo Kruskal. Ekzemplo estas montrata.

La figuro montras grafikaĵon, kiu konsistas el du koneksaj komponantoj. La aŭdaca linioj indiki la optimuman kadro ripoj (verda) konstruita uzante la Kruskal algoritmo.

La supro bildo montras la originalan grafikaĵon kaj malsupre - skeleton de minimuma pezo, konstruita por li uzante la algoritmo.

La sekvenco de la aldonitaj ripoj (1.6); (0,3), (2,6) aŭ (2,6), (0,3) - ne gravas; (3,4); (0,1), (1,6) aŭ (1,6), (0,1), ankaŭ gravas (5,6).

Kruskal algoritmo trovas praktikan aplikon, ekzemple, por optimizar la gasket komunikado, vojoj en novaj loĝejaj kvartaloj lokoj en ĉiu lando, kaj ankaŭ en aliaj kazoj.