Das Finden der Pfad mit der maximalen minimalem Gewicht

https://stackoverflow.com/questions/873126

22-08-2019
|

Frage

Ich versuche, einen Algorithmus zu trainieren, um einen Weg über einen gerichteten Graphen zu finden. Es ist kein herkömmlicher Weg und ich kann nicht alle Verweise auf so etwas wie dies geschah schon finden.

Ich möchte den Weg finden, die die maximale Mindestgewicht hat.

d. Wenn es zwei Pfade mit Gewichten 10-> 1-> 10 und 2-> 2> 2, dann wird der zweite Pfad als besser als die ersten, da das Mindestgewicht (2) größer als das Mindestgewicht der ersten (1 ).

Wenn jemand einen Weg herauszufinden, dies zu tun, oder zeigen Sie mir nur in die Richtung einiger Referenzmaterial wäre es unglaublich nützlich sein:)

EDIT :: Es scheint, ich vergaß zu erwähnen, dass ich von einem bestimmten Scheitelpunkt zu einer anderen speziellen Ecke zu bekommen bin versucht. Ganz dort wichtiger Punkt: /

EDIT2 :: Als jemand unten darauf hingewiesen, sollte ich betonen, dass Kantengewichte sind nicht negativ.

Lösung

Verwenden Sie entweder Prim oder Kruskals Algorithmus. sie einfach modifizieren, so dass sie nicht mehr, wenn sie herausfinden, dass die Eckpunkte Sie fragen verbunden sind.

EDIT: Sie bitten um maximales Minimum, aber Ihr Beispiel sieht aus wie Sie Minimum Maximum wollen. Im Fall einer maximalen Mindest wird Kruskals Algorithmus nicht funktionieren.

EDIT: Das Beispiel ist in Ordnung, mein Fehler. Nur Prim-Algorithmus wird dann arbeiten.

Andere Tipps

Ich bin Kopieren diese Antwort und auch das Hinzufügen Hinzufügen meines Korrektheitsbeweises für den Algorithmus:

würde ich einige Varianten rel="noreferrer">. Ich nahm den Pseudo-Code unten direkt aus Wikipedia und nur 5 kleine Dinge geändert:

Umbenannt dist width (aus Zeile 3 auf)
wird jedes width Initialized -infinity (Linie 3)
Initialisiert die Breite der Quelle infinity (Linie 8)
Stellen Sie das Zielkriterium -infinity (Zeile 14)
Verändert die Update-Funktion und Zeichen (Zeile 20 + 21)

1  function Dijkstra(Graph, source):
2      for each vertex v in Graph:                                 // Initializations
3          width[v] := -infinity  ;                                // Unknown width function from 
4                                                                  // source to v
5          previous[v] := undefined ;                              // Previous node in optimal path
6      end for                                                     // from source
7      
8      width[source] := infinity ;                                 // Width from source to source
9      Q := the set of all nodes in Graph ;                        // All nodes in the graph are
10                                                                 // unoptimized – thus are in Q
11      while Q is not empty:                                      // The main loop
12          u := vertex in Q with largest width in width[] ;       // Source node in first case
13          remove u from Q ;
14          if width[u] = -infinity:
15              break ;                                            // all remaining vertices are
16          end if                                                 // inaccessible from source
17          
18          for each neighbor v of u:                              // where v has not yet been 
19                                                                 // removed from Q.
20              alt := max(width[v], min(width[u], width_between(u, v))) ;
21              if alt > width[v]:                                 // Relax (u,v,a)
22                  width[v] := alt ;
23                  previous[v] := u ;
24                  decrease-key v in Q;                           // Reorder v in the Queue
25              end if
26          end for
27      end while
28      return width;
29  endfunction

Einige (handwaving) Erklärung, warum dies funktioniert: Sie mit der Quelle starten. Von dort aus haben Sie unendliche Kapazität auf sich. Nun überprüfen Sie alle Nachbarn der Quelle. Angenommen, die Kanten haben nicht alle die gleiche Kapazität (in Ihrem Beispiel, sagen (s, a) = 300). Dann gibt es keinen besseren Weg, b dann über (s, b) zu erreichen, so dass Sie wissen, die beste Fall Kapazität von b. Weiter geht es zu den besten Nachbarn der bekannten Menge von Knoten gehen, bis Sie alle Ecken erreichen.

Der Nachweis der Korrektheit des Algorithmus:

An jedem Punkt in dem Algorithmus, wird es 2 Sätze von Eckpunkten A und B . Die Scheitelpunkte in A werden die Vertices werden, auf die die korrekte maximale Mindestkapazität Pfad gefunden wurde. Und Satz B hat Eckpunkte, auf die wir keine Antwort gefunden haben.

Induktiv Hypothese : Bei jedem Schritt werden alle Eckpunkte in der Serie A haben die richtigen Werte von maximal ihnen Mindestkapazität Weg. dh., werden alle vorherigen Iterationen korrekt sind.

Die Korrektheit der Basisfall : Wenn die Menge A hat nur den Scheitelpunkt S. Dann wird der Wert S ist unendlich, was richtig ist.

In der aktuellen Iteration setzen wir

val [W] = max (val [W], min (val [V], width_between (V-W)))

Induktiv Schritt : Angenommen, W ist der Scheitelpunkt in der Serie B mit der größten val [W]. Und W aus der Warteschlange aus der Warteschlange entfernt und W die Antwort val [W] eingestellt wurde.

