Comment mettre en œuvre l'algorithme de Prim avec un tas de Fibonacci?

Question

Je sais que algorithme de Prim et je sais que sa mise en œuvre, mais toujours je saute une partie qui Je veux demander maintenant. Il a été écrit que la mise en œuvre de l'algorithme de Prim avec tas est Fibonacci O(E + V log(V)) et ma question est :

• ce qui est un tas de Fibonacci en bref?
• Comment est-il mis en œuvre? Et
• Comment pouvez-vous mettre en œuvre l'algorithme de Prim avec un tas de Fibonacci?

Answer 1

Un tas de Fibonacci est une file d'attente prioritaire assez complexe qui a une excellente amoritzed comportement asymptotique sur toutes ses opérations - insertion, trouver-min, et la diminution de clé fonctionnent tous en O (1) amorti le temps, tout en suppression et extrait min run dans amorti O (lg n). Si vous voulez une bonne référence sur le sujet, je vous recommande fortement ramasser une copie de « Introduction aux algorithmes, 2e édition » par CLRS et la lecture du chapitre sur elle. Il est remarquablement bien écrit et très illustrative. Le document original sur des tas de Fibonacci par Fredman et Tarjan est disponible en ligne, et vous pouvez le vérifier. C'est la dense, mais donne un bon traitement de la matière.

Si vous souhaitez voir une mise en œuvre des tas de Fibonacci et l'algorithme de Prim, je dois donner un bouchon sans vergogne pour mes propres implémentations:

1. Ma mise en œuvre d'un tas de fibonacci.
2. Ma mise en œuvre de l'algorithme de Prim en utilisant un tas de Fibonacci.

Les commentaires de ces deux mises en œuvre devrait fournir une assez bonne description de la façon dont ils travaillent; laissez-moi savoir s'il y a quelque chose que je peux faire pour clarifier!

Answer 2

L'algorithme de Prim sélectionner le bord avec le poids le plus faible entre le groupe de vortexes déjà sélectionnés et le reste des vortexes.
Donc, pour mettre en œuvre l'algorithme de Prim, vous avez besoin d'un tas minimum. Chaque fois que vous sélectionnez un avantage que vous ajoutez le nouveau tourbillon au groupe de vous vortexes avez déjà choisi, et tous ses bords adjacents entrent dans le tas.
Ensuite, vous choisissez le bord avec la valeur minimale à nouveau dans le tas.

Donc le temps que nous obtenons sont:
Fibonacci:
Le choix bord minimum = O (temps de retrait minimum) = O (log (E)) = O (log (V)) Insertion de bords de segment = O (temps d'insertion d'un objet au tas) = ?? 1

tas Min:
Le choix bord minimum = O (temps de retrait minimum du tas) = ?? O (log (E)) = O (log (V)) Insertion de bords de segment = O (temps d'insertion d'un objet au tas) = ?? O (log (E)) = O (log (v))

(Rappelez-vous que E = ~ V ^ 2 ... donc log (E) == log (V ^ 2) == 2log (V) = O (log (V))

Donc, au total, vous avez des inserts E et choosings minimum V (Il est un arbre à la fin).

Donc, en mini tas vous obtiendrez:

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

Et en tas de Fibonacci vous obtiendrez:

O (Vlog (V) + E)

Answer 3

Je Dijkstra en utilisant implémenté tas de fibonacci il y a quelques années, et le problème est assez similaire. En fait, l'avantage des tas de Fibonacci est qu'il permet de trouver le minimum d'un ensemble une opération constante; de sorte que de très approprié pour Prim et Dijkstra, où à chaque étape, vous devez effectuer cette opération.

Pourquoi il est bon

La complexité de ces algorithmes utilisant un tas binomial (ce qui est le plus « standard ») est O (E * log V), car - à peu près - vous essayerez chaque bord (E), et pour chacun d'entre eux vous sera soit ajouter le nouveau sommet à votre tas binomial (log V) ou diminuer sa clé (log V), et ensuite trouver le minimum de votre tas (un autre journal V).

Au lieu de cela, lorsque vous utilisez un Fibonacci entasse le coût de l'insertion d'un sommet ou en diminuant sa clé dans votre tas est constant si vous avez seulement un O (E) pour cela. MAIS la suppression d'un sommet est O (log V), donc depuis la fin chaque sommet sera supprimé qui ajoute un O (V * log V), pour une O totale (E + V * log V).

Donc, si votre graphique est assez dense (par exemple E >> V), en utilisant un tas de Fibonacci est mieux qu'un tas binomial.

Comment

L'idée est donc d'utiliser le tas de Fibonacci pour stocker tous les sommets accessibles depuis la sous-arborescence vous avez déjà construit, indexé par le poids du plus petit bord qui y mène. Si vous avez compris la mise en œuvre ou l'algorithme de Prim avec l'aide d'une autre structure de données, il n'y a pas de réelles difficultés à utiliser un tas de Fibonacci à la place - il suffit d'utiliser les insérer et deletemin méthodes de tas comme vous le feriez normalement, et utiliser le decreaseKey méthode pour mettre à jour un sommet lorsque vous relâchez un bord menant.

La seule partie difficile est de mettre en œuvre le tas de Fibonacci réelle.

Je ne peux pas vous donner tous les détails de mise en œuvre ici (cela prendrait des pages), mais quand je l'ai fait moi je compté sur introduction aux algorithmes (Cormen et al) . Si vous ne l'avez pas encore, mais sont intéressé par des algorithmes que je recommande fortement que vous obtenez une copie de celui-ci! Il agnostique de la langue, et il fournit des explications détaillées sur tous les algorithmes de normalisation, ainsi que leurs preuves, et va certainement augmenter vos connaissances et la capacité à utiliser tous, et de concevoir et de prouver de nouveaux. Ce PDF (à partir de la page de Wikipedia, lié ) fournit quelques-uns des détails de mise en œuvre, mais il est certainement pas aussi clair que introduction aux algorithmes .

Je rapport et Code est en Caml (et en français), donc je ne sais pas si ça aide !!! Et si vous pouvez comprendre quelque chose de ce s'il vous plaît soyez indulgents, je ne faisais que commencer la programmation pour que mes compétences de codage étaient assez pauvres à l'époque ...