Il minimo più veloce algoritmo spanning tree

Question

http://en.wikipedia.org/wiki/Minimum_spanning_tree

Sto cercando di punto di riferimento il mio minimo spanning algoritmo di albero contro il meglio del meglio. Qualcuno sa dove posso trovare un'implementazione C++ di questi algoritmi? Ho abbuffato e cercato su Google e non ho trovato nulla. Se questi algoritmi sono i migliori, sicuramente ci deve essere un'implementazione C++ da qualche parte?

Il minimo veloce spanning tree algoritmo ad oggi è stato sviluppato da David Karger, Philip Klein, e Robert Tarjan, che ha trovato un tempo lineare algoritmo randomizzato basa su una combinazione di algoritmo di Borůvka e il contrario -algoritmo di eliminazione. [2] [3] L'algoritmo non randomizzato più veloce, di Bernard Chazelle, si basa sull'heap morbido , una coda approssimativa con priorità . [4] [5] Il tempo di esecuzione è O (m α (m, n)), dove m è il numero di spigoli , n è il numero di vertici e α è la classica inversa funzionale della funzione Ackermann. La funzione α cresce molto lentamente, quindi che per tutti gli scopi pratici può essere considerata una costante non maggiore di rispetto a 4; quindi l'algoritmo di Chazelle si avvicina molto al tempo lineare. Se i pesi del bordo sono numeri interi con una lunghezza di bit limitata , allora gli algoritmi deterministici sono noti con il tempo di esecuzione lineare . [6] Se esiste un algoritmo deterministico con tempo di esecuzione lineare per i pesi generali è ancora una domanda aperta. Tuttavia, Seth Petie e Vijaya Ramachandran hanno trovato un algoritmo deterministicamente deterministico ottimale , la cui complessità computazionale è sconosciuta. [7]

Ho già testato gli algoritmi del grafico di Boost C++.

Answer 1

Quando la pagina di Wikipedia dice "l'algoritmo dell'albero di spanning minimo più veloce", ciò che intendono è l'algoritmo con i limiti asintotici più bassi - in questo caso, O (m α (m, n)), con m, n e α definito come nella citazione che hai incollato. In parole povere, questo significa che per valori di input molto grandi, la quantità di tempo impiegata sarà sempre limitata da C * m * α (m, n), per un certo valore di C. Ma si noti che C potrebbe essere molto grande - cioè , questo algoritmo potrebbe essere più lento di altri quando applicato a valori di input più piccoli, anche se è più veloce di altri per valori di input molto grandi.

Quando si confrontano i limiti asintotici di due algoritmi, non c'è "test" per vedere quale è più veloce: basta dimostrare i limiti asintotici di ciascun algoritmo e vedere quale è inferiore. ("Asintotica" si riferisce al comportamento come la dimensione di ingresso va all'infinito - ed è difficile per eseguire i test con valori di ingresso infinita grandezza.)

Ma si noti che ci sono casi in cui si dovrebbe non utilizzare l'asintoticamente algoritmo più veloce. Se la "C" è molto grande, potrebbe essere meglio usare un algoritmo più semplice per valori di dati più piccoli.

La mia ipotesi è che il tuo algoritmo possa migliorare sul C, ma non sui limiti asintotici. Ma se mi sbaglio, devi inviarlo ad ACM!

Per ulteriori informazioni, consultare: http://en.wikipedia.org/wiki/Big_O_notation

Answer 2

www.dcc.uchile.cl/~raparede/publ/09algorIQS.pdf "On Ordinamento, Mucchi, e minimo Spanning Trees", Gonzalo Navarro e Rodrigo Paredes

presenta alcune "migliori delle migliori" misure di memoria interna ed esterna e fornisce riferimenti alle precedenti implementazioni .

Riferiscono # di I/O e tempo di CPU in funzione delle dimensioni grafico e descrivono bene i loro casi di test, in modo da in linea di principio si potrebbe fare i test e confrontare con loro grafici pubblicati. È possibile utilizzare il loro riferimento Prim2 (codice da Peter Sanders, che rende disponibili molti codici veloci) per calibrare le proprie misurazioni con .