Come implementare l'algoritmo di Prim con un mucchio di Fibonacci?

Question

di Prim algoritmo e so che la sua attuazione, ma sempre ho saltare una parte che Vorrei chiedere ora. È stato scritto che l'attuazione algoritmo di Prim con Fibonacci heap è O(E + V log(V)) e la mia domanda è:

• quello che è un mucchio di Fibonacci in breve?
• Come si realizza? E
• Come è possibile implementare l'algoritmo di Prim con un mucchio di Fibonacci?

Answer 1

Un Fibonacci heap è una coda di priorità piuttosto complesso che ha eccellenti amoritzed comportamento asintotico in tutte le sue operazioni - l'inserimento, find-min, e la diminuzione-chiave tutti corrono a O (1) ammortizzato tempo, mentre correre di eliminazione e l'estratto-min in ammortizzato O (lg n). Se volete un buon riferimento su questo argomento, vi consiglio vivamente di prendere una copia di "Introduzione agli algoritmi, 2nd Edition" di CLRS e letto il capitolo su di esso. E 'straordinariamente ben scritto e molto illustrativo. Il documento originale su Fibonacci cumuli di Fredman e Tarjan è disponibile online, e si potrebbe desiderare di check it out. E 'denso, ma dà una buona trattamento del materiale.

Se vuoi vedere l'implementazione di cumuli di Fibonacci e l'algoritmo di Prim, devo dare una spina spudorato per i miei implementazioni:

1. mia implementazione di un mucchio di Fibonacci.
2. mia implementazione dell'algoritmo di Prim utilizzando un mucchio di Fibonacci.

I commenti in entrambe queste implementazioni dovrebbe fornire una descrizione abbastanza buona di come funzionano; fatemi sapere se c'è qualcosa che posso fare per chiarire!

Answer 2

L'algoritmo di Prim selezionare il bordo con il peso più basso tra il gruppo di vortici già selezionati e il resto dei vortici.
Quindi, per implementare l'algoritmo di Prim, è necessario un mucchio minimo. Ogni volta che si seleziona un vantaggio si aggiunge il nuovo vortice al gruppo dei vortici hai già scelto, e tutti i suoi bordi adiacenti andare nel mucchio.
Poi si sceglie il bordo con il valore minimo di nuovo dal mucchio.

Quindi i tempi che otteniamo sono:
Fibonacci:
bordo minima scelta = O (momento della rimozione di minimo) = O (log (E)) = O (log (V))
Inserimento bordi mucchio = O (tempo di inserire l'elemento ad mucchio) = 1

mucchio

Min:
bordo minima scelta = O (momento della rimozione minima dalla heap) = O (log (E)) = O (log (V))
Inserimento bordi mucchio = O (tempo di inserire l'elemento ad mucchio) = O (log (E)) = O (log (V))

(Si ricordi che E = ~ V ^ 2 ... quindi il login (E) == log (V ^ 2) == 2log (V) = O (log (V))

Quindi, in totale si hanno inserti E, e choosings minimi V (E 'un albero, alla fine).

Quindi, in Min mucchio si otterrà:

O (Vlog (V) + Elog (V)) == O (Elog (V))

E nel mucchio di Fibonacci si otterrà:

O (Vlog (V) + E)

Answer 3

ho implementato utilizzando Fibonacci Dijkstra cumuli a pochi anni fa, e il problema è abbastanza simile. Fondamentalmente, il vantaggio di cumuli di Fibonacci è che rende trovare il minimo di un insieme un'operazione costante; Ecco, questo è molto appropriato per Prim e Dijkstra, dove ad ogni passo si deve eseguire questa operazione.

Perché è bene

La complessità di questi algoritmi utilizzando un heap binomiale (che è il modo in più "standard") è O (E * log V), perché - più o meno - si cercherà ogni bordo (E), e per ciascuno di essi si sarà o aggiungere il nuovo vertice al binomio mucchio (log V) o diminuire la sua chiave (log V), e poi a trovare il minimo del mucchio (un altro ceppo V).

Al contrario, quando si utilizza un heap di Fibonacci il costo di inserimento di un vertice o diminuendo la sua chiave nella vostra mucchio è costante in modo da avere solo O (E) per questo. MA eliminazione di un vertice è O (log V), così poiché alla fine sarà rimosso ogni vertice che aggiunge un O (V * log V), per un totale O (E + V * log V).

Quindi, se il grafico è abbastanza densa (ad esempio E >> V), utilizzando un mucchio di Fibonacci è meglio di un heap binomiale.

Come

L'idea è quindi quella di utilizzare il mucchio di Fibonacci per memorizzare tutti i vertici accessibili dal sotto-albero che già costruito, indicizzati dal peso del bordo più piccola che conduce ad esso. Se avete capito la realizzazione o l'algoritmo di Prim con l'utilizzo di un'altra struttura di dati, non v'è alcuna reale difficoltà ad utilizzare un mucchio di Fibonacci invece - basta usare il Inserisci e deletemin metodi del mucchio come si farebbe normalmente, e utilizzare il decreasekey metodo per aggiornare un vertice quando si rilascia un bordo anteriore di esso.

L'unica parte difficile è quello di attuare il mucchio reale Fibonacci.

non posso dare tutti i dettagli di implementazione qui (che avrebbe preso le pagine), ma quando l'ho fatto la mia ho fatto affidamento su Introduzione agli algoritmi (Cormen et al) . Se non lo avete ancora, ma sono interessati a algoritmi mi raccomando che si ottiene una copia di esso! E 'la lingua agnostico, e fornisce spiegazioni su tutti gli algoritmi standard, così come le loro prove dettagliato, e sarà sicuramente aumentare la vostra conoscenza e la capacità di utilizzare tutti loro, e progettare e dimostrare nuovi. Questo PDF (dalla pagina di Wikipedia si è collegato ) fornisce alcuni dei dettagli di implementazione, ma non è assolutamente chiaro come Introduzione agli algoritmi .

Ho un rapporto e un presentazione ho scritto dopo averlo fatto, che spiegano un po 'come procedere (per Dijkstra - vedere la fine della ppt per le funzioni di Fibonacci heap in pseudo-codice), ma è tutto in francese ... e la mia codice è in Caml (e francese) in modo da non sono sicuro se questo aiuta !!! E se si può capire qualcosa di esso si prega di essere indulgente, ero appena agli inizi di programmazione così le mie capacità di codifica erano piuttosto scarsa, al momento ...