Ich versuche eine effiziente Lösung für mein Problem zu finden. Nehmen wir an, ich habe ein positiv gewichtetes Diagramm Gmit 100 Knoten (jeder Knoten ist nummeriert) und es ist ein azyklisches Diagramm. Es kann also keine Kante wie 2,2 oder 2,1 geben. Ich habe eine Liste von Knoten, sagen wir 10 aus dem Diagramm G. Angenommen, jeder dieser Knoten befindet sich auch in einem Array. Ich suche nach einer Möglichkeit, das Gesamtgewicht des kürzesten Pfades von Knoten 1 bis 100 zu finden, das mindestens einen bestimmten (sagen wir 5) dieser Knoten aus dieser Liste durchläuft.
Betrachten Sie zur Vereinfachung ein Diagramm mit 6 Knoten, 0 ... 5, jetzt sind Knoten 1 und 4 als Punkte markiert, an denen wir angeben können, ob sie übergeben werden sollen. Angenommen, vorhandene Pfade sind 0-1-2-5, 0-3-4-5 und 1-4. Nehmen wir nun an, alle Kanten werden mit 5 gewichtet, mit Ausnahme von 3 bis 4 mit 1. Wenn wir einen Algorithmus mit dem kürzesten Pfad ausführen, wird der Pfad 0-3-4-5 im Grunde genommen mit 11 gewichtet. Wenn wir jedoch einen Algorithmus ausführen Geben Sie die Mindestanzahl der angegebenen Punkte an und versuchen Sie es mit der Menge 2. Dann sollte der Algorithmus auf 0-1-4-5 ausgeführt werden, das mit 15 gewichtet ist.
Ich habe so geschrieben
shortestPath(destinationNode, minAmount)
if(destinationNode == srcNode && minAmount < 1)
return 0
else if(destinationNode == srcNode && minAmount > 1)
return INFINITY
int destNo = destinationNode get number
int cost = INFINITY
for (int i = 0; i < destNo; i++)
if (d[i][destNo] != null)
int minimumAmountCount = minAmount;
for (int j = 0; j < marked.length(); j++)
if (marked[j] == i)
minimumAmountCount = minimumAmountCount - 1;
cost = MIN(cost, shortestPath(Node(i), minimumAmountCount);
return cost;
Grundsätzlich rufen wir diesen Algorithmus auf, indem wir unseren Zielknoten und die Mindestanzahl von Knoten aus dieser Liste verwenden. Zunächst möchten wir sicherstellen, dass dies eine rekursive Funktion ist und einen Haltepunkt haben sollte, wenn das übergebene Ziel gleich dem Quellknoten ist (der im Wesentlichen Knoten # 0 ist). Der zweite Fall, den wir überprüfen müssen, ist, ob wir genug besucht haben. Wenn es also weniger als 1 (0 oder negative Zahl) ist, haben wir genug Punkte besucht und 0 zurückgegeben, da der Abstand von Knoten 0 zu Knoten 0 0 wäre Wir haben nicht genug besucht, dann geben wir unendlich zurück, damit der Algorithmus andere Pfade berücksichtigt.
Damit der zurückkehrende Teil funktioniert, müssen wir die Nummer des Zielknotens definieren (wenn wir davon ausgehen, dass wir 100 Knoten haben, wäre dies beim ersten Start Knoten Nr. 99) und die Kosten als unendlich initialisieren.
Dann führen wir eine for-Schleife aus, die von 0 (im Wesentlichen Knoten # 0) bis zu unserer aktuellen Knotennummer beginnt. Dies liegt daran, dass das Diagramm keine Rückwärtskanten enthält. Mithilfe der Knotennummer prüfen wir anhand der Matrix, ob für diese Knoten ein Gewicht vorhanden ist. Wenn es existiert, initialisieren wir eine Variable für unseren aktuellen Mindestbetrag und führen dann eine Schleife aus und prüfen, ob die Quelle zum aktuellen Ziel in der Liste der markierten Knoten enthalten ist. Wenn es markiert ist, verringern wir einfach den Mindestbetrag.
Für den letzten Schritt führen wir die Funktion erneut aus, indem wir das Ziel als aktuelle Quelle und mit dem aktuellen Mindestbetrag ändern.
Aber es scheint sehr teuer zu sein, wenn man bedenkt, dass die Worst-Case-Komplexität der verschachtelten Schleife O (| Node | ^ 2) und die vollständige Wiederholung O (| Node | ^ 2 * | Edges |) benötigt. Gibt es also eine andere effiziente Lösung für dieses Problem?
quelle
Antworten:
Berechnen Sie den kürzesten Pfad zwischen allen Paaren der zwölf speziellen Knoten (Knoten 1, 100 und alle zehn Ihrer bestimmten Knoten) und verwenden Sie diese als Kantenlängen in einem neuen Diagramm, das nur aus diesen zwölf Knoten besteht. Jetzt haben Sie ein Diagramm mit zwölf Knoten und möchten den kürzesten Pfad von 1 bis 100 finden, der mindestens fünf andere Knoten verwendet. Jetzt können Sie Ihren Algorithmus (der meiner Meinung nach nur dynamische Programmierung ist) für dieses Diagramm verwenden, das viel kleiner ist. Die Lösung im neuen Diagramm gibt eine Lösung für das ursprüngliche Diagramm an, die Sie finden können, indem Sie die Kanten in der Lösung im neuen Diagramm durch die kürzesten Pfade ersetzen, die Sie im ersten Schritt berechnet haben.
In Ihrem Beispiel haben wir 4 Knoten im neuen Diagramm. Die Kantenlängen im neuen Diagramm sind: 0-1: 5, 0-4: 6, 0-5: 11, 1-4: 5, 1-5: 10, 4-5: 5. Diese entsprechen den kürzesten Pfaden zwischen den Knoten und im Originaldiagramm. Der kürzeste Pfad mit einem Knoten aus der Liste ist 0-4-5 mit der Länge 11. Wenn Sie nun jede Kante in diesem Pfad durch den im ersten Schritt berechneten Pfad ersetzen, erhalten Sie den Pfad 0-3-4-5 im Original Graph.i j
quelle
Wenn Sie nur 100 Knoten haben und Ihre Bögen angegeben oder einfach zu berechnen sind, machen Sie sich darüber keine Sorgen.
Wenn nicht: Ihr Diagramm ist wahrscheinlich sehr dünn (viel mehr Knotenpaare mit Bögen als ohne Bögen). Verwenden Sie also verknüpfte Listen oder eine andere Datenstruktur, mit der Sie nur Bögen durchlaufen können, ohne Nicht-Bögen überspringen zu müssen. Die Namen solcher Datenstrukturen sind sprachabhängig; verschiedene Arten von Java- oder C # -Listen oder Wörterbüchern, z. B. Hashes in Perl oder assoziative Arrays in PHP.
Ich würde sie verwenden, um eine Zuordnung von Knoten zu Vorwärtsbögen (dh Paaren von Kosten- und Zielknoten) und eine andere von Knoten zu Rückwärtsbögen zu erstellen.
Ich würde zwei weitere zuweisen, um die Abstände von Knoten zu Knoten von jedem Knoten zu jedem Zwischenknoten und von jedem Zwischenknoten zu jedem Knoten zu halten, und sie unter Verwendung des Standardalgorithmus berechnen (Floyd's, auch bekannt als Dijkstra's, oder fälschlicherweise , Warshall's).
Ich würde einen weiteren zuweisen, um die endgültigen Knoten-zu-Knoten-Abstände zu halten, und sie berechnen als für den Zwischenknoten .
quelle