Graphentheorie Frage, Java. Welcher Algorithmus zu erreichen, die folgende

https://stackoverflow.com/questions/1805619

05-07-2019
|

Frage

Ich habe ein Diagramm, mit X-Knoten und Y Kanten. Die gewichteten Kanten. Der Punkt ist, an einem Knoten zu starten, und an einem anderen zu stoppen. Jetzt kommt das Problem;

Visualisieren Sie das Problem. Die Kanten sind Straßen, und die Kantengewichte sind die max Gewichtsgrenzen für Fahrzeuge auf den Straßen fahren. Wir möchten, dass die größte LKW möglich von A nach B fahren, damit die maximal zulässige Gewicht für einen LKW, einen bestimmten Weg nimmt das kleinste Gewicht von allen Kanten in diesem Pfad ist. Ich mag das größte zulässige Höchstgewicht für alle Pfade von A nach B

Kann ich irgendeine Art von Dijkstra-Algorithmus für dieses Problem? Ich bin nicht sicher, wie dieses Problem in Form eines Algorithmus zum Ausdruck bringt, dass ich umsetzen kann. Jede Hilfe ist sehr geschätzt.

Update: Getestet habe ich aus Somethings, die nicht für mich arbeiten. Ein Knoten wäre für jede ankommende Kante einen LKW max hat.

Lösung

Dijkstra-Algorithmus sollte funktionieren, aber Ihr „Abstand“ in diesem Fall ist ein bisschen komisch. Ihr „Abstand“ ist die maximale Größe LKW Sie zu einem Knoten erhalten. Nennen wir, dass M [v] für einen Knoten v Sie müssen Knoten, um von der größten M [v], um kleinste M [v] (gegenüber der normalen Dijkstra) verarbeiten und berechnen für jede Kante e von v nach w:.

M[w] = max(M[w], min(e.weight, M[v]))

Andere Tipps

Das klingt (fast) genau wie das maximale Strömungsproblem die gelöst werden kann, effizient zu nutzen die Ford-Fulkerson Algorithmus .

Wie Keith hat in einem Kommentar darauf hingewiesen, Maximum der Algorithmus variiert werden muss leicht finden nur ein Pfad mit maximierter minimalem Pfadsegment, da der LKW kann nicht in mehrere Teile aufgeteilt werden.

Ich glaube, du bist für diese Suche

Kürzester Weg

edit: eigentlich keine Arent Sie, und die maximale Strömungsverbindung korrekt ist

Also, wenn ich das richtig verstehen, Sie fragt, „Was ist die größten Lastwagen sind die von A fahren kann nach B“

Um Dijkstra-Algorithmus anwenden, müssen Sie einen Weg, „Kosten“ zu modellieren. Wenn Sie eine Standard-Implementierung verwenden möchten, können Sie die Umkehrung des Gewichts auf die Kosten zuordnen. Somit ist die höchste Kostenkante derjenige mit dem niedrigsten Gesamtgewicht. Natürlich sind da Sie wahrscheinlich schöne Zahlen wollen, können Sie einfach die Vergleiche ändern, anstatt wirklich die Umkehrungen verwendet wird.

Sie suchen einen [ http://en.wikipedia.org/wiki/Flow_network zu optimieren ] . Die Kapazität ist die maximale Gewichtsgrenze der Straße; und die Strömung ist das Gewicht des LKW.

Sie könnten eine Art Mindest Spanning Tree Ansatz. Verbinden Knoten eine Kante zu einer Zeit, höchster Fluss Kanten zuerst, bis A und B verbunden sind. Die letzte Kante, die Sie das Graphen hinzugefügt ist die niedrigste Flusskante, die Sie überqueren müssen werden von A nach B kommen wahrscheinlich nicht der effizienteste Lösung (O (N ²) worst case) , aber zumindest einfach es ist.

Dies ist weder kürzesten Weg Problem, noch ein max-Flow-Problem. Es ist eigentlich kein Problem. Er erklärte - wollen max Gewicht für alle Pfade A nach B, so dass alle Wege von A nach BFS gehen zu generieren. Für alle Pfade bei B endet erhalten finden min Gewicht der Pfad der Kanten.

Verwenden Dijkstra-Algorithmus mit dem Kehrwert des maximalen LKW Gewicht als Kanten Kosten, und das Maximum der einzelnen Kantengewichte als Gesamtroutenkosten.

d. edge_cost gleich 1 / (maximaler LKW Gewicht erlaubt) die total_cost einer bestimmte Strecke ist das Maximum des einzelnen edge_cost den alle Kanten in der Route.

Verschiedene Antworten oben schlagen einfach Dijkstra-Algorithmus mit einer modifizierten Gewichtungsfunktion. Zum Beispiel w(e) = -c(e) oder ‚w (e) = 1 / c (e)‘, wobei w(e) das Gewicht einer Kante ist, die durch den Algorithmus verwendet, und c(e) ist die Kapazität der Kante in der ursprünglichen Problemformulierung.

Diese nicht funktionieren.

Man kann sich leicht Gegenbeispiele schaffen, dass diese falsche Ergebnisse liefern würde. Betrachten wir zum Beispiel die Grafik:

a---3-->b---3--->c---3-->d
 \                       ^
  \                      |
   \----------3----------|

Nehmen wir den Wert von a ( "Abstand des Knotens a im Algorithmus Formulierung) Null ist. Die zwei Pfade von a zu d sind in diesem Problem äquivalent. Doch wenn wir nur die Randkapazität negieren, Abstand (d), den langen Weg verwendet wird, wird (-3)+(-3)+(-3) = -9 während des kurzen Weges unter Verwendung wäre es -3 werden. Wenn wir die Randkapazität, Abstand (d) mit dem langen Weg inverse würde (1/3)+(1/3)+(1/3)=1, während es nur die kurzen (1/3) würde verwenden.

Was Arbeit Modifizieren des Entspannungsschrittes des Algorithmus, dh anstelle der Verwendung der Funktionen der Zugabe (+) und weniger als (<), mit jeweils Funktionen min und Größer-als ( >), und verwenden Sie einen max-Heap anstelle eines min-Heap. Wir konnten die letzten beiden Änderungen vermeiden, wenn wir die Kantengewichte negieren und verwenden weniger als, aber keine Möglichkeit, können wir vermeiden + ersetzen, da wir einige Betreiber @ brauchen, wo a @ a = a für alle a Werte, während + nur für a=0 funktioniert.

Also, die einzig richtige Antwort, die ich sehe, ist die allererste gegeben, von Keith Randall.

Eine schöne Übung wäre formal zu beweisen, dass der modifizierte Algorithmus korrekt ist. Was muss bewiesen werden soll: -., Wenn der Knoten mit u Maximalwert d(u) zu jeder Schleifeniteration ist, dann ist kein Pfad nicht markierten Knoten beteiligt einen Weg zu schaffen, um u einen Abstand größer als d(u) ergibt

Intuitiv ist es leicht zu sehen, da alle andere nicht markierten Knoten haben Abstand von weniger als (oder gleich) der Abstand von ‚u‘ (weil wir wählen u wie den mit maximalem Abstand), und dem Abstand der erzeugten Pfade durch aufeinanderfolgende Aufrufe von min erzeugt wird, so kann es nur wachsen kleines, nicht größer.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow