Festgefahren auf das Lösen des minimalen Spanning-Baumproblems

Ich habe mein Problem reduziert, um den minimalen aufspannenden Baum im Diagramm zu finden. Aber ich möchte eine weitere Einschränkung haben, die ist, dass der Gesamtgrad für jeden Eckpunkt einen bestimmten konstanten Faktor nicht überschreiten sollte. Wie modelliere ich mein Problem? Ist MST der falsche Weg? Kennst du Algorithmen, die mir helfen?Festgefahren auf das Lösen des minimalen Spanning-Baumproblems

Ein weiteres Problem: Mein Diagramm hat doppelte Kantengewichte, gibt es also eine Möglichkeit, die Anzahl der eindeutigen MSTs zu zählen? Gibt es Algorithmen, die das tun?

Vielen Dank.

Edit: Nach Grad, meine ich die Gesamtzahl der Kanten, die den Scheitelpunkt verbinden. Mit doppeltem Kantengewicht meine ich, dass zwei Kanten das gleiche Gewicht haben.

Quelle

2009-05-20 unj2

Sie können einfach den Kruskal-Algorithmus anwenden und die Nedges aus der Liste entfernen, die mit Knoten mit einem maximalen Gesamtgrad verbunden sind, aber ich weiß nicht, ob dies eine optimale Lösung bestimmt (und ob überhaupt eine Lösung gefunden wird!)) – akappa

Andernfalls können Sie den vollständigen kruskal-Algorithmus anwenden und dann einige lokale Suchtechniken verwenden, um einen gültigen Spannbaum zu erhalten. – akappa

.? Dieses Papier zeigt, wie man in polynomialer Zeit findet Ein Spanning Tree maximalen Grad d + 1, die mindestens so gut wie jeden Spanning Tree maximalen Grad d ist: http://www.andrew.cmu.edu/user/mohits/mbdst.pdf

// Bearbeiten Des Original-Link ist derzeit inaktiv, versuchen http://research.microsoft.com/pubs/80193/mbdst.pdf statt.

Quelle

2009-06-09 04:33:03 Dave

Havent liest das ganze Ding aber sieht echt brauchbar aus. Vielen Dank. – unj2

Nun, es ist leicht zu beweisen, dass es keine Lösung sein kann: einfach Ihre Eingabe grafische Darstellung eines Baumes machen, die einen Scheitelpunkt mit dem Grad hat höher als Ihr Limit ..

Quelle

2009-05-20 22:43:42

Was ist, wenn ich den Ladefaktor höher als die Gesamtgewichtsbeschränkung setze? Das ist, ich bin bereit, mich für das zweite minimale oder sogar ein Drittel minimal zu entscheiden. Aber das bringt Heuristiken mit sich, die mehr Probleme verursachen können. Zum Beispiel, wie entscheiden Sie, welche Kante ersetzt werden soll? Gott gibt es einen anderen Weg, um dieses Problem zu lösen? – unj2

Ich weiß es nicht; Sie haben uns nicht gesagt, was Ihr Problem ist :-) Aber wenn Sie einen aufspannenden Baum mit allen Scheitelpunkten mit deg <= n ... wollen, dann kann ich ein Diagramm erstellen, in dem jeder Spannbaum (minimal oder anders) enthalten ist mindestens eine Ecke mit dem Grad n + 1. Heuristiken werden dir in dieser Situation nicht helfen. –

Garey Johnson hatte dieses Problem zu hamilton reduzieren: (Also das half Annähern der erste:. http://caislab.icu.ac.kr/Lecture/data/2003/spring/ice514/project/m03.ppt jedoch bessere Arbeitsmodelle geschätzt ...

Zählen:. http://mathworld.wolfram.com/SpanningTree.html Danach ist Mathematica eine Funktion hat Irgendwelche Vorschläge in diesem

Quelle

2009-05-21 14:55:02 unj2

Nun, wenn du dich mit dem Matrix-Baum-Theorem (referenziert auf mathworld) beschäftigst, kannst du vielleicht einen Weg finden, einen Spannbaum systematisch in einen anderen zu verwandeln. Wenn du das kannst, dann kannst du durch die aufspannenden Bäume radeln, bis du einen findest, der zu deinen Zwecken passt. Dies ist jedoch alles eine wilde Vermutung; keine Garantien :-) –

Festgefahren auf das Lösen des minimalen Spanning-Baumproblems

Antwort

Verwandte Themen