J'écris un algorithme pour trouver le deuxième arbre de couvre des frais min. Mon idée était la suivante:
Ma question est la suivante: cela fonctionnera-t-il? Y a-t-il une meilleure façon de faire cela?
9 Réponses :
Considérez ce cas:
------100----
| |
A--1--B--3--C
| |
| 3
| |
2-----D
De plus, si le bord min a la connexion d'un sommet pendentif, supprimez-le et calculer la MST à nouveau ne vous obtiendra même pas de MST.
Vous pouvez le faire - essayez de supprimer les bords du MST, un à la fois du graphique et d'exécuter le MST, en prenant le min. Donc, c'est semblable au vôtre, sauf pour itératif:
Merci. J'ai établi quelques exemples et cette idée semble fonctionner pour tous mes exemples. :)
Cela fonctionne - mais c'est une recherche étendue qui prendra O (n ^ 2 * logn) par rapport à la complexité O (Nlogn) de Kruskal.
C'est juste une façon de dire que le MST et le MST_2 sont différents par exactement un bord - il y a de meilleurs algorithmes que cela, mais c'est un moyen d'y penser. Il y a aussi un algorithme (ve) - Kruskal est en fait O (V journalisation), en faisant ci-dessus O (V ^ 2 LOG E).
Kruskal's est en fait O (E Log E) car vous triez les bords - Ignorez les jeux disjoints, ce qui est essentiellement constant s'il est fait correctement. Cet algorithme est donc O (ve log e) depuis que vous avez des bords O (v) dans le MST. Donc, le pire cas est O (v ^ 3 Log V). (journal e = journal v ^ 2 = 2log v = o (journal v)).
Vous avez raison. Généralement pour les problèmes de graphique, je pars dans les E, car le journal E et le journal V est une différence constante, mais cela pourrait indiquer différents algorithmes. J'ai eu des bowvotes pour donner trop de choses dans ma réponse et j'ai eu des bowvotes pour ne pas donner la réponse, mais je sais que cela n'est pas optimal!
Une note supplémentaire, si les bords sont déjà triés, vous n'avez pas besoin de régler à nouveau pour les Kruskal ultérieurs, d'où la complexité. Vous avez juste besoin d'un syndicat linéaire (ish) trouver tous les bords en MST moins un bord. Ensuite, vous pouvez parcourir de manière linéaire la chose triée de toute façon.
Je dis ça comme ça :). Personnellement, je suis contre des bowvotes pour donner trop loin, je ne baisse que si la solution est fausse ou non ce que l'Asker cherche.
@ Notre note supplémentaire: vrai, mais vous ne recevez toujours pas O (v ^ 2 log e). Kruskal initial est O (e journal e + e). Ensuite, vous avez des recalculs o (v) sans tri, donc o (ve) et o (v ^ 3) le pire des cas (O (e log e + ve) est exact).
Oh je suis d'accord, maintenant je ne sais pas ce que je pensais, je pense que je soulignais le O (ve). =)
Vous pouvez le faire dans O (v 2 ). D'abord calculer le MST en utilisant algorithme de prim (peut être fait en O (v 2 )).
Compute Recherche d'un bord retour max [u, v] = le coût du tranchant de coût maximal sur le chemin (unique) de u à V dans le MST . Peut être fait dans O (v 2 ).
(u, V) Ce n'est pas une partie du MST qui minimise ABS (max [u, v] - poids (U, V)) . Peut être fait dans O (E) == O (v 2 ).
mst '= mst - {le bord qui a max [u, v] poids} + {(u, v)} , qui vous donnera le deuxième meilleur MST.
Merci pour l'algorithme. Le lien est mort.
Voici un algorithme qui calculer le 2ème arbre minimum étendu dans O (n ^ 2)
permet de dire le bord actuel de l'arbre est e. Ce bord de l'arbre divisera l'arbre en deux arbres, disons T1 et T-T1. Répéter pour chaque sommet V dans T-T1. = O (n ^ 2)
Sélectionnez Edge Calculez le poids de l'arbre nouvellement formé. Disons e = (u, v) où u est dans t1 et V est dans t-t1. = O (n ^ 2)
E '= (U, V) Pour tous V dans T-T1 et E' est en G (graphique d'origine) et il est minimum
w = poids (t)-poids (E) + poids (E ')
Est-ce que o (n ^ 2) le mieux que l'on puisse faire?
Ceci est similaire à la réponse de Larry.
Après avoir trouvé du MST,
pour chaque new_edge = pas un bord en MST
solution du lien suivant.
http://web.mit.edu/6.263/www/quiz1-f05 -sol.pdf
Votre approche ne fonctionnera pas, comme cela pourrait être le cas que min. Bord de poids dans le MST est un pont (un seul bord raccordant 2 parties de graphique) afin de supprimer ce bord de l'ensemble entraînera 2 nouveau MST par rapport à un MST.
légère édition de votre algo.
Use kruskals to find lowest MST.
for all edges i of MST
Delete edge i of the MST.
Run kruskals again on the entire graph.
loss=cost new edge introduced - cost of edge i
return MST for which loss is minimum
basé sur la réponse de @ Ivlad
Pour vous mettre en pratique, vous pouvez essayer le problème de programmation concurrentiel UVA 10600 - ACM Concours et Blackout , qui consiste à trouver le deuxième arbre minimum étendu dans un graphique pondéré, comme demandé par l'OP. Ma mise en œuvre (en moderne C ++) peut être trouvée ici < / a>. Explication détaillée du
O (V² log V) algorithme
O ( V² journal v)
O (V²)
MST est un arbre qui a le total de poids minimum de tous les bords du graphique. Ainsi, le 2e MST minimum aura le 2e poids total minimum de tous les bords du graphique.
Soit T -> best_mst (triez les bords du graphique, puis trouvez MST en utilisant l'algorithme Kruskal)
T '-> 2ème meilleur MST
Disons que T a 7 bords, maintenant pour trouver T 'nous allons un par un enlever l'un de ces 7 bords et trouver un remplacement de ce bord (le coût de ce bord sera définitivement supérieur au bord que nous venons de retirer de T ).
Disons que le graphique original a 15 bords
Notre meilleur mst (t) a 7 bords
et 2e meilleur mst (t ') va également avoir 7 bords seulement
Comment trouver T '
Il y a 7 bords dans T, maintenant pour tous ces 7 bords, retirez-les un par un et trouvez le remplacement de ces bords.
Disons les bords en MST (T) -> {A, B, C, D, E, F, G}
Disons que notre réponse sera 2nd_best_mst et initialement, il a une valeur infinte (je sais que cela ne semble pas bon, supposons simplement pour le moment).
Pour tous les bords de best_mst:
actuel_edge = i Trouver le remplacement de ce bord, le remplacement de ce bord va certainement avoir du poids plus que le bord, l'un des 7 bords) comment nous allons trouver le remplacement de ce bord, en utilisant l'algorithme de Kruskul (nous trouvons à nouveau le MST, nous n'utiliserons donc que Kruskal Algorithm, mais nous n'avons pas besoin de trier les bords à nouveau, car nous l'avons fait quand nous étions Trouver le best_mst (t). NEW_MST sera généré 2nd_best_mst = min (nouveau_mst, 2nd_best_mst) Retour 2nd_best_mst Algorithme
laissez "dire que le graphique orignal a 10 bords Trouvez le best_mst (en utilisant Kruskal Algo) et assumez best_mst n'a que 6 bords Bow Il y a 4 bords restants qui ne sont pas dans le meilleur_mst (car leur valeur de poids est grande et une de ces bords nous donnera notre 2nd_best_mst Pour chaque bord 'x' non présent dans le best_mst (c'est-à-dire 4 bords laissés) ajoutez ce bord dans la best_mst qui créera le cycle Trouvez le bord 'k' avec le poids maximum dans le cycle (autre que le nouvelly_added_edge 'x') Supprimer Edge 'K' temporairement qui formera un nouvel arbre étendu Calculez la différence de poids et cartographiez la perte_différence avec le bord 'x'. Répétez l'étape 4 pour tous ces 4 bords et renvoyez l'arbre étendu avec la plus petite différence de poids à la best_mst.
Eh bien, j'ai une autre idée ...... mais je ne suis pas à peu près sûr que fonctionne ..... Ajoutez le poids minimum parmi les précédents évitant les bords au plus récent MST. Si mon idée est fausse. Nanyone peut donner un exemple?