Minimuma generanta arbo: Malsamoj inter versioj

{{polurinda movu|Minimuma generantabranĉanta arbo}}

[[Dosiero:Minimum spanning tree.svg|thumb|300px|right|La minimuma generantabranĉanta arbo de ebena grafeo. Ĉiu randobranĉo estas (etikedita, markita, markita) kun ĝia pezo, kiu jenĉ malglatetie egalamalfajne alegalas ĝiasian longolongon.]]

Donita koneksa, sendirekta grafeo, [[Generanta arbo|(naskanta, generanta)branĉanta arbo]] de (tiu, ke, kiu) (grafikaĵo, grafeo) estas subgrafeo kiu estas arbo kaj trakonektaskunkonektas ĉiujĉiujn verticoj kuneverticojn. Sola (grafikaĵo, grafeo) povas havi multajmultajn malsamamalsamajn (naskanta,branĉantajn generanta) (arboj, arbas)arbojn. Ni povas ankaŭ asigni ''pezopezon'' al ĉiu rando, kiu estas nombro (figuranta, prezentanta) kiel _unfavorable_ ĝi estas, kaj uzi ĉition tiu alpor asigni pezopezon al (naskanta, generanta)branĉanta arbo per komputantakomputi la (sumo, sumi)sumon de la (pezoj, pezas) de la randojbranĉoj en (tiu, ke, kiu) (naskanta, generanta)branĉanta arbo. '''minimumaMinimuma generantabranĉanta arbo''' aŭ '''minimumaminimum-peza pezo (naskanta, generanta)branĉanta arbo''' estas tiam (naskanta, generanta)branĉanta arbo kun pezo malpli ol aŭ egala al la pezo de ĉiu alia (naskanta, generanta)branĉanta arbo. Pli ĝenerale, (ĉiu, iu) ajn sendirekta grafeo havas '''minimumominimuman (naskanta, generanta)branĉantan arbaroarbaron'''.

Unu ekzemplo devusestus estikabla kablotelevid-kompanio TVdemetanta kompania kuŝiganta kablokablon al nova najbaraĵonajbarejo. Se ĝi estas limigita al burysubterigi la kablokablon nur laŭ certaj vojoj, tiam tie devus esti (grafikaĵo, grafeo)n (figuranta,prezentantan prezentanta)tion kiuj punktoj estas koneksakoneksaj per tiuj vojoj. IuIuj deel tiuj vojoj povus esti pli multekostamultekostaj, ĉar ili estas pli longalongaj, aŭ postuli la kablo alkablon esti enfosita pli profundaprofunde; ĉi tiuj vojoj devus esti (prezentita, prezentis)prezentitaj per randoj kun pli grandagrandaj (pezoj, pezas). ''(naskanta, generanta)Branĉanta arbo'' por (tiu, ke, kiu) (grafikaĵo, grafeo) devus esti subaro de tiuj vojoj (tiu, ke, kiu)kiuj havas neneniujn (cikloj, ciklas)ciklojn sed ankoraŭ trakonektas al ĉiu domo. Tie povus esti kelkaj (naskanta,branĉantaj generanta) (arboj, arbas) eblaeblaj. ''minimumaMinimuma generantabranĉanta arbo'' devus esti unu kun la (plej malalta, plej suba) tuteca kostikosto.

En la okazokazo se de egalgajno (kravato, ligi?), tie povitapovus esti kelkaj minimumaj generantajbranĉantaj arboj; en apartaprecipe, se ĉiuj (pezoj, pezas) estas la samasamas, ĉiu (naskanta, generanta)branĉanta arbo estas minimumo. Tamen, unu teoremajteoremo ŝtatoj (tiudiras, ke, kiu) se ĉiu randobranĉo havas klaraklaran pezopezon, la minimuma generantabranĉanta arbo estas unika.{{citon}} Ĉi tiuTio estas vera en multaj realismarealismaj (situacioj, situacias), kiel la unutiu pli supre, kie ĝi'sestas malverŝajne (ĉiu,ke iu)iuj ajn du vojoj havihavas ''akurateĝuste'' la samasaman kostikoston. Ĉi tiu ĝeneraligasankaŭ ĝeneraliĝas al (naskanta,branĉantaj generanta) (arbaroj, arbaras, silvoj, silvas) kiel bone.

Minimuma generantabranĉanta arbo estas fakte la minimumominimum-kostikostaj subgrafeaj trakonektantaj ĉiuj verticoj, ekdeĉar (subgrafeoj, subgrafeas) enhavanta (cikloj,enhavantaj ciklas)ciklojn bezonenecese havihavas pli tuteca pezo.

== (Algoritmoj, Algoritmas) ==

La unua algoritmo por trovantatrovi minimumaminimuman generantabranĉantan arboarbon estis ellaborita perfar Ĉeĥa sciencisto _Otakar_Otakar Borů_vka_vka en [[1926]] (vidi _Boruvka_'svidu [[algoritmo de Boruvka]]). Ĝia celo estis kompetenta elektra _coverage_ de [[Bohemio]]. Estas nun du (algoritmoj, algoritmas) kutime uzitauzataj, _Prim_'sl algoritmo de Prim kaj _Kruskal_'sla algoritmo de Kruskal. Ĉiuj tri estas [[Avara algoritmo|avaraj algoritmoj]] (tiu, ke, kiu)kiuj kurirulas en polinoma tempo, (do, tiel) la problemo detrovi trovantatiajn tia (arboj, arbas)arbojn estas en '''[[P (komplekseco)|P]]'''.

La plej rapida minimuma generantabranĉanta arba algoritmo alĝis datonun estis ellaborita perfar _Bernard_Bernard _Chazelle_Chazelle, kaj bazita sur tiu de Borů_vka_'svka. Ĝia (kuro, kurante, rulante) temporultempo estas ''[[Granda O skribmaniero|O]]''(''m'' &α;(''m'',''n'')), kie ''m'' estas la nombro de randoj, ''n'' (ligas, referas) alestas la nombro de verticoj kaj α estas la klasika (funkcionalo, funkcia) inverso de la [[Akermana funkcio]]. La funkcio α kreskas ege malfrue, tiel ke por ĉiuj praktikapraktikaj (celoj, celas) ĝi (majo, povas) esti konsiderata konstanto ne pli granda ol 4; tial _Chazelle_'sla algoritmo de Chazelle prenas tre proksime al ''[[Granda O skribmaniero|O]]''(''m'') tempotempon.

KioKiu estas la plej rapida ebla algoritmo por ĉi tiu problemo? Tio estas unu deel la plej malnovamalnovaj (malfermi,malfermitaj malfermita) (demandoj, demandas) en komputiko. Estas klare lineara suba baro, ekdeĉar ni devas almenaŭ ekzameni ĉiuĉiujn (pezoj, pezas)pezojn. Se la rando (-pezoj, pezas) estas (entjeroj, entjeras) kun barita malmulta longo, tiam (determinisma, determina)j (algoritmoj, algoritmas) estas sciatasciataj kun lineara (kuro, kurante, rulante) temporultempo, ''O''(''m''). Por ĝeneralaĝeneralaj (pezoj, pezas), [[Hazardigita algoritmo|hazardigitaj algoritmoj]] estas sciata (tiu, ke,kies kiu)atendita kurirultempo enestas lineara atendis tempo.

Ĉu tie ekzistas (determinisma, determina) algoritmo kun lineara (kuro, kurante, rulante) temporultempo por ĝeneralaĝeneralaj (pezoj, pezas) estas ankoraŭ (malfermi, malfermita) demando. Tamen, Set _Pettie_Pettie kaj _Vijaya_Vijaya _Ramachandran_Ramachandran havi fundamenti verŝajne (optima, optimala)n (determinisma, determina)n minimumaminimuman generantabranĉantan arbaarban algoritmoalgoritmon, la komputa komplekseco kiesde kiu estas nekonatonekonata. [http://portal.acm.org/citation.cfm?doid=505241.505243]

Pli ĵuse, esploriesploro havasfokusas fokusitasuper sur solvantasolvi la minimumaminimuman generantabranĉantan arbaarban problemoproblemon en alte _parallelized_paraleligita maniero. Ekzemple, la _pragmatic_pragmata (2003) papero "Rapida Komunigita-Memoro (Algoritmoj, Algoritmas) por KomputantaKomputi la MinimumoMinimuman (Naskanta, Generanta)Generantan ArbaroArbaron de _Sparse_Sparse (Grafikaĵoj, Grafeoj)" per Davido A. pli malbona kaj _Guojing_Guojing _Cong_Cong demonstracias algoritmo (tiu, kealgoritmon, kiu) povas komputi _MSTs_MSTs 5 (tempoj, tempas)-oble pli rapidarapide sur 8 (proceziloj, procezas, traktiloj, traktas, procesoroj, procesoras, datumtraktiloj, datumtraktas) ol (optimigis, optimumigita) (sekvenca (vica, sinsekva) algoritmo.[http://www.cs.unm.edu/~treport/tr/03-12/MST-bader.pdf] Tipe, paralelo (algoritmoj, algoritmas) estas bazitabazitaj sur _Boruvka_'sla algoritmo de Boruvka — _Prim_'sla algoritmoj de Prim kaj aparte _Kruskal_'sde algoritmoKruskal ne (krusto, skalo) kiel bone al aldona (proceziloj, procezas, traktiloj, traktas,aldonaj procesoroj, procesoras, datumtraktiloj, datumtraktas).

AliaAliaj specialigitaspecialigitaj (algoritmoj, algoritmas) havijam estas (dizajnita, desegnita)j por komputantajkomputi minimumajminimumajn generantajgenerantajn arbojarbojn de (grafikaĵo, grafeo) (do, tiel) granda (tiugrandaj, ke, kiu) la plejparto deel ĝiili devas esti butikitastorita sur disko ajn (tempoj, tempas). Ĉi tiuj ''ekstera memoro'' (algoritmoj, algoritmas), ekzemple kiel priskribispriskribitaj en "Inĝenierada Ekstera Memora Minimumo (Naskanta, Generanta)Branĉanta Arba Algoritmo" perfar Roma _Dementiev_Dementiev _et_ _al_k.a.,[http://citeseer.ist.psu.edu/dementiev04engineering.html] povas operacii kieltiel malgranda kiel 2 alĝis 5 (tempoj, tempas)-oble pli malfrua ol tradicia en-memora algoritmo; ili pretendi (tiupretendas, ke, kiu)"problemoj de "(masiva, peza) minimuma generanta arbo (problemoj, problemas) enspacanta kelkajkelkajn (fiksitaj diskoj, diskaparatoj)n povas esti solvitasolvitaj tranoktitranokte sur (PC, Persona komputilo)." Ili fidibezonas kompetentakompetentan eksteraeksteran memoromemoron (speco, ordigo) (algoritmoj, algoritmas) kaj sur (grafikaĵo, grafeo) kuntiraj teknikoj por reduktanta la (grafikaĵa, grafea, grafa)n ampleksoamplekson kompetente.

==_MST_ MST sur plenaj grafeoj ==

Ĝi havasJam estas montrita perfar J. Miĥaelo _Steele_Steele bazitabazite sur laboro perfar A. Sinjora Friso (tiu, ke, kiu) donitadonite [[plena grafeo]] sur ''n'' verticoj, kun rando (-pezoj, pezas) elektitaelektitaj de kontinua hazarda distribuo <math>f</math> tia (tiu, ke, kiu) <math>f'(0) > 0</math>, kiel ''n'' (manieroj, proksimiĝoj)proksimiĝas [[Infinito|malfinio]] la amplekso de la _MST_MST (manieroj, proksimiĝoj) <math>\zeta(3)/f'(0)</math>, kie <math>\zeta</math> estas la [[Rimana ζ funkcio]].

Por uniformouniformaj hazardahazardaj (pezoj, pezas) en <math>[0,1]</math>, la akurataĝusta atendisatendita amplekso de la minimuma generantabranĉanta arbo havas estas komputita por malgrandaj plenaj grafeoj.

== RilatantaRilataj (problemoj, problemas) ==

RilatantaRilata (grafikaĵo, grafeo) estas la [[K-minimuma generantabranĉanta arbo|''k''-minimuma generanta arbo]] (''k''-_MST_) kiu estas la arbo (tiu, ke, kiu) (naskas, generas) iuiun subarosubaron de ''k'' verticoj en la (grafikaĵo, grafeo) kun minimuma pezo.

Geometrie rilatantarilata problemo estas la Eŭklida minimuma generantabranĉanta arbo.

* Jozefo _Kruskal_Kruskal

* [http://citeseer.ist.psu.edu/nesetril00otakar.html _Otakar_Otakar _Boruvka_Boruvka sur Minimumo (Naskanta, Generanta)Branĉanta Arba Problemo (traduko de la ambaŭ 1926 (paperoj, paperas)de 1926, (komentoj, komentas), historio) (2000) _Jaroslav_Jaroslav _Nesetril_Nesetril, Evo _Milková_Milková, _Helena_Helena _Nesetrilová_Nesetrilová] (sekcio 7 donas lialian algoritmoalgoritmon, kiu (aspektas, aspektoj,kiel rigardas)mikso ŝatiinter krucitiu interde _Prim_'sPrim kaj _Kruskal_'stiu de Kruskal)

* [http://www.cs.princeton.edu/~chazelle/pubs.html A MinimumoMinimuma (Naskanta, Generanta)Branĉanta Arba Algoritmo kun Inverso-_Ackermann_Ackermann-a Tipa Komplekseco], _Bernard_Bernard _Chazelle_Chazelle, 1999

* Tomaso H. Cormen-a, Karlo E. _Leiserson_Leiserson, _Ronald_Ronald L. _Rivest_Rivest, kaj _Clifford_Clifford Stein-a. ''Enkonduko al (Algoritmoj, Algoritmas)'', (Sekundo, Dua) RedakcioRedakto. _MIT_ PremiMIT Press kaj _McGraw_McGraw-MontetoHill, 2001. ISBN 0262032937. Ĉapitro 23: Minimumo (Naskanta,Generantaj Generanta) (Arboj, Arbas), _pp_pp.561&ndash;579.