Nun müssen wir zeigen, dass jeder zweiter S-W Weg eine Breite <= val [W]. Dies wird immer wahr, weil alle anderen Möglichkeiten von W erreicht durch einen anderen Eckpunkt gehen (nennen wir es X) in der Gruppe B.

Und für alle anderen Ecken X in der Serie B, val [X] <= val [W]

So ein beliebiger anderer Pfad zu W wird durch val [X] eingeschränkt werden, die nie mehr als val ist [W].

So ist die aktuelle Schätzung von val [W] ist optimal und daher berechnet Algorithmus die korrekten Werte für alle Ecken.

Sie können auch die „binäre Suche auf die Antwort“ Paradigma verwenden. Das heißt, tut eine binäre Suche auf den Gewicht, für jedes Gewicht Prüfung w ob Sie einen Pfad in der Grafik nur Kanten von Gewicht von mehr als w Verwendung finden können.

Der größte w für die Sie (durch binäre Suche gefunden) gibt die Antwort. Beachten Sie, dass Sie nur überprüfen müssen, ob ein Pfad vorhanden ist, so dass nur ein O (| E |) Breite beginn / Tiefensuche, kein kürzesten Weg. So ist es O(|E|*log(max W)) in allem, vergleichbar mit dem Dijkstra / Kruskal / Prim O(|E|log |V|) (und ich kann nicht sofort einen Beweis für diejenigen sehen, auch).

Diese gelöst werden kann, einen BFS-Stil-Algorithmus, jedoch benötigen Sie zwei Varianten:

Anstatt jeden Knoten als „besucht“ markiert, können Sie es mit dem Mindestgewicht auf dem Weg markieren Sie es zu erreichen nahm.

Wenn beispielsweise I und J Nachbarn sind, hat I-Wert w1, und das Gewicht der Kante zwischen ihnen ist, w2, dann J = min (w1, w2).

Wenn Sie einen markierten Knoten mit dem Wert w1 erreichen, könnte man zu bemerken muß und es erneut verarbeiten, wenn Sie einen neuen Wert w2 zuweisen (und w2> w1). Dies ist erforderlich, um sicherzustellen, dass Sie das Maximum aller Minimalwerte bekommen.

Zum Beispiel, wenn ich und J Nachbarn sind, ich Wert w1 hat, hat J-Wert w2, und das Gewicht der Kante zwischen ihnen ist w3, dann, wenn min (W2, W3)> w1 müssen Sie bemerken, J und Prozess all seine Nachbarn wieder.

Ich bin nicht sicher, dass Prim hier funktionieren wird. Nehmen Sie dieses Gegenbeispiel:

V = {1, 2, 3, 4}

E = {(1, 2), (2, 3), (1, 4), (4, 2)}

weight function w:
  w((1,2)) = .1, 
  w((2,3)) = .3
  w((1,4)) = .2
  w((4,2)) = .25

Wenn Sie anwenden Prim den maxmin Weg von 1 bis 3 zu finden, die ab dem 1. den 1 --> 2 --> 3 Pfad auswählen, während der maxmin Abstand für den Weg erreicht wird, die durch 4 geht.

Ok, meine eigene Frage zu beantworten hier nur um zu versuchen und ein wenig Feedback bekommt ich auf der vorläufigen Lösung hatte ich vor Posting hier gearbeitet:

Jeder Knoten speichert ein „Pfadfragment“, das ist der ganze Weg zu sich selbst so weit.

0) gesetzt aktuellen Scheitelpunkt zum Startecke
1) Erzeuge alle Pfad Fragmente von diesem Scheitelpunkt und diese in einer Prioritätswarteschlange
2) Nehmen Sie das Fragment aus der Spitze aus der Prioritäts-Warteschlange, und stellt den aktuellen Scheitelpunkt zu Scheitelpunkt der Endung des Weges
3) Wenn der aktuelle Scheitelpunkt der Zielscheitelpunkt ist, dann wieder den Weg
4) goto 1 |

Ich bin mir nicht sicher, dass dies obwohl der beste Weg finden, denke ich, die Ausgangsbedingung in Schritt drei ein wenig ambitioniert ist. Ich kann nicht glauben, eine bessere Ausgangsbedingung obwohl, da dieser Algorithmus nicht in der Nähe Ecken hat (ein Knoten kann in so viele Pfad Fragmente referenziert werden, wie es mag) Sie können nicht einfach warten, bis alle Ecken geschlossen sind (wie Dijkstra für Beispiel)

Sie können nach wie vor Dijkstra! Verwenden

Stattdessen + verwenden, verwenden Sie die min () Operator.
Darüber hinaus sollten Sie den Heap / priority_queue so orientieren, dass die größten Dinge auf der Oberseite sind.

So etwas sollte funktionieren: (ich habe wahrscheinlich einige Details der Implementierung verpasst)

let pq = priority queue of <node, minimum edge>, sorted by min. edge descending
push (start, infinity) on queue
mark start as visited
while !queue.empty:
   current = pq.top()
   pq.pop()
   for all neighbors of current.node:
      if neighbor has not been visited
          pq.decrease_key(neighbor, min(current.weight, edge.weight))

Es ist sichergestellt, dass, wenn Sie zu einem Knoten erhalten Sie einen optimalen Weg gefolgt (da Sie alle Möglichkeiten, in absteigender Reihenfolge zu finden, und man kann nie Ihren Weg verbessern, indem eine Kante hinzufügen)

Die Zeitschranken sind die gleichen wie Dijkstra -. O (Vlog (E))

EDIT: oh warten, das ist im Grunde, was Sie auf dem Laufenden. LOL.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow