Diese Frage wurde durch eine Frage zum Stapelüberlauf motiviert .
Angenommen, Sie erhalten einen Wurzelbaum (dh es gibt eine Wurzel und Knoten haben Kinder usw.) auf n Knoten (mit 1 , 2 , … , n bezeichnet ).
Jedem Scheitelpunkt ist ein nicht negatives ganzzahliges Gewicht zugeordnet: w i .
Zusätzlich erhalten Sie eine ganze Zahl , so dass 1 ≤ k ≤ n ist .
Das Gewicht einer Menge von Knoten S ⊆ { 1 , 2 , … , n } ist die Summe der Gewichte der Knoten: ∑ s ∈ S w s .
Bei gegebener Eingabe , w i und k ,
Die Aufgabe besteht darin, einen Teilwald * minimalem Gewicht von T zu finden , so dass S genau k Knoten hat (dh | S | = > k ).
Mit anderen Worten, für jeden Unterwald von T , so dass | S ' | = k , wir müssen W ( S ) ≤ W ( S ' ) haben .
Wenn die Anzahl der untergeordneten Knoten jedes Knotens begrenzt war (z. B. Binärbäume), gibt es einen Polynomzeitalgorithmus mit dynamischer Programmierung.
Ich habe das Gefühl, dass dies NP-schwer für allgemeine Bäume ist, aber ich konnte keine Referenzen / Beweise finden. Ich habe sogar hier gesucht , konnte aber nichts finden, was helfen könnte. Ich habe das Gefühl, dass dies NP-hart bleiben wird, selbst wenn Sie einschränken (und dies könnte einfacher zu beweisen sein).
Dies scheint ein gut untersuchtes Problem zu sein.
Weiß jemand, ob dies ein NP-Hard-Problem ist / ob ein P-Zeit-Algorithmus bekannt ist?
* Ein Unterwald von ist eine Teilmenge S von Knoten des Baums T , so dass, wenn x ∈ S ist , alle Kinder von x auch in S sind. (dh es ist eine disjunkte Vereinigung von verwurzelten Unterbäumen von T ).
PS: Bitte entschuldigen Sie, wenn sich herausstellt, dass ich etwas Offensichtliches verpasst habe und die Frage wirklich nicht zum Thema gehört.
Antworten:
quelle