Coller à la résolution du problème Minimal Spanning Tree

J'ai réduit mon problème à trouver le Spanning Tree minimal dans le graphique. Mais je veux avoir une autre contrainte qui est que le degré total pour chaque sommet ne devrait pas dépasser un certain facteur constant. Comment modéliser mon problème? MST est-il le mauvais chemin? Connaissez-vous des algorithmes qui m'aideront?Coller à la résolution du problème Minimal Spanning Tree

Encore un problème: Mon graphe a des poids de bord dupliqués. Y a-t-il un moyen de compter le nombre de MST uniques? Y a-t-il des algorithmes qui font cela?

Merci. Edit: Par degré, je veux dire le nombre total d'arêtes reliant le sommet. Par poids de bord dupliqué, je veux dire que deux arêtes ont le même poids.

Source

2009-05-20 unj2

Vous pouvez simplement appliquer l'algorithme de kruskal, en supprimant de la liste les nedges qui sont connectés aux nœuds avec un degré total maximum, mais je ne sais pas si cela détermine une solution optimale (et si elle détermine une solution! – akappa

Sinon, vous pouvez appliquer l'algorithme complet de kruskal, puis utiliser des techniques de recherche locale pour obtenir un spanning tree valide. – akappa

.? Cet article montre comment trouver, en temps polynomial , Un arbre couvrant de degré maximal d + 1 qui est au moins aussi bon que tout arbre couvrant de degré maximal d: http://www.andrew.cmu.edu/user/mohits/mbdst.pdf

// Modifier le lien d'origine est actuellement inactif, essayez http://research.microsoft.com/pubs/80193/mbdst.pdf à la place.

Source

2009-06-09 04:33:03 Dave

Havent lire le tout mais semble vraiment utile. Merci. – unj2

Eh bien, il est facile de prouver qu'il n'y peut pas être une solution: il suffit de faire votre entrée graphique un arbre qui a un sommet avec un degré supérieur à votre limite ..

Source

2009-05-20 22:43:42

Et si je mettais le facteur de charge plus haut que la contrainte de poids totale? C'est-à-dire que je suis disposé à me contenter du deuxième minimum ou même du troisième minimum. Mais cela implique des heuristiques qui peuvent créer plus de problèmes. Par exemple, comment décidez-vous quel bord remplacer? Dieu est-il un autre moyen de résoudre ce problème? – unj2

Je ne sais pas; vous ne nous avez pas dit quel est votre problème :-) Mais si vous voulez un arbre couvrant avec tous les vertices ayant deg <= n ... eh bien, je peux arriver à un graphique où n'importe quel spanning tree (minimal ou non) inclut au moins un sommet de degré n + 1. Heuristics ne vous aidera pas dans cette situation .. –

Garey Johnson avait ce problème réduit à hamilton: (donc, celui-ci aidé Approximation le premier. http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt Cependant, les modèles de travail meilleures sont appréciés ...

comptage. http://mathworld.wolfram.com/SpanningTree.html Selon cette étude, Mathematica a une fonction Toute suggestion dans celui-ci

Source

2009-05-21 14:55:02 unj2

Eh bien, si vous creusez dans le théorème de l'arbre de la matrice (référencé sur mathworld), peut-être vous pouvez trouver un moyen de transformer systématiquement un arbre couvrant dans un autre. Si vous pouvez le faire, vous pouvez faire défiler les arbres couvrant jusqu'à ce que vous trouviez celui qui convient à vos fins. C'est tout une supposition sauvage, cependant; pas de garanties :-) –

Coller à la résolution du problème Minimal Spanning Tree

Répondre

Questions connexes