Maximale Anzahl von wurzelgesteuerten Pfaden

Question

Ich habe diese Frage mit der rekursiven Methode zu lösen und basierend auf der rekursiven Methode eine dynamische Programmierlösung zu erstellen. Ich wäre dankbar für Hilfe, hauptsächlich mit der rekursiven Lösung.

Gegeben ein Wurzelbaum T und eine Zahl K. root-directed path ist definiert als ein Pfad, in dem jeder Eckpunkt ein Elternteil des Eckpunkts vor ihm im Pfad ist. Ziel: die maximale Anzahl von dinstinct finden (keine gemeinsamen Eckpunkt) von Wurzel gerichteten Wegen der Länge k in T

zum Beispiel: für den Baum in dem Bild und k = 3 ist die Antwort: 3 example

Answer 1

Definieren Sie DP_in(u,k) als die maximale Anzahl von verschiedenen (keine gemeinsamen Scheitelpunkte) von Root-gerichtete Pfade der Länge k in der Baum unter u im Pfad unterwurzelt auf u im Pfad.

Auch definieren DP_out(u,k) als die maximale Anzahl von unterschiedlichen (keine gemeinsamen Eckpunkt) von Wurzel gerichteten Wegen der Länge k in dem Unterbaum verwurzelt auf u mit u in keinen Pfad.

Ich werde zuerst behandeln DP_out(u,k). Wenn sich u in keinem Pfad befindet, benötigen Sie die maximalen Root-directed-Pfade der Länge k, die an einem der untergeordneten Elemente u untergeordnet sind. So haben wir:

DP_out(u,k)=Sum i=1 to r [max(DP_in(v_i, k-1), DP_out(v_i, k)) ] wo v_1, ..., v_r sind die Kinder von u.

Jetzt als für DP_in(u,k), da u ist auf dem Weg, dann ein, und nur ein, der die Kinder u im Weg sein muss, die u enthält. Daher haben wir, dass:

DP_in(u,k)= max (DP_in(v_i, k-1)+ Sum j=1 to r, j=/=i [max(DP_in(v_j, k-1), DP_out(v_j, k))]) über i=1,...,r.

Wenn r der Wurzelknoten des Baumes ist, dann ist die Antwort, die Sie wollen in der Tat ist max(DP_in(r,k), DP_out(r,k)).

Sie können die DP-Tabelle gleichzeitig von der Unterseite des Baums (Blätter) aufbauen und nach oben gehen, um sicherzustellen, dass die Reihenfolge des Füllens der Tabellen in Ordnung ist.

Wir wissen, dass es O(n^2) Unter Problemen, und jedes Teilproblem von DP_out(u,k) kann in O(n) berechnet werden, während jedes Teilproblem von DP_in(u,k) in O(n^2) naiven berechnet werden. Also eine Summe von Worst Case O(n^4).

Beachten Sie, dass ich natürlich nicht behaupte, dass meine Methode die optimale ist, es ist höchstwahrscheinlich eine leicht optimierte Methode (mit einigen DS), aber ich würde dies für Sie zu verfolgen, wenn Sie interessiert sind drin.