Wie kann ich zufällig Bäume mit begrenzter Höhe überspannen?

9

Für ein Projekt, an dem ich arbeite, sollte ich zufällige Spannbäume mit begrenzter Höhe generieren.

Grundsätzlich mache ich Folgendes: 1) Generiere einen Spanning Tree 2) Überprüfe die Machbarkeit, wenn machbar, behalte sie.

1) Ausgehend von einem minimalen Spannbaum (Prims oder Kruskals) füge ich eine nicht vorhandene Kante hinzu und dies erzeugt einen Zyklus. Ich erkenne diesen Zyklus und entferne eine der Kanten dieses Zyklus, die mir einen neuen Spannbaum gibt, und fahre fort dieser Spannbaum durch Hinzufügen einer neuen Kante ...

2) Angenommen, es gibt einen speziellen Scheitelpunkt . Für jeden Scheitelpunkt v sollte die Länge des Pfades von v nach V c e n t e r kleiner als δ sein , wobei δ ein gegebener Parameter ist.vcentervvV.centerδδ

Gibt es einen besseren (klugen) Weg, dies zu tun?

PS Ich habe vergessen, die andere Einschränkung anzugeben (mein Fehler): Der Grad der Eckpunkte sollte ebenfalls begrenzt sein.

Arman
quelle
Ich bin mir nicht sicher, ob ich das richtig verstehe. Entfernen Sie im ersten Schritt die Kante nur zufällig oder so, dass die Höhe des Baumes (möglicherweise) verringert wird?
Sacha
Ich füge zufällig Kanten hinzu und entferne sie.
Arman
Könnten Sie stattdessen einen zufälligen kürzesten Pfad über Bäume untersuchen? Es vereinfacht die Dinge
Jaroslaw Bulatow
Haben Sie Kosten an den Rändern? Suchen Sie einen Spannbaum mit der Höhe δ und minimalen Kosten? Wie @pboothe schrieb, können Sie BFS verwenden und das war's. Das einzige Problem ist, dass BFS zu viel Speicher verwendet. Wenn Sie sich für die Kosten interessieren, können Sie den Algorithmus in Wikipedia für euklidische minimale Spannbäume ausprobieren ( en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree ). Es hat eine Laufzeit von mit O ( n ) Raum. Ö(nLogn)Ö(n)
Marcos Villagra
Ihr Problem hat also drei begrenzte Größen: Höhe des Baums, Grad jedes Scheitelpunkts und Abstand von v_center, stimmt das? Nur die Beschränkung des begrenzten Grades selbst macht das Problem NP-schwer, aber ich nehme an, Sie suchen nach einer Methode, die wahrscheinlich schnell eine Lösung und keinen exakten Algorithmus liefert.
Jagadish

Antworten:

7

Ich habe vor ein paar Jahren an Bäumen mit begrenzter Tiefe gearbeitet, sie sind wirklich interessant. Einige meiner Kollegen haben Algorithmen für die Nachrichtenübermittlung entwickelt, die hervorragende Arbeit geleistet haben, aber ich kann keinen ihrer verfügbaren Codes finden. Wir haben es hier in einem physikalischen Stil geschrieben: http://iopscience.iop.org/1742-5468/2009/12/P12010/ . Sie haben mir gesagt, dass es auch mit Gradgrenzen funktioniert, obwohl das es nicht in die Zeitung geschafft hat.

Der von Ihnen vorgeschlagene Ansatz, den ich als Markov-Kette Monte Carlo bezeichnen würde, ist häufig ein Konkurrent des Ansatzes zur Nachrichtenübermittlung. Wenn Sie daran interessiert sind, aus dem Satz von Spannbäumen mit begrenztem Grad und begrenzter Tiefe eines bestimmten Diagramms ungefähr gleichmäßig zufällig zu wählen, empfehle ich, Ihren Ansatz zu ändern, um "weiche" Grenzen zu verwenden. Das heißt, anstatt einen Kantentausch abzulehnen, bei dem der Baum die Tiefengrenze verletzt, akzeptieren Sie ihn, jedoch mit geringerer Wahrscheinlichkeit als ein Tausch, der die Grenze nicht verletzt. Wenn Sie einen Parameter haben, der steuert, wie viel niedriger diese Wahrscheinlichkeit ist, können Sie die Einschränkung, die Konfigurationen verletzt, immer weniger wahrscheinlich machen, bis Sie zu einer realisierbaren Lösung gelangen, die nahezu gleichmäßig zufällig ist.

Die große Frage ist, wie lange Sie brauchen, um die Kette laufen zu lassen. Da ein Spanning Tree mit einem Grad von höchstens 2 ein Hamilton-Pfad ist, sollten Sie erwarten, dass jede generische Grenze in der Größe des Diagramms exponentiell ist. Aber vielleicht sind die Grafiken, an denen Sie interessiert sind, in irgendeiner Weise etwas Besonderes.

Abraham Flaxman
quelle
2
Weitere Details sowie einen Film: healthalgorithms.wordpress.com/2010/12/23/…
Abraham Flaxman
3

Wenn Ihr Problem darin besteht, einen Spanning Tree aus einer Menge S gleichmäßig abzutastenS.S.hhh

Ich bin mir jedoch nicht sicher, ob der von Ihnen beschriebene Algorithmus einen zufälligen Spanning Tree generiert. Ich würde empfehlen, stattdessen Standardalgorithmen zu betrachten. Es gibt zwei Algorithmen: Wilsons Algorithmus und Aldous-Broders Algorithmus. Sie können einen Blick hier . Es gibt einen neueren (Näherungs-) Algorithmus, der jedoch ziemlich kompliziert ist.

Es kann auch eine Möglichkeit geben, diesen Spanning Tree mit begrenzter Höhe direkt zu generieren. Aber ich habe noch nie von solchen Algorithmen gehört.

Danu
quelle
1

Verwenden Sie die Breitensuche! Führen Sie aus jedem Scheitelpunkt im Diagramm ein BFS durch und wählen Sie den resultierenden Baum mit der kleinsten Höhe aus. Ein BFS findet immer den Pfad von der Wurzel zu jedem anderen Scheitelpunkt mit den wenigsten Sprüngen.

Peter Boothe
quelle
Du hast definitiv recht. Wir haben mit BFS angefangen, aber es hat aufgrund von Gradbeschränkungen für die Scheitelpunkte nicht funktioniert. Ich habe vergessen, diese Einschränkung zu erwähnen (mein Fehler): Der Grad der Eckpunkte im generierten Baum sollte ebenfalls begrenzt sein. Ihre Antwort stimmt mit der aktuellen Frage überein, aber ich denke, ich sollte meine Frage bearbeiten.
Arman
Dann ist Ihr Problem mit ziemlicher Sicherheit NPC durch Reduktion von Degree Constrained Spanning Tree - en.wikipedia.org/wiki/Degree-constrained_spanning_tree
Peter Boothe