Rekonstruktion eines Baums aus Trennzeichenabfragen

Angenommen, ist ein Baum konstanten Grades, dessen Struktur wir nicht kennen. Das Problem besteht darin, den Baum durch Fragen des Formulars auszugeben : "Liegt der Knoten auf dem Pfad von Knoten zu Knoten ?". Angenommen, jede Abfrage kann von einem Orakel in konstanter Zeit beantwortet werden. Wir kennen den Wert von , die Anzahl der Knoten im Baum. Ziel ist es, den Zeitaufwand für die Ausgabe des Baums in zu minimieren .$T$$T$$x$$a$$b$$n$$n$

Gibt es einen -Algorithmus für das obige Problem?$o(n^2)$

Angenommen, der Grad eines Knotens in beträgt höchstens 3.$T$

Was ich weiß

Das Gehäuse mit begrenztem Durchmesser ist einfach . Wenn der Durchmesser des Baumes , können wir einen Divide-and-Conquer-Algorithmus erhalten:$D$

Jeder binäre Baum hat ein gutes Trennzeichen, das den Baum in Komponenten mit einer Größe von nicht weniger als 1 / 3n unterteilt.

1. Wählen Sie einen beliebigen Scheitelpunkt x. Wenn es ein gutes Trennzeichen ist, beschriften Sie das und wiederholen Sie den Vorgang.
2. Finde alle 3 Nachbarn von x.
3. Bewegen Sie sich in Richtung des Nachbarn mit der größten Anzahl von Knoten. Wiederholen Sie Schritt 2 mit dem Nachbarn.

Da das Finden des Trennzeichens höchstens Schritte dauert , erhalten wir einen -Algorithmus.$D$$O(nD\log n)$

Ein randomisierter Algorithmus$O(n\;\log^2 n)$ . (verschoben von den Kommentaren unten)

Wähle zwei Ecken x und y nach dem Zufallsprinzip. Mit einer Wahrscheinlichkeit von 1/9 liegen sie auf den gegenüberliegenden Seiten eines Trennzeichens. Wählen Sie den mittleren Knoten des Pfades von nach . Überprüfen Sie, ob es sich um ein Trennzeichen handelt, oder führen Sie eine binäre Suche durch.$x$$y$

Es dauert , bis das Trennzeichen gefunden ist. Wir erhalten also einen zufälligen -Algorithmus.$O(n\;\log n)$$O(n\;\log^2 n)$

Hintergrund. Ich habe dieses Problem von einem Freund erfahren, der mit probabilistischen grafischen Modellen arbeitet. Das obige Problem entspricht ungefähr dem Erlernen der Struktur eines Verbindungsbaums unter Verwendung eines Orakels, das bei drei Zufallsvariablen X, Y und Z den Wert der gegenseitigen Information zwischen X und Y bei dem Wert von Z angeben kann. Wenn der Wert nahe ist bis Null können wir annehmen, dass Z auf dem Weg von X nach Y liegt.

Nein. Die folgende einfache Gegnerstrategie impliziert, dass jeder Algorithmus zum Rekonstruieren eines Knoten-Baums mindestens "zwischen" Abfragen erfordert .$n$$\binom{n-1}{2} = n(n-1)/2$

Beschriften Sie die Knoten . Der Gegner beantwortet alle Fragen so, als wäre der Baum ein Stern mit dem Scheitelpunkt in der Mitte. Stellen Sie sich als Root und die anderen Knoten als untergeordnete Knoten vor.0 $0,1,2,\dots,n-1$$0$$0$

Between?(a,x,b)
    if x=0 return TRUE else return FALSE

Angenommen, der Algorithmus wird angehalten, nachdem weniger als Abfragen ausgeführt wurden. Dann müssen zwei Eckpunkte und , wobei keiner gleich Null ist, so dass der Algorithmus keine Permutation des Tripels abgefragt hat . Wenn der Algorithmus behauptet, dass der Baum kein Stern mit der Mitte , deckt der Gegner seine Eingabe auf und beweist, dass der Algorithmus falsch ist. Der Gegner enthüllt dann, dass tatsächlich das einzige Kind von , was beweist, dass der Algorithmus erneut falsch ist.y z ( 0 , y , z ) 0 x $n(n-1)/2$$y$$z$$(0,y,z)$$0$$x$$y$

Update: Hoppla, habe gerade die Gradbeschränkung bemerkt. Zum Glück ist dies keine große Hürde. Ersetzen Sie Knoten durch Ihren bevorzugten Binärbaum, wobei die anderen Knoten in einer unbekannten Reihenfolge als Blätter angezeigt werden, und legen Sie diesen Teilbaum dem Rekonstruktionsalgorithmus offen. Die Rekonstruktion des resultierenden -Knoten-Binärbaums erfordert immer noch mindestens Abfragen. Entsprechend erfordert die Rekonstruktion eines Binärbaums mit Knoten mindestens Abfragen. (Ich bin sicher, eine subtilere Konstruktion würde die Konstante verbessern.)n - 1 ( 2 n - 3 ) n ( n - 1 ) / 2 m ( m + 3 ) ( m + 2 ) /$0$$n-1$$(2n-3)$$n(n-1)/2$$m$$(m+3)(m+2)/8$ Wie Jagadish betont, funktioniert diese Verallgemeinerung nicht. Abfragen über interne Knoten im Baum erlegen den Blättern eine Reihenfolge auf, wodurch die Anzahl der erforderlichen Abfragen verringert wurde.

$\tilde O(n \sqrt{n})$