Positive topologische Reihenfolge

45

Angenommen, ich habe einen gerichteten azyklischen Graphen mit reellen Zahlengewichten auf seinen Eckpunkten. Ich möchte eine topologische Reihenfolge der DAG finden, in der für jedes Präfix der topologischen Reihenfolge die Summe der Gewichte nicht negativ ist. Oder wenn Sie eine ordnungstheoretische Terminologie bevorzugen, habe ich eine gewichtete Teilreihenfolge und möchte eine lineare Erweiterung, sodass jedes Präfix eine nicht negative Gewichtung hat. Was ist über dieses Problem bekannt? Ist es NP-vollständig oder in polynomieller Zeit lösbar?

ds.algorithms directed-acyclic-graph partial-order David Eppstein
quelle

4

Probieren Sie den Greedy-Algorithmus in diesem Diagramm aus: 1 -> 2 -> 3, 1 -> 4 -> 5, Scheitelpunktgewichte sind 1: +2, 2: -2, 3: +3, 4: -1 5: -2. Der gierige Algorithmus würde mit v1 beginnen, dann v4 wählen und dann hängen bleiben. Die richtige Reihenfolge ist v1, v2, v3, v4, v5.

Robin Kothari

2

"Einige der Frechet-Entfernungsprobleme, die JeffE und andere untersucht haben" - Nette Abstraktion! Zum Vorteil anderer ist hier eine Version: Angenommen, Sie erhalten einen kantengewichteten ebenen Graphen G und zwei Scheitelpunkte s und tn der Außenfläche. Sie möchten einen Grenzpfad von s nach t durch eine Folge von Elementarbewegungen in den anderen umwandeln. Jede Bewegung ersetzt den aktuellen Pfad durch seine symmetrische Differenz mit einer Gesichtsgrenze. Wie schnell können wir die mve-Sequenz finden, die die maximale Länge des sich entwickelnden Pfades minimiert?

Jeffs

3

Tsuyoshi, tut mir leid, ich habe versucht, während des Kommentierens eine neue Zeile einzufügen. Dadurch wurde mein Kommentar abgeschnitten. Die Idee ist also, dass Sie eine Schnur fest um Ihr Handgelenk gebunden haben und wissen möchten, ob Sie sie abwickeln können. Ihr Handgelenk wird als Polygonnetz dargestellt, dessen Zellen Elemente einer Teilreihenfolge sind (früher näher an der Zeichenfolge, später in der Reihenfolge näher an off). Das Gewicht einer Zelle ist der Längenunterschied zwischen ihrer inneren und äußeren Grenze.

David Eppstein

1

@ David: Danke für die Erklärung. Dieses Mal kann ich verstehen, wie es mit der aktuellen Frage zusammenhängt, und es ist interessant!

Tsuyoshi Ito

3

Eine nicht so nützliche, aber unterhaltsame Beobachtung: Dieses Problem entspricht dem Problem der Einzelmaschinen-Sequenzierung mit Fristen und Prioritätsbeschränkungen, bei denen die Verarbeitungszeit für jeden Auftrag negativ sein kann . Bei nicht-negativer Verarbeitungszeit liegt dieses Problem in P (Lawler und Mooer 1969, jstor.org/stable/2628367 ) vor. Wenn eine Lösung vorhanden ist, gibt es eine Lösung, die von der Verarbeitungszeit unabhängig ist. Dies ist eindeutig der Fall, wenn einige Aufträge eine negative Verarbeitungszeit haben.

Tsuyoshi Ito

18

Dieses Problem scheint sehr ähnlich zu SEQUENZIEREN, UM MAXIMALE KUMULATIVE KOSTEN ZU MINIMIEREN, Problem [SS7] in Garey & Johnson . Nämlich:

INSTANZ: Setze von Aufgaben, Teilauftrag auf , "Kosten" für jedes (wenn , kann es als "Gewinn" angesehen werden) und eine konstante . $T$ $\prec$ $T$ $c(t) \in Z$ $t \in T$ $c(t) < 0$ $K \in Z$

FRAGE: Gibt es einen Einprozessor-Zeitplan für , der die Prioritätsbedingungen einhält und der die Eigenschaft hat, dass für jede Aufgabe die Summe der Kosten für alle Aufgaben mit ist höchstens ? $\sigma$ $T$ $t \in T$ $t'$ $\sigma(t') \leq \sigma(t)$ $K$

Ich bin nicht sicher , ob das Problem bleibt NP-vollständig , wenn auf 0 G & J Erwähnung fixiert ist , dass das Problem bleibt NP-vollständig , wenn für all . $K$ $c(t) \in \{-1,0,1\}$ $t \in T$

mhum
quelle

7

Das sieht gut aus. Dann kann man, glaube ich, ohne Einschränkung der Allgemeinheit nehmen, andernfalls einen uneingeschränkten Job mit dem Wert (oder Jobs mit dem Wert ) hinzufügen .

K = 0

$K=0$

c

$c$

- K

$-K$

K

$K$

c

$c$

- 1

$-1$

Daveagp

@mhum: Ich arbeite an einem technischen Bericht über verwandte Ergebnisse und möchte Sie zitieren. Würdest du mir deinen richtigen Namen geben? Wenn Sie möchten, können Sie es mir

per

9

Nun, meine Antwort ist meine Frage, aus der hervorgeht, dass Sie, wenn Sie dieses Problem in P lösen könnten, auch ein anderes offenes Problem lösen könnten: Positive topologische Ordnung, nehmen Sie 3

Bearbeiten: Dieses Problem hat sich auch als NP-vollständig erwiesen, sodass Ihr Problem bereits NP-vollständig ist, wenn Ihre DAG nur zwei Ebenen hat, dh wenn es keine gerichteten Pfade mit zwei Kanten gibt.

domotorp
quelle

3

Wenn ich das Problem richtig verstehe, kann meiner Meinung nach das mit Vorrang verbundene Problem der Einzelmaschinenplanung zur Minimierung der gewichteten Summe der Fertigstellungszeiten (1 | vor | \ sum wc) auf das von Ihnen interessierte Problem reduziert werden. In Aufgabe 1 | prec | \ sum wc haben wir n Jobs mit jeweils einer nicht negativen Gewichtung und einer Bearbeitungszeit, eine Position auf den Jobs und wir wollen eine lineare Erweiterung der Jobs, so dass die gewichtete Summe der Jobabschlusszeiten ist minimiert. Die Probleme sind NP-vollständig, obwohl wir davon ausgehen, dass die Verarbeitungszeit für jeden Auftrag gleich 1 ist. Ist dies sinnvoll?

monaldo
quelle

Es ist definitiv eine interessante Möglichkeit. Aber wie macht man die Reduktion so, dass das Optimierungskriterium (minimale Summe der Fertigstellungszeiten) in Constraints (nicht negative Präfixe) umgewandelt wird?

David Eppstein

Ich kenne dieses NP-Vollständigkeitsergebnis des Planungsproblems nicht, aber ich denke, es bezieht sich auf das Entscheidungsproblem der Entscheidung, ob es eine lineare Erweiterung gibt, so dass die gewichtete Summe der Jobabschlusszeiten höchstens K beträgt, daher denke ich nicht Hierbei ist die Unterscheidung zwischen einem Optimierungskriterium und einer Einschränkung wichtig. Ich habe jedoch nicht verstanden, wie die Beschränkung für die gewichtete Summe der Fertigstellungszeiten im aktuellen Problem dargestellt werden soll.

Tsuyoshi Ito

Ich denke, dass die Reduzierung nicht so einfach ist, wie ich am Anfang gedacht habe. Ich bin mir meiner Antwort nicht mehr sicher.

Monaldo

Ich habe gerade einen Fehler in meinem vorherigen Kommentar festgestellt. Als ich es gepostet habe, dachte ich, dass es einfach ist, eine Beschränkung für die ungewichtete Summe darzustellen (daher die Betonung auf gewichtet ), aber das war völlig falsch.

Tsuyoshi Ito

2

Was ist, wenn wir immer das maximale Element (in der Teilreihenfolge) mit dem geringsten Gewicht nehmen. Nachdem wir die Elemente erschöpft haben, geben wir sie in umgekehrter Reihenfolge als Ausgabe zurück.

Daniel Martin
quelle

Das Problem ist unveränderlich bei der Transformation der Umkehrung der Teilordnung und der Negierung aller Gewichte. Ich verstehe also nicht, wie sich dies von dem vorwärtsgierigen Algorithmus unterscheiden kann, zu dem Robin K in den Kommentaren ein Gegenbeispiel gegeben hat.

David Eppstein

Diese Methode funktioniert jedoch für sein Beispiel: Zuerst wird Scheitelpunkt 5 ausgewählt, dann Scheitelpunkt 4, dann 3, 2 und schließlich 1. Die endgültige Reihenfolge lautet also 1, 2, 3, 4, 5. Tatsächlich ziehe ich an Ich glaube, es ist schwer zu beweisen, dass diese Methode funktioniert. Angenommen, Sie haben eine Lösung, bei der in der letzten Position kein maximales Element (Senke) mit minimalem Gewicht vorhanden ist. Dann können Sie eine andere Lösung finden, die diese Eigenschaft besitzt, indem Sie einfach die Position eines solchen Elements so ändern, dass es von Dauer ist, und den Rest wie er ist beibehalten. Fahren Sie mit der Induktion fort, und Sie erhalten einen formellen Beweis.

Daniel Martin

Ja ... es funktioniert nicht ... 1 -> 2 -> 3, 1 -> 4 mit den Gewichten 4, -7, 6, 3.

Daniel Martin

1

Dieses Problem erinnert mich an viele Entscheidungsbäume. Ich würde diese Art von Lösung in Betracht ziehen, bei der versucht wird, immer den vielversprechendsten Weg einzuschlagen, aber indem man sich den gesamten Teilgraphen ansieht:

Arbeiten Sie sich von Sink Nodes aus schrittweise auf die Quellen zu. Geben Sie dabei jeder Kante ein Gewicht. Dieses Gewicht sollte den Mindestbetrag darstellen, den Sie "bezahlen" müssen, oder Sie "gewinnen", indem Sie den Teilgraphen ab dem Knoten, auf den die Kante zeigt, überqueren. Angenommen, wir befinden uns auf Stufe i + 1 und steigen auf Stufe i auf. Dies ist, was ich tun würde, um eine Gewichtung für eine Kante zuzuweisen, die auf einen Knoten der Ebene i zeigt:

edge_weight = pointing_node_weight.
Finden Sie die Kante beginnend mit "Zeige Knoten" mit dem maximalen Gewicht. Sei dieses Gewicht next_edge_weight.
Kantengewicht + = next_edge_weight

Erstellen Sie dann die Reihenfolge wie folgt:

Sei S die Suchgrenze, dh die Menge der Knoten, aus denen als nächstes ausgewählt werden soll.
Wählen Sie den Knoten so aus, dass (node_weight + maximum_edge_weight) maximiert wird.
Entfernen Sie den Knoten aus dem Graphen und S. Fügen Sie die "Kinder" des Knotens zu S. hinzu.
Wenn das Diagramm nicht leer ist, fahren Sie mit Schritt 1 fort.
Halt.

Die Idee ist, diejenigen Untergraphen zu durchlaufen, die zuerst so viel Gewinn wie möglich bringen, um später die Kosten für die Untergraphen mit negativem Gewicht tragen zu können.

Chazisop
quelle

Positive topologische Reihenfolge

Antworten: