Ist dieses optimale Fahrproblem unter Fristen NP-schwer auf Bäumen?

Einer meiner Freunde fragt mich das folgende Planungsproblem auf Baum. Ich finde es sehr sauber und interessant. Gibt es eine Referenz dafür?

Problem: Es gibt einen Baum , jede Kante hat symmetrische Reisekosten von 1 . Für jeden Eckpunkt gibt es eine Aufgabe, die vor ihrem Stichtag erledigt werden muss . Die Aufgabe wird auch als . Jede Aufgabe hat den einheitlichen Wert 1. Die Bearbeitungszeit für jede Aufgabe beträgt 0 , dh der Besuch einer Aufgabe, bevor ihre Frist ihrem Abschluss entspricht. Ohne Verlust der Allgemeinheit bezeichne die Wurzel und nehme an, dass sich bei keine Aufgabe befindet . Es ist ein Fahrzeug , bei zum Zeitpunkt 0 Außerdem gehen wir davon aus, dass für jede Ecke , $T(V,E)$ $v_i$ $d_i$ $v_i$ $v_0$ $v_0$ $v_0$ $d_i \ge dep_i$ $dep_i$ steht für die Tiefe von . Dies ist selbstverständlich, der Scheitelpunkt mit einer kürzeren Frist als die Tiefe sollte als Ausreißer betrachtet werden. Das Problem besteht darin, eine Zeitplanung zu finden, die möglichst viele Aufgaben erledigt. $v_i$

Fortschritt:

Wenn der Baum auf einen Pfad beschränkt ist, befindet er sich über dynamische Programmierung in . $\mathsf{P}$
Wenn der Baum zu einem Graphen verallgemeinert ist, ist er in -complete. $\mathsf{NP}$
Ich habe einen sehr einfachen gierigen Algorithmus, von dem angenommen wird, dass er eine 3-Faktor-Apporoximation aufweist. Ich habe es nicht vollständig bewiesen. Nun, ich bin mehr an den NP-harten Ergebnissen interessiert. :-)

Danke für deinen Rat.

ds.algorithms graph-algorithms np-hardness Peng Zhang
quelle

Bei einer vollständigen Grafik wäre die Aufgabe einfach, oder? Verwenden Sie einfach einen einfachen gierigen Algorithmus ...

Joe

@ Joe: Ja. Da jede Kante 1 Einheit benötigt, ist die Kreuzung egal. Interessieren Sie sich noch für dieses Problem, wenn ja. Vielleicht können wir uns per E-Mail unterhalten. :-)

Peng Zhang

Was ist, wenn alle Fristen gleich sind und / oder wir nur fragen, ob alle Aufgaben erledigt werden können?

Domotorp

@domotorp: Wenn es darum bittet, alle Aufgaben mit einer Frist zu erledigen, lautet die Antwort JA, und zwar genau dann, wenn die einheitliche Frist. Nur Tiefe erste Suche. Was das optimale Problem für den FallIch weiß nicht, ob es einfach ist. Es gibt viele Varianten zu diesem Problem, z. B. die Überlegung, ob die Fristen Werte aus einer endlichen Menge erhalten, deren Kardinalität eine Konstante ist. Vielen Dank für Ihren Kommentar.

d \geq | V |

$d\ge |V|$

d < | V |

$d< |V|$

Peng Zhang

Ich würde sagen, NP-schwer zu sehen, den Planungs-Zoo , außer wenn ich dein Problem falsch verstanden habe.

Gopi

Antworten:

Ich bin mir nicht sicher, ob dies Ihre Antwort ist (siehe unten), aber ein bisschen zu lang für die Kommentare.

Ich dachte, Ihr Problem wäre etwa: , wobei: $(P|tree;p_i=1|\Sigma T_i)$

$P$ steht für identische homogene Prozessoren,
"Baum" steht für Vorrangbedingung der Form eines Baumes,
$p_i=1$ steht für das Gewicht der Aufgaben gleich 1 und
$\Sigma T_i$ steht für die Minimierung der Summe der Verspätungen (dh der Anzahl der Aufgaben, die nach Ablauf ihrer Frist abgeschlossen werden).

Wenn dies der Fall ist, ist Ihr Problem NP-schwer: Sie können es als eine Verallgemeinerung der Minimierung der Gesamtverzögerung auf einer einzelnen Maschine mit Prioritätsbeschränkungen ansehen . In der Tat besagt dieses Papier, dass es für mehrere lineare Ketten auf einem einzelnen Prozessor NP-schwer ist. Die einfache Transformation besteht darin, die Bäume der Form einer Wurzel und lineare Ketten, die von der Wurzel ausgehen, zu nehmen.

Ich bin jedoch überrascht, weil Sie anscheinend sagen, dass Sie für den Fall einer einzelnen linearen Kette die dynamische Programmierung verwenden würden. Ich verstehe nicht, warum Sie DP benötigen würden, da es mir so scheint, als hätten Sie beim Planen einer einzelnen linearen Kette aufgrund der Prioritätsbeschränkungen keine große Auswahl: nur eine einzige Auswahl. Vielleicht habe ich dein Problem falsch verstanden.

Gopi
quelle

Mein Problem scheint anders zu sein als deins. Meins ist, "ein verwurzelter Baum, laufender Rand kostet Zeiteinheit, jeder Scheitelpunkt mit einer Aufgabe mit seiner Frist, Aufgabe braucht keine Zeit, um zu bearbeiten. Wie viele Aufgaben können von der Wurzel aus erledigt werden?". Es gibt also keine Rangfolge, es wird keine Zeit benötigt, um eine Aufgabe zu bearbeiten. Vielen Dank.

Peng Zhang

@PengZhang, Wenn es ein Stammbaum ist, dann gibt es Vorrang? Was die Kosten an den Rändern (Vorrang?) Oder an den Aufgaben angeht, scheint es mir dasselbe zu sein. Ich sehe den Unterschied zwischen beiden wirklich nicht. Wie viele Aufgaben können erledigt werden? Wenn Sie die Anzahl der Aufgaben, die nach Ablauf der Frist erledigt werden, minimieren, entspricht dies der Maximierung der Anzahl der Aufgaben, die erledigt werden können. Vielleicht könnten Sie ein Bild von dem zeichnen, was Sie erwarten?

Gopi

Ich sehe keinen klaren Zusammenhang zwischen zwei Problemen. Bei dem ursprünglichen Problem hängen die Kosten für den Besuch eines nächsten Knotens davon ab, welcher Knoten im vorherigen Schritt besucht wurde. Bei der Planung mit Prioritätsbeschränkungen hängen die Kosten eines nächsten zu verarbeitenden Jobs nicht davon ab, welcher Job im vorherigen Schritt verarbeitet wurde, solange die Prioritätsbeschränkung erfüllt ist.

Yoshio Okamoto

@Gopi: Die Kosten für Kanten können meines Erachtens nicht auf Knoten "übertragen" werden. Wenn der Baum auf einen Pfad beschränkt ist (möglicherweise die Kette, auf die Sie verwiesen haben), können wir in meinem Problem die dynamische Programmierung wie folgt durchführen. Lassen Sie die als nummerierten Eckpunkte von links nach rechts. Lassen die maximale Tasks von Positionsintervall bezeichnen zum Zeitpunkt und der vehichle steht am . Es sei dasselbe wie mit der Ausnahme, dass das Fahrzeug bei steht . Dann haben wir

abgeleitet werden von

1, 2, \dots, n

$1,2,\cdots, n$

f (t, l, r)

$f(t,l,r)$

[l, r]

$[l,r]$

t

$t$

l

$l$

g (t, l, r)

$g(t,l,r)$

f (t, l, r)

$f(t,l,r)$

r

$r$

f (t, l, r)

$f(t,l,r)$

. Da

polynomisch sind, ist dp polynomisch.

{f (\cdot, l + 1, r), g (\cdot, l, r - 1)

$\{f(\cdot,l+1,r), g(\cdot,l,r-1)$

t, l, r

$t,l,r$

Peng Zhang

@PengZhang, ok, ich denke, ich habe ein besseres Verständnis dafür, was du meinst. Ich glaube immer noch, dass man das Papier, das ich gegeben habe, leicht anpassen kann, indem man spezielle Bäume betrachtet, bei denen die Zweige Pfade sind (daher verwurzelte Pfade).

Gopi

Damit dies stimmt, müssen wir einige Annahmen treffen. Siehe Kommentare unten

Für den Baumfall gibt es meines Erachtens einen Algorithmus für die rekursive dynamische Programmierung der Polynomzeit, der durch die maximale Deadline-Zeit parametrisiert ist. Die Teilprobleme sind: wenn wir einen Unterbaum durch die Zeit eingeben und verlassen Sie den Unterbaum durch die Zeit , was ist die maximale Anzahl von Aufgaben , die wir in dem Unterbaum beenden können? Die Basisfälle an den Blättern sind einfach und wir merken von unten nach oben. $t_a$ $t_b$

Wenn wir wirklich durch die maximale Deadline-Zeit parametrisieren würden, wäre der Algorithmus in der Größe des Baums nicht wirklich polynomisch. Die Länge des längsten Pfads, der jeden Knoten in der Struktur besucht, ist jedoch nur in polynomial , und wir müssen nie mehr die Fristen nachprüfen. $|V|$

Joe
quelle

Können Sie mir die Wiederholung zeigen? Ich habe das Gleiche wie bei Ihnen zuvor versucht. Lassen Sie

das Unterproblem des Besuchs des untergeordneten Baums bezeichnen, der auf dem Scheitelpunkt

wurzelt . Aber es gibt zwei Probleme. 1. Wie können Sie Ihre Lösung aus den Teilproblemen erstellen? Die Aufzählung der Söhne ist meines Erachtens unumgänglich. 2. Sie können einen Knoten mehrmals betreten und verlassen. Während des Zeitfensters

können Sie also andere Scheitelpunkte besuchen, die sich nicht im Teilbaum befinden, der auf

wurzelt . Vielen Dank. :-)

f [a, t, t^{'}]

$f[a, t, t']$

a

$a$

[t, t^{'}]

$[t,t']$

a

$a$

Peng Zhang

Punkt (1) ist nicht so problematisch wie Punkt (2). Damit meine Idee so funktioniert, wie ich sie mir ursprünglich vorgestellt habe, müssen Sie einen Teilbaum nicht mehrmals schließen und erneut eingeben. Es ist nicht offensichtlich, dass die beste Lösung nicht überall um den Baum herumspringt: Besorgt ein Blatt und etwas in der Nähe der Wurzel und geht zu einem Blatt und dann zu einem anderen Blatt, das weit von den anderen 2 entfernt ist usw. Möglicherweise ist dies möglich um die Tatsache auszunutzen, dass Sie alle Knoten auf jedem Pfad erhalten, den Sie gehen. Insbesondere wenn ein Kind besucht wurde, ist das Elternteil bereits besucht.

Joe

: In meinen Gedanken ist Punkt (1) in der Tat ein Problem . Für Punkt (2) nannte ich die Einschränkung "keine erneute Eingabe" als Einschränkung "Tiefensuche". Die DFS-Einschränkung wird häufig in der Literatur verwendet. Und unter dieser Bedingung ist mein Problem tatsächlich polynomisch, solange der maximale Grad des Baums eine Konstante ist . Daher frage ich mich, ob meine Frage NP-schwer ist. Vielen Dank.

Peng Zhang

In Bezug auf die DFS-Einschränkung ist es einfach, ein Beispiel zu erstellen, in dem die optimale Sequenz diese Einschränkung verletzt. Stellen Sie sich einen vollständigen, ausgeglichenen Binärbaum mit 7 Knoten vor. Lassen Sie die 2 Blätter im linken Teilbaum die Fristen 2 und 12 haben, die 2 Blätter im rechten Teilbaum die Fristen 8 und 6 und die internen Knoten die Fristen 100. Sie können alle Knoten besuchen, indem Sie die Blätter in der Reihenfolge 2,6,8 besuchen 12; Jede andere Bestellung verstößt gegen mindestens eine Frist.

mhum

Das Problem, eine konstante Annäherung für diesen Fall zu erhalten oder NP-Hard zu beweisen, ist noch offen, und jedes Ergebnis wäre eine gute Veröffentlichung. Einige Sonderfälle wurden behoben. Ich habe, zusammen mit anderen, einige Teilergebnisse, die spezielle Fälle wie Spinnen und Bäume mit konstanter Höhe lösen. Das allgemeine Problem für Bäume ist jedoch ungelöst.

vgta
quelle