Solución:
Un montón de Fibonacci es una cola de prioridad bastante compleja que tiene un excelente comportamiento asintótico amorizado en todas sus operaciones: inserción, búsqueda mínima y tecla de disminución, todas se ejecutan en O (1) tiempo amortizado, mientras que eliminar y extraer min se ejecutan en O amortizado. (lg n) tiempo. Si desea una buena referencia sobre el tema, le recomiendo encarecidamente que obtenga una copia de “Introducción a los algoritmos, 2ª edición” de CLRS y lea el capítulo al respecto. Está muy bien escrito y es muy ilustrativo. El documento original sobre los montones de Fibonacci de Fredman y Tarjan está disponible en línea, y es posible que desee consultarlo. Es denso, pero da un buen trato al material.
Si desea ver una implementación de los montones de Fibonacci y el algoritmo de Prim, tengo que darle un descaro a mis propias implementaciones:
- Mi implementación de un montón de Fibonacci.
- Mi implementación del algoritmo de Prim usando un montón de Fibonacci.
Los comentarios en ambas implementaciones deberían proporcionar una descripción bastante buena de cómo funcionan; avíseme si hay algo que pueda hacer para aclararlo.
El algoritmo de Prim selecciona la arista con menor peso entre el grupo de vértices ya seleccionado y el resto de vértices.
Entonces, 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 van al montón.
Luego, vuelve a elegir el borde con el valor mínimo del montón.
Entonces, las complejidades de tiempo que obtenemos son:
Fibonacci:
Elección del borde mínimo = O (tiempo de eliminación del mínimo) = O (log (E)) = O (log (V))
Insertar bordes en el montón = O (tiempo de insertar el elemento en el montón) = 1
Montón mínimo:
Elegir el borde mínimo = O (tiempo de eliminar el mínimo del montón) = O (log (E)) = O (log (V))
Insertar bordes en el montón = O (tiempo de insertar el elemento en el montón) = O (log (E)) = O (log (V))
(Recuerde que E = ~ V ^ 2 … entonces log (E) == log (V ^ 2) == 2Log (V) = O (log (V))
Entonces, en total tiene inserciones E y opciones mínimas de V (es un árbol al final).
Entonces, en Min heap obtendrás:
O (Vlog (V) + Elog (V)) == O (Elog (V))
Y en el montón de Fibonacci obtendrás:
O (Vlog (V) + E)
Implementé Dijkstra usando montones de Fibonacci hace unos 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 tienes que realizar esta operación.
Por que es bueno
La complejidad de esos algoritmos que usan un montón binomial (que es la forma más “estándar”) es O (E * log V), porque, aproximadamente, probará cada borde (E), y para cada uno de ellos agregará el nuevo vértice de su montón binomial (log V) o disminuir su clave (log V), y luego tiene que encontrar el mínimo de su montón (otro log V).
En cambio, cuando usa un montón de Fibonacci, el costo de insertar un vértice o disminuir su clave en su montón es constante, por lo que solo tiene una 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 total O (E + V * log V).
Entonces, si su gráfico es lo suficientemente denso (por ejemplo, E >> V), usar un montón de Fibonacci es mejor que un montón binomial.
Cómo
Por lo tanto, la idea es usar el montón de Fibonacci para almacenar todos los vértices accesibles desde el subárbol que ya construiste, indexados por el peso del borde más pequeño que conduce a él. Si entendió la implementación o el algoritmo de Prim con el uso de otra estructura de datos, no hay ninguna dificultad real en usar un montón de Fibonacci en su lugar, simplemente use el insertar y deletemin métodos del montón como lo haría normalmente, y utilice el tecla de disminución método para actualizar un vértice cuando suelta un borde que conduce a él.
La única parte difícil es implementar el montón de Fibonacci real.
No puedo darte todos los detalles de implementación aquí (eso tomaría páginas), pero cuando hice el mío, confié mucho en Introducción a los algoritmos (Cormen et al). Si aún no lo tiene pero le interesan los algoritmos, le recomiendo que obtenga una copia. Es independiente del lenguaje y proporciona explicaciones detalladas sobre todos los algoritmos estándares, así como sus pruebas, y definitivamente aumentará su conocimiento y capacidad para usarlos todos, diseñar y probar nuevos. Este PDF (de la página de Wikipedia que vinculó) proporciona algunos de los detalles de implementación, pero definitivamente no es tan claro como Introducción a los algoritmos.
Tengo un informe y una presentación que escribí después de hacer eso, que explica un poco cómo proceder (para Dijkstra, vea el final del ppt para las funciones del montón de Fibonacci en pseudocódigo) pero está todo en francés … y mi El código está en Caml (y en francés), ¡así que no estoy seguro de si eso ayuda! Y si puede entender algo de esto, sea indulgente, apenas estaba comenzando a programar, por lo que mis habilidades de codificación eran bastante pobres en ese momento …