¿Cómo implementar el algoritmo de Prim con un montón de Fibonacci?

Question

Sé Prim's algorithm y sé su implementación, pero siempre omito una parte que quiero preguntar ahora. Se ha escrito que la aplicación del algoritmo de Prim con Fibonacci heap es O(E + V log(V)) y mi pregunta es:

• lo que es un montón de Fibonacci en breve?
• ¿Cómo se implementa? Y
• ¿Cómo se puede implementar el algoritmo de Prim con un montón de Fibonacci?

Answer 1

a Fibonacci montón es una cola de prioridad bastante complejo que tiene excelente amoritzed comportamiento asintótico en todas sus operaciones - inserción, encontrar-min, y la disminución -key todo ejecutar en O (1) tiempo amortizado, mientras que eliminar y extraer-min se ejecutan en tiempo O (lg n) amortizado. Si desea una buena referencia sobre el tema, le recomiendo que recoja una copia de "Introducción a los algoritmos, segunda edición" de CLRS y lea el capítulo sobre ella. Está notablemente bien escrito y es muy ilustrativo. The original paper on Fibonacci heaps by Fredman and Tarjan está disponible en línea, y es posible que desee comprobarlo. Es denso, pero da un buen tratamiento del material.

Si desea ver una implementación de montones de Fibonacci y el algoritmo de Prim, tengo que dar un descarado enchufe para mis propias implementaciones:

1. My implementation of a Fibonacci heap.
2. My implementation of Prim's algorithm using a Fibonacci heap.

El los comentarios en ambas implementaciones deberían proporcionar una descripción bastante buena de cómo funcionan; ¡Avísame si hay algo que pueda hacer para aclarar!

Answer 2

El algoritmo de Prim selecciona el borde con el menor peso entre el grupo de vórtices ya seleccionados y el resto de los vórtices.
Para implementar el algoritmo de Prim, necesita un montón mínimo. Cada vez que selecciona un borde, agrega el nuevo vórtice al grupo de vórtices que ya ha elegido y todos sus bordes adyacentes entran en el montón.
Luego elige de nuevo el borde con el valor mínimo del montón.

Así que los tiempos que obtenemos son:
Fibonacci:
La elección de borde mínimo = O (tiempo de eliminación mínimo) = O (log (E)) = O (log (V))
bordes Inserción a montón = O (tiempo de insertar el artículo a amontonar) =

Min montón:
La elección de borde mínimo = O (tiempo de eliminación mínimo de montón) = O (log (E)) = O (registro (V))
Insertar bordes en heap = O (tiempo de insertar elemento en heap) = O (log (E)) = O (log (V))

(Recuerde que E = ~ V^2 ... así que inicie sesión (E) == log (V^2) == 2Log (V) = O (log (V))

Por lo tanto, en total tiene insertos E, y V selecciones mínimas (es un árbol al final) .

Así en Min amontona obtendrá:

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

Y en Fibonacci se amontonarán' ll obtener:

O (Vlog (V) + e) ​​

Answer 3

Implementé Dijkstra usando montones de Fibonacci hace algunos años, y el problema es bastante similar. Básicamente, la ventaja de los montones de Fibonacci es que hace que encontrar el mínimo de un conjunto sea una operación constante; así que eso es muy apropiado para Prim y Dijkstra, donde en cada paso debes realizar esta operación.

¿Por qué es bueno

La complejidad de los algoritmos usando un montón binomial (que es la forma más "estándar") es O (E * V log), porque - más o menos - que tratará cada arista (E), y para cada uno de ellos agregará el nuevo vértice a su pila binomial (log V) o disminuirá su clave (log V), y luego tendrá que encontrar el mínimo de su pila (otro log V).

En cambio, cuando usa un montón de Fibonacci, el costo de insertar un vértice o disminuir su clave en el montón es constante, por lo que solo tiene un O (E) para eso. PERO eliminar un vértice es O (log V), por lo que al final se eliminarán todos los vértices que agreguen un O (V * log V), para un O total (E + V * log V).

Así que si su gráfica es lo suficientemente densa (por ejemplo, E >> V), usar un montón de Fibonacci es mejor que un montón binomial.

Cómo

La idea es, pues, utilizar el montón de Fibonacci para almacenar todos los vértices accesibles desde el subárbol que ya edificados, indexados por el peso de la arista más pequeña que conduce a ella. Si entendió la implementación o el algoritmo de Prim con otra estructura de datos, no hay una dificultad real en usar un montón de Fibonacci en su lugar: simplemente use inserte y deletemin métodos del montón como lo haría normalmente, y use la tecla de disminución método para actualizar un vértice cuando sueltas un borde que lo conduce.

La única parte difícil es implementar el montón real de Fibonacci.

No puedo darle todos los detalles de implementación aquí (eso tomaría páginas), pero cuando hice la mía, confié fuertemente en Introduction to algorithms (Cormen et al). Si aún no lo tiene pero está interesado en algoritmos, le recomiendo que obtenga una copia. Es independiente del idioma y proporciona explicaciones detalladas sobre todos los algoritmos de estándares, así como sus pruebas, y definitivamente aumentará su conocimiento y capacidad para usarlos todos, y diseñar y probar otros nuevos. This PDF (de la página de Wikipedia que ha vinculado) proporciona algunos de los detalles de implementación, pero definitivamente no es tan claro como Introducción a los algoritmos.

Tengo un report y una presentation escribí después de hacer eso, que explican un poco la forma de proceder (por Dijkstra - ver el final del PPT para las funciones de Fibonacci montón de pseudo-código) pero es todo en francés. .. y mi code está en Caml (y en francés) así que no estoy seguro si eso ayuda !!! Y si puedes entender algo de eso, por favor sé indulgente, recién estaba comenzando a programar, así que mis habilidades de codificación eran bastante malas en ese momento ...