Probleme beim Verständnis einer pseudocode max-flow-Algorithmus zur geometrischen constraint solving
So, ich bin versucht, meinen Weg durch dieses Papier, die in Erster Linie über die Suche nach minimal-dichten Teilgraphen eines gewichteten Graphen (im Rahmen der geometric constraint solving).
Einem dichten Teilgraphen, in dem die Summe der kantengewichte und die Summe der vertex GEWICHTE gleich sind.
Erklärt der Autor, dass dies irgendwie entspricht das max-flow-Algorithmus, und so schlägt er vor, eine variation des standard-max-flow-Algorithmus, die er sagt, ist effizienter für dieses problem. Aber ich bin nicht allzu vertraut mit den Konzepten und ich finde die Beschreibung sehr schwammig. Vielleicht könnte jemand mir helfen mit ihm?
Des Algorithmus ist wie folgt angegeben:
Ich bin schrecklich verwirrt über das, was Sie in Schritt 17 werden soll, wo die Flüsse sind tatsächlich initialisiert, und wie die Vermehrung funktioniert.
Dem Papier gibt ein Beispiel:
Also versuchte ich Schritt durch das Beispiel, aber ich konnte es nicht zu tun, was es soll. Es scheint, wie wenn Sie es Schleifen, das erste mal besucht, e1, v0 und v2, und Etiketten e0 und e2. Dann Besuche e0 und labels v2. Dann Besuche e2, sondern alle Ihre Ecken bereits besucht haben, so dass der Algorithmus tut nichts. Wie kommt es zu erweitern, den Weg?
Vielen Dank im Voraus.
InformationsquelleAutor reveazure | 2011-11-04
Du musst angemeldet sein, um einen Kommentar abzugeben.
, wo die Flüsse sind tatsächlich initialisiert Sie sind nicht – eine Beaufsichtigung durch die Autoren. Davon aus für alle e-und v, die fev ist zunächst null.
wie die Brustvergrößerung Prozess funktioniert Schritt 17 ist spürbar höheren Niveau als der rest der routine. Verstärkung der Pfade sind ein standard Unterthema der maximale Durchfluss, die bedeckt ist von vielen Bachelor-algorithmen Texte.
Betrachten wir ein flow-problem, wo alles, was Gewicht hat 1.
Habe ich noch nicht gezogen
s
undt
. Lassen Sie uns nehmen wir an, wir haben geschoben, um eine Einheit vonc
zub
.Den rückwärts gerichteten Bogen von
b
zuc
erscheint, weil, wir können zwar nicht senden-flow ausb
zuc
im absoluten Sinn, wir können Abbrechen, die eine Einheit geht ausc
zub
, die rechnerisch den gleichen Effekt hat. Der maximale Fluss hat den Wert 2, die wir erkennen, durch die Erhöhung der Pfada -> b -> c -> d
. Das bedeutet nur, drücken Sie eine Einheit ausa
zub
haben, brechen Sie die eine Einheit zub
ausc
, drücken Sie eine Einheit ausc
zud
.Hier einige pseudocode für Schritt 17.
amount
sollte der größte Wert, verursacht keine Rand mehr zu produzieren, als sein Gewicht oder einen Eckpunkt aus, um mehr verbrauchen als sein Gewicht.InformationsquelleAutor horror movie