Topologische Sortierung mit einer Zielfunktion

Question

Ich habe eine DAG mit N Knoten, d. H. 1, 2, ..., N, und jeder Knoten hat ein Gewicht (wir können es Zeit nennen) x_1, x_2, ..., x_N. Ich möchte eine topologische Sortierung durchführen, aber die Schwierigkeit besteht darin, dass ich beim Sortieren eine Zielfunktion habe. Meine Zielfunktion ist die Minimierung der Gesamtzeit zwischen mehreren Knotenpaaren.

Zum Beispiel habe ich eine DAG mit 6 Knoten, und ich möchte eine bestimmte topologische Sortierung so dass (1,3) + (2,4) minimiert wird, wo (A,B) die Zeit zwischen zwei Knoten A und B. Zum Beispiel zeigt, wenn wir eine Art [1, 6, 3, 2, 5, 4, 7], (1,3) = x_6 und (2,4) = x_5. Basierend auf der DAG, möchte ich eine Sortierung finden, die (1,3) + (2,4) minimiert.

Ich habe eine Zeit lang dieses Problem nachgedacht. Generieren Sie alle möglichen topologischen Sortierungen (Referenz link) und berechnen Sie die Zielfunktion eins nach dem anderen ist immer eine mögliche Lösung, aber es dauert zu lange, wenn N groß ist. Ich war auch Zweig gebundene Beschneidung vorgeschlagen zu verwenden, wenn alle möglichen Arten zu erzeugen (Ich bin nicht sehr vertraut Zweig gebunden, aber ich denke, das wird nicht dramatisch, die Komplexität reduzieren).

Jeder (optimale oder heuristische) Algorithmus für diese Art von Problem? Es wäre perfekt, wenn der Algorithmus auch auf andere Zielfunktionen angewendet werden könnte, wie zum Beispiel die Minimierung der Gesamtstartzeit für einige Knoten. Jeder Vorschlag wird geschätzt.

PS: Oder ist es alternativ möglich, dieses Problem als ein lineares ganzzahliges Optimierungsproblem zu formulieren?

Answer 1

Eine Möglichkeit, dies zu lösen, ist wie folgt:

Zunächst laufen wir All-Pairs kürzesten Weg Algorithmus Floyd-Warshall. Dieser Algorithmus kann in essentially 5 lines of code und es läuft in O(V^3) Zeit codiert werden. Er erzeugt die kürzesten Wege zwischen jedem der Knotenpaare in dem Graphen, d. H. Er erzeugt eine VXV-Matrix von kürzesten Wegen als seine Ausgabe.

Es ist trivial, diesen Algorithmus zu ändern, so dass wir auch die Anzahl der Scheitelpunkte in jedem der O(N^2) Pfade erhalten können. Jetzt können wir alle Pfade eliminieren, die weniger als N Ecken haben. Für die verbleibenden Pfade ordnen wir sie nach ihren Kosten an und testen dann jeden von ihnen, um zu sehen, ob die topologische Sortiereigenschaft nicht verletzt wird. Wenn diese Eigenschaft nicht verletzt wird, haben wir unser gewünschtes Ergebnis gefunden. Der letzte Schritt, d.h. das Testen der topologischen Sortierung, kann in O (V + E) für jeden der O (V^2) -Wege durchgeführt werden. Dies ergibt die Worst-Case-Laufzeit von O(V^4). Doch in der Praxis soll dies schnell sein, weil Floyd-Warshall sehr Cache gemacht werden kann freundlich und wir würden nur einen Bruchteil von O (N^2) Wegen in der Realität testen. Wenn Ihre DAG nicht dicht ist, können Sie möglicherweise auch topologische Tests mit geeigneten Datenstrukturen optimieren.

Answer 2

Hier ist eine Idee:

Der Einfachheit halber zunächst annehmen, dass Sie ein einzelnes Paar haben zu optimieren (I auf den allgemeinen Fall äußern werde später) und nehme an, Sie bereits Ihr Diagramm in ein sortiert haben topologisch Array.

das Array Segment Nehmen am unteren beginnend (in Bezug auf Ihre topologischen Reihenfolge) Knoten des Paares, sagen l, und bei dem höheren Knoten enden, sagen h. Errechne für jeden einzelnen Knoten, der zwischen l und h sortiert ist, ob er von unten durch l begrenzt ist und/oder von oben durch h begrenzt ist.Sie können die vorherige Eigenschaft berechnen, indem Sie Knoten in einem "aufwärts" BFS von l markieren, schneiden an Knoten sortiert über h; und ähnlich letzteres durch Markieren in einem "Abwärts" -BFS von h, Schneiden an Knoten sortiert unter l. Die Komplexität beider Passagen ist O (B * L), wobei B der Verzweigungsfaktor ist und L die Anzahl der Knoten ist, die ursprünglich zwischen l und h sortiert sind.

nun alle Knoten, die nicht begrenzt sind, von oben durch h oberhalb h bewegt werden, und alle Knoten, die von unten her begrenzt sind, nicht durch l kann unter l (die beiden Sätze überlappen können,) alle ohne Verletzung der bewegt werden topologische Sortierung des Arrays, vorausgesetzt, dass die ursprüngliche sortierte Reihenfolge innerhalb jeder Gruppe von Knoten, die nach oben oder nach unten verschoben wurden, erhalten bleibt.

Dasselbe Verfahren kann auf beliebig viele Paare angewendet werden, vorausgesetzt, dass die Segmente, die sie aus der ursprünglichen Sortierreihenfolge schneiden, nicht überlappen.

Wenn zwei Paare sich überlappen, sagen wir (l1, h1) und (l2, h2), so dass z.B. l1 < l2 < h1 < h2 in der ursprünglichen Reihenfolge sortiert, haben Sie die folgenden zwei Fälle:

1) Im trivialen Fall, in dem h1 und l2 passieren in der topologischen Ordnung in keinem Zusammenhang sein, dann sollten Sie Lage sein, die zwei Paare meist unabhängig voneinander zu optimieren, die Anwendung nur einige Sorgfalt entweder l2h1 oben oder unten h1l2 zu bewegen (aber nicht zB h1l1 unten, wenn das sollte möglich erweisen.)

2) Wenn l2 < h1 in der topologischen Ordnung, Sie beide Paare als einziges Paar behandeln können (l1, h2) und dann möglicherweise das Verfahren gelten noch einmal zu (l2, h1).

Da es nicht klar ist, was der gesamte Prozess im nicht-triviale überlappende Fall zu erreichen, vor allem, wenn Sie kompliziertere überlappende Muster haben, kann es sich als besser sein alle Paare gleichmäßig zu behandeln, unabhängig davon, überlappen. In diesem Fall kann die Reihenfolge wiederholt verarbeitet werden, während jeder Lauf eine Verbesserung gegenüber der vorherigen ergibt (ich bin nicht sicher, ob die Prozedur in Bezug auf die Zielfunktion monoton ist - wahrscheinlich nicht.)