Fibonaĉi amaso
El Vikipedio, la libera enciklopedio
fonto: http://en.wikipedia.org/wiki/Fibonacci_heap
En komputika scienco, la Heap-Fibonacci estas nun amasa datumstrukturo konsistanta el kolekto de arboj. Ĝi havas pli bonan amortizitan rulan tempon ol duterma amaso. Fibonaĉi amasoj estis disvolvitaj de Michael L. Fredman kaj Robert E. Tarjan en 1984 kaj unua eldonita en scienca revuo en 1987. La nomo de Heap-Fibonacco devenas Fibonacci-nombroj kiuj estas uzataj en la rula tempa analitiko.
Trovi minimumo estas O(1) amortizita tempo. [1] Adiciaj Operacioj, malgrandiĝi ŝlosilon, kaj merge (unio) laboras en konstanta amortizita tempo. [2] . Operacioj forviŝas kaj forviŝas minimuman laboron en ho (log n) amortizita tempo [2] . Tio signifas, ke ekde malplenan datumstrukturon, ajna vico de operacioj de la unua grupo kaj b operacioj de la dua grupo prenus O(a + b log n) tempo. En duterma amaso tia vico de operacioj prenus O((a + b) log (n)) tempo. Heap-Fibonacco estu tiel bona ol duterma amaso kiam b estas asimptote pli malgranda ol.
Uzanta heap-Fibonacca por prioritataj vostoj plibonigas la asimptotan rulan tempon de algoritmoj gravas, kiel Dijkstra algoritmo por kalkuli la plej mallongan vojon inter du nodoj en grafeo.
Heap-Fibonacco estas kolekto de arbaj kontentigas la heap-minimuma proprieto, tio estas, la ŝlosilo de infano estas ĉiam pli granda ol aŭ egala al la ŝlosilon de la patro. Ĉi tio implicas ke la minimuma ŝlosilo estas ĉiam ĉe la radiko de unu el la arboj. Kompare kun dutermaj amasoj, la strukturo de Heap-Fibonaĉo estas pli fleksebla. La arboj ne havas preskribitan formon kaj en la ekstrema kazo la amaso povas havi ĉiun eron en aparta arbo. Tiu fleksebleco permesas iujn operaciojn esti ekzekutita en "mallaborema" maniero, prokrastante la laboro por postaj operacioj. Ekzemple kunfandi amasojn estas farita simple konkatenante la du listoj de arboj, kaj funkciado malpliiga ŝlosilo kelkfoje tranĉas nodo de lia patro kaj formas novan arbon.
Tamen en iu momento iu ordo devas esti prezentita al la amaso por atingi la deziratan rula tempo. Aparte, gradoj de verticoj (ĉi tie grado signifas la nombron de infanoj) subtenas sufiĉe malalta: ĉiu vertico havas gradon maksimume O (log n) kaj la grandeco de subarbo enradikiĝas nodon de k-grado estas almenaŭ Fk + 2, kie Fk estas la k-a fibonaĉa nombro. Tio estas atingita per la regulo, ke ni povas tranĉi maksimume unu infano de ĉiu ne-radika nodo. Kiam dua infano estas tranĉita, la nodo mem bezonas esti tranĉita de lia patro kaj iĝas la radikon de nova arbo (vidu Pruvo de gradaj baroj, sube). La nombro de arboj estas malkreskis en la operacio delete minimumo, kie arboj estas ligitaj kune.
Kiel rezulto de relajada strukturo, iuj operacioj povas preni longan tempon dum aliaj estas farita tre rapide. En la amortizita rultempo analizo ni ŝajnigas ke tre rapidaj operacioj preni iom pli longa ol ili reale fari. Tiu aldona tempo estas tiam poste subtrahita de la reala rula tempo de malrapidaj operacioj. La kvanto de tempo savis postan uzon estas mezurita je ĉiu momento por potenciala funkcio. La potencialo de heap-fibonaĉo estas donita per
Tiel, la radiko de ĉiu arbo kiel unu muro havas unu unuo de tempo stokita. Tiu unueco de tempo povas esti uzata poste por ligi tiun arbon kun alia arbo ĉe amortizita tempo 0. Ankaŭ, ĉiu markita nodo havas du ekzemplerojn de tempo stokita. Oni povas uzi por tranĉi la nodon de lia patro. Se ĉi tio okazas, la nodo igas radikon kaj la dua unuo de tempo restos stokitajn en ĝi kiel en ajna alia radiko.
Operacio trovu minimumon nun bagatela ĉar ni plenumas la sagon al la nodo enhavi ĝin. Ĝi ne ŝanĝas la potencialon de la amaso, sekve ambaŭ reala kaj amortizas koston estas konstanto. Kiel supre menciite, merge estas implementado simple konkatenante la listoj de arbaj radikoj de la du amasoj. Ĉi tiu povas esti farita en konstanta tempo kaj la potenciala ne ŝanĝas, kondukante denove al konstanta amortizita tempo.
Operacion adicii funkcias kreante novan amason kun unu ero kaj farante kunfandi. Ĉi prenas konstantan tempon, kaj la potencialaj kreskoj de unu, ĉar la nombro de arboj pliigas. La amortizita kosto estas tiel ankoraŭ konstanto.
Operacio ekstraktu minimumon (sama kiel delete minimumo) operacias en tri fazoj. Unue ni prenas la radikon enhavita la minimuma ero kaj forigi ĝin. Liaj filoj estos radikoj de novaj arboj. Se la nombro de infanoj estis d, ĝi prenas tempon O(d) por procesi ĉiujn novajn radikojn kaj la potencialaj kreskoj per d -1. Tial la amortizita rula tempo de ĉi tiu fazo estas O (d) = O (log n).
Tamen por kompletigi la ekstrakto minimuma operacio, ni bezonas ĝisdatigi la sagon al la radiko kun minimuma ŝlosilo. Bedaŭrinde povas esti ĝis n radikojn ni bezonas por kontroli. En la dua fazo ni do malpliigi la nombron de radikoj per sinsekve ligas kune radikoj de la sama grado. Kiam du radikoj u kaj v
havas la saman gradon, ni faras unu el ili estas infano de la alia
tiel, ke la tiu kun la plej malgranda ŝlosilo restas la radiko. Ĝia grado pliigos al oni. Ĉi ripetas ĝis ĉiu radiko havas malsaman grado. Trovi arbojn de la sama grado kompetente ni uzas aron de longo O (log n), en kiu ni gardas puntero al unu radiko de ĉiu grado. Kiam dua radiko estas trovita de la sama grado, la du estas kunigitaj kaj la tabelo estas ĝisdatigita. La reala rula tempo estas O (log n + m) kie m estas la kvanto de radikoj al la komenco de la dua fazo. Fine ni havos maksimume O (log n) radikoj (ĉar ĉiu havas malsaman grado). Tial la diferenco en la potenciala funkcio de antaŭ tiu fazo al post kiam ĝi estas: O (log n) - m, kaj la amortizita rula tempo estas tiam maksimume O (log n + m) + O (log n) - m = O (log n). Ĉar ni povas grimpi ĝis la ekzempleroj de potencialo stokitaj en inserción en ĉiu nodo de la konstanta faktoro en la O (m) parto de la reala kosto por tiu fazo.
En la tria fazo ni kontrolu ĉiu el la ceteraj radikoj kaj trovi la minimumo. Ĉi prenas O (logo n) tempo kaj la potenciala ne ŝanĝas. La ĝenerala amortizita rula tempo de ekstrakto minimuma estas do O (log n).
Fibonaĉi amaso de Figuro 1 post malkreskanta ŝlosilo de nodo 9 al 0. Ĉi nodo tiel kiel liaj du akcentitaj prapatroj estas tranĉitaj de la arbo enradikigite je 1 kaj metis kiel novaj radikoj.
Operacion malpliigo ŝlosilo
prenos la nodo, malpliigi la ŝlosilon kaj se la amaso propraĵo igas
seksperfortita (la nova tonalo estas pli malgranda ol la ŝlosilon de la
patro), la nodo estas tranĉita de lia patro. Se la patro ne estas radiko, ĝi estas markita. Se ĝi estis markita jam, ĝi tranĉas kiel bone kaj lia patro estas markita. Ni daŭrigas supren ĝis ni atingos ĉu la radiko aŭ senmarkajn nodo. En la procezo ni kreas iujn nombro, diri k, de novaj arboj. Ĉiu de ĉi tiuj novaj arboj krom eble la unua estis markita origine sed kiel radiko igos nemarkita. Unu nodo povas igi markita. Tial la potenciala malgrandiĝas per almenaŭ k - 2. La reala tempo por realigi la kortego estis O (k), do la amortizita rula tempo estas konstanta.
Fine, operacio delete povas esti realigita simple per malkreskanta la ŝlosilo de la elemento esti forviŝita al minus malfinio, tiel igante ĝin la minimumo de la tuta amaso. Tiam ni nomas ĉerpi minimuma eltiri ĝin. La amortizita rula tempo de ĉi tiu operacio estas O (log n).
por ĉiuj entjeroj 
, Kie 
. (Ni tiam havi 
, Kaj prenante la log al bazo 
de ambaŭ flankoj donas 
kiel postulis.)
Konsideri ajna nodo x ie en la havaĵo (x povas ne esti la radiko de unu el la ĉefaj arboj). Difini grandecon (x) esti la amplekso de la arbo enradikigite je x (la nombro de posteuloj de x, inkludante x mem). Ni pruvi per indukto sur la alteco de x (la longo de plej longa simpla vojo de x al posteulo folio), kiu grandeco (x) ≥ F d +2, kie d estas la grado de x.
Bazo kazo: Se x havas altecon 0, tiam d = 0, kaj grandeco (x) = 1 = F 2.
Indukta kazo: Supozi x havas pozitivan alteco kaj grado d> 0. Estu y 1, y 2, ..., y d esti la infanoj de x, indeksita laŭ la ordo de la tempoj ili plej lastatempe faris filoj de x (y 1 esti la plej fruaj kaj y d la lasta), kaj estu c 1 , c 2, ..., c d ilia respektivaj gradoj. Ni asertas ke c i ≥ i -2 por ĉiu mi kun 2 ≤ i ≤ d: Ĝuste antaŭ y mi iĝis infano de x, y 1, ..., y mi -1 jam filoj de x, kaj tiel x havis grado almenaŭ mi -1 tiame. Ekde arboj estas kombinitaj nur kiam la gradoj de iliaj radikoj estas egalaj, ĝi certe estis, ke y mi ankaŭ havis grado almenaŭ mi -1 tiutempe fariĝis knabo de x. De tiu tempo ĝis nun, y mi povas nur perdis maksimume unu infano (kiel garantiitaj de la markante procezo), kaj do ĝia nuna grado c mi estas almenaŭ i -2. Tiu pruvas la aserton.
Ekde la altecoj de ĉiuj y mi estas severe malpli ol tiu de x, oni povas apliki la indukta hipotezo al ili akiri grandeco (y mi) ≥ F c mi +2 ≥ F (i -2) +2 = F i. La nodoj x kaj y 1 ĉiu kontribui almenaŭ 1 ĝis grandeco (x), kaj tial ni havas
Al rutino indukto pruvas, ke
por ajna , Kiu donas la deziratan suba baro sur grandeco (x).
(*) Amortizita tempo
(**) Kun bagatela modifo stoki plia sagon al la minimuma ero
(***) Kie n estas la grandeco de la pli granda amaso
Trovi minimumo estas O(1) amortizita tempo. [1] Adiciaj Operacioj, malgrandiĝi ŝlosilon, kaj merge (unio) laboras en konstanta amortizita tempo. [2] . Operacioj forviŝas kaj forviŝas minimuman laboron en ho (log n) amortizita tempo [2] . Tio signifas, ke ekde malplenan datumstrukturon, ajna vico de operacioj de la unua grupo kaj b operacioj de la dua grupo prenus O(a + b log n) tempo. En duterma amaso tia vico de operacioj prenus O((a + b) log (n)) tempo. Heap-Fibonacco estu tiel bona ol duterma amaso kiam b estas asimptote pli malgranda ol.
Uzanta heap-Fibonacca por prioritataj vostoj plibonigas la asimptotan rulan tempon de algoritmoj gravas, kiel Dijkstra algoritmo por kalkuli la plej mallongan vojon inter du nodoj en grafeo.
Enhavo |
Strukturo
Figuro 1. Ekzemplo de Fibonaĉi amaso. Ĝi havas tri arboj de gradoj 0, 1 kaj 3. Tri verticoj estas markitaj (montrita en blua). Tial la potencialo de la amaso estas 9.
Heap-Fibonacco estas kolekto de arbaj kontentigas la heap-minimuma proprieto, tio estas, la ŝlosilo de infano estas ĉiam pli granda ol aŭ egala al la ŝlosilon de la patro. Ĉi tio implicas ke la minimuma ŝlosilo estas ĉiam ĉe la radiko de unu el la arboj. Kompare kun dutermaj amasoj, la strukturo de Heap-Fibonaĉo estas pli fleksebla. La arboj ne havas preskribitan formon kaj en la ekstrema kazo la amaso povas havi ĉiun eron en aparta arbo. Tiu fleksebleco permesas iujn operaciojn esti ekzekutita en "mallaborema" maniero, prokrastante la laboro por postaj operacioj. Ekzemple kunfandi amasojn estas farita simple konkatenante la du listoj de arboj, kaj funkciado malpliiga ŝlosilo kelkfoje tranĉas nodo de lia patro kaj formas novan arbon.
Tamen en iu momento iu ordo devas esti prezentita al la amaso por atingi la deziratan rula tempo. Aparte, gradoj de verticoj (ĉi tie grado signifas la nombron de infanoj) subtenas sufiĉe malalta: ĉiu vertico havas gradon maksimume O (log n) kaj la grandeco de subarbo enradikiĝas nodon de k-grado estas almenaŭ Fk + 2, kie Fk estas la k-a fibonaĉa nombro. Tio estas atingita per la regulo, ke ni povas tranĉi maksimume unu infano de ĉiu ne-radika nodo. Kiam dua infano estas tranĉita, la nodo mem bezonas esti tranĉita de lia patro kaj iĝas la radikon de nova arbo (vidu Pruvo de gradaj baroj, sube). La nombro de arboj estas malkreskis en la operacio delete minimumo, kie arboj estas ligitaj kune.
Kiel rezulto de relajada strukturo, iuj operacioj povas preni longan tempon dum aliaj estas farita tre rapide. En la amortizita rultempo analizo ni ŝajnigas ke tre rapidaj operacioj preni iom pli longa ol ili reale fari. Tiu aldona tempo estas tiam poste subtrahita de la reala rula tempo de malrapidaj operacioj. La kvanto de tempo savis postan uzon estas mezurita je ĉiu momento por potenciala funkcio. La potencialo de heap-fibonaĉo estas donita per
- Potencialo = t + 2 m
Tiel, la radiko de ĉiu arbo kiel unu muro havas unu unuo de tempo stokita. Tiu unueco de tempo povas esti uzata poste por ligi tiun arbon kun alia arbo ĉe amortizita tempo 0. Ankaŭ, ĉiu markita nodo havas du ekzemplerojn de tempo stokita. Oni povas uzi por tranĉi la nodon de lia patro. Se ĉi tio okazas, la nodo igas radikon kaj la dua unuo de tempo restos stokitajn en ĝi kiel en ajna alia radiko.
Apliko de operacioj
Por permesi rapidan forigon kaj kunmeton, la radikoj de ĉiuj arboj estas ligitaj per cirkuli, duoble ligitaj listoj. La infanoj de ĉiu vertico estas ankaŭ ligitaj uzante tia listo. Por ĉiu nodo, ni subtenos lian numeron de infanoj kaj ĉu la nodo estas markita. Plie ni subtenos sagon al la radiko enhavas la minimuma ŝlosilo.Operacio trovu minimumon nun bagatela ĉar ni plenumas la sagon al la nodo enhavi ĝin. Ĝi ne ŝanĝas la potencialon de la amaso, sekve ambaŭ reala kaj amortizas koston estas konstanto. Kiel supre menciite, merge estas implementado simple konkatenante la listoj de arbaj radikoj de la du amasoj. Ĉi tiu povas esti farita en konstanta tempo kaj la potenciala ne ŝanĝas, kondukante denove al konstanta amortizita tempo.
Operacion adicii funkcias kreante novan amason kun unu ero kaj farante kunfandi. Ĉi prenas konstantan tempon, kaj la potencialaj kreskoj de unu, ĉar la nombro de arboj pliigas. La amortizita kosto estas tiel ankoraŭ konstanto.
Fibonaĉi amaso de Figuro 1 post unua fazo de ekstrakto minimumo. Nodo kun ŝlosilo 1 (la minimuma) estis forviŝita kaj liaj filoj estis aldonitaj kiel apartaj arboj.
Fibonaĉi amaso de Figuro 1 post ekstrakto minimuma estas kompletigita. Unue, nodoj 3 kaj 6 estas ligitaj kune. Tiam la rezulto estas ligita kun arbo enradikigite ĉe vertico 2. Fine, la nova minimuma estas trovita.
En la tria fazo ni kontrolu ĉiu el la ceteraj radikoj kaj trovi la minimumo. Ĉi prenas O (logo n) tempo kaj la potenciala ne ŝanĝas. La ĝenerala amortizita rula tempo de ekstrakto minimuma estas do O (log n).
Fine, operacio delete povas esti realigita simple per malkreskanta la ŝlosilo de la elemento esti forviŝita al minus malfinio, tiel igante ĝin la minimumo de la tuta amaso. Tiam ni nomas ĉerpi minimuma eltiri ĝin. La amortizita rula tempo de ĉi tiu operacio estas O (log n).
Pruvo de grado baroj
La amortizita agado de Fibonaĉi amaso dependas de la grado (nombro de infanoj) de ajna arbo radiko esti O (log n), kie n estas la grandeco de la amaso. Ĉi tie ni montras ke la grandeco de la (sub) arbo enradikigite en ajna nodo x de grado d en la havaĵo devas havi grandecon almenaŭ F d +2, kie F k estas la k-a fibonaĉi nombro . La grado ligita sekvas el tio kaj la fakto (facile pruvita per indukto) kiu por ĉiuj entjeroj , Kie . (Ni tiam havi , Kaj prenante la log al bazo de ambaŭ flankoj donas kiel postulis.) Konsideri ajna nodo x ie en la havaĵo (x povas ne esti la radiko de unu el la ĉefaj arboj). Difini grandecon (x) esti la amplekso de la arbo enradikigite je x (la nombro de posteuloj de x, inkludante x mem). Ni pruvi per indukto sur la alteco de x (la longo de plej longa simpla vojo de x al posteulo folio), kiu grandeco (x) ≥ F d +2, kie d estas la grado de x.
Bazo kazo: Se x havas altecon 0, tiam d = 0, kaj grandeco (x) = 1 = F 2.
Indukta kazo: Supozi x havas pozitivan alteco kaj grado d> 0. Estu y 1, y 2, ..., y d esti la infanoj de x, indeksita laŭ la ordo de la tempoj ili plej lastatempe faris filoj de x (y 1 esti la plej fruaj kaj y d la lasta), kaj estu c 1 , c 2, ..., c d ilia respektivaj gradoj. Ni asertas ke c i ≥ i -2 por ĉiu mi kun 2 ≤ i ≤ d: Ĝuste antaŭ y mi iĝis infano de x, y 1, ..., y mi -1 jam filoj de x, kaj tiel x havis grado almenaŭ mi -1 tiame. Ekde arboj estas kombinitaj nur kiam la gradoj de iliaj radikoj estas egalaj, ĝi certe estis, ke y mi ankaŭ havis grado almenaŭ mi -1 tiutempe fariĝis knabo de x. De tiu tempo ĝis nun, y mi povas nur perdis maksimume unu infano (kiel garantiitaj de la markante procezo), kaj do ĝia nuna grado c mi estas almenaŭ i -2. Tiu pruvas la aserton.
Ekde la altecoj de ĉiuj y mi estas severe malpli ol tiu de x, oni povas apliki la indukta hipotezo al ili akiri grandeco (y mi) ≥ F c mi +2 ≥ F (i -2) +2 = F i. La nodoj x kaj y 1 ĉiu kontribui almenaŭ 1 ĝis grandeco (x), kaj tial ni havas
Al rutino indukto pruvas, ke
por ajna , Kiu donas la deziratan suba baro sur grandeco (x). Plej malbona kazo
Kvankam la tuta rultempo de vico de operacioj ekde la malplenan strukturo estas barita per la baroj donita pli supre, iuj (tre malmultaj) operacioj en la vico povas preni tre longa por kompletigi (en aparta forviŝi kaj forviŝi minimuma havas lineara rultempo en la plej malbona kazo). Tial Fibonacci amasoj kaj aliaj amortizita datumstrukturoj eble ne taŭga por reala tempo sistemoj . Eblas krei datumstrukturo kiu havas la saman plej malbona kazo agado kiel la Fibonacci amaso havas amortizita agado. [3] Tamen la rezultanta strukturo estas tre komplika, do ĝi ne estas utila en plej oportuna kazoj.Resumo de kurante fojoj
| Komuna Operacioj | Efekto | Unsorted Ligita Listo | Mem-balancadon duuma serĉarbo | Duuma amaso | Binoma amaso | Fibonaĉi amaso | Brodal vosto [3] | Emparejamiento amaso |
|---|---|---|---|---|---|---|---|---|
| enŝovu (datumojn, ŝlosilo) | Aldonas datumojn al la vosto, tagged kun ŝlosilo | O (1) | O (log n) | O (log n) | O (log n) | O (1) | O (1) | O (1) [2] |
| findMin () -> ŝlosilo, datumoj | Revenas ŝlosilo, datumoj respondante min-valoro ŝlosilon | O (n) | O (log n) aŭ O (1) (**) | O (1) | O (log n) [4] | O (1) [1] | O (1) | O (1) [2] |
| deleteMin () | Forigas datumoj respondante min-valoro ŝlosilon | O (n) | O (log n) | O (log n) | O (log n) | O (log n) * | O (log n) | O (log n) * [2] |
| forviŝi (nodo) | Forigas datumoj responda al donita ŝlosilo, donita sagon al la nodo esti forviŝita | O (1) | O (log n) | O (log n) | O (log n) | O (log n) * | O (log n) | O (log n) * [2] |
| decreaseKey (nodo) | Malgrandiĝas la ŝlosilon de nodo, donita sagon al la nodo esti modifitaj | O (1) | O (log n) | O (log n) | O (log n) | O (1) * | O (1) | Nekonata sed barita:  * [2] |
| merge (heap1, heap2) -> heap3 | Kunfandas du amasoj en tria | O (1) | O (m log (n + m)) | O (m + n) | O (log n) *** | O (1) | O (1) | O (1) [2] |
(**) Kun bagatela modifo stoki plia sagon al la minimuma ero
(***) Kie n estas la grandeco de la pli granda amaso
Nenhum comentário:
Postar um comentário