252 Kurseinheit 1 Kapitel4

View all featured content
Cobra

Cobra

Dr Franke Ghostwriter
252 KE1 Kap.4

Hallo,
nachdem ich mich nun todesmutig wieder mit dieser geliebten KE beschaeftigt habe, verstehe ich mal wieder nichts. Okay, das erste ist wohl mal wieder, dass ich den Sinn dieses Kapitels gar nicht verstehe😕.
Bei dem Ford-Fulkerson Algorithmus wird wild gerechnet, nur ich weiss nicht wirklich wie. Woher habe ich denn mein epsilon i?
In Tabelle 4.2 sind die Knoten markiert. Fuer die erste Iteration und Knoten 1,2,3 kann ich noch folgen: Man schaut, wie viel im Maximum zu einem Knoten fliesst. Mit phi ij als Anfangsstaerke ergeben sich dann die Werte. Nur, bei Knoten 4 habe ich dann nur ein epsilon j=3. Warum?
Und warum habe ich im 2. Iterationsschritt nur epsilon j=2?😕😕😕
Danke,
Ulrike
 
Nach Datum sortieren Nach Stimmen sortieren
Cobra schrieb:
Fuer die erste Iteration und Knoten 1,2,3 kann ich noch folgen: Man schaut, wie viel im Maximum zu einem Knoten fliesst. Mit phi ij als Anfangsstaerke ergeben sich dann die Werte. Nur, bei Knoten 4 habe ich dann nur ein epsilon j=3. Warum?
Und warum habe ich im 2. Iterationsschritt nur epsilon j=2?😕😕😕
Zum Vergrößern anklicken....
Hallo Ulrike,

Du musst beim Ford-Fulkerson-Algorithmus bei der Betrachtung eines Knoten durch alle Iterationen immer die Vorgänger und Nachfolger berücksichtigen.

Beispiele:
a) Knoten 4 - 1. Iteration:
Du erreichst diesen Knoten via Knoten 5 mit folgenden Parametern:

[tex]i = 5, \quad j = 4, \quad\epsilon_5 = 3, \quad\phi_{54} = 0, \quad\kappa_{54} = 8 [/tex]

Nun wendest Du die Markierungsvorschrift aus Tabelle 4.1 an. Dann ergibt sich:

[tex]\epsilon_4 = min (\epsilon_5, \quad\kappa_{54} - \phi_{54}) = 3[/tex]

b) Knoten 4 - 2. Iteration:
Analog:

[tex]i = 5, \quad j = 4, \quad\epsilon_5 = 2, \quad\phi_{54} = 3, \quad\kappa_{54} = 8 [/tex]

Dann ergibt sich:

[tex]\epsilon_4 = min (\epsilon_5, \quad\kappa_{54} - \phi_{54}) = 2[/tex]

OK?

Gruß Franz
 
Positive Stimme 0 Negative Stimme
FranzK schrieb:
Hallo Ulrike,

Du musst beim Ford-Fulkerson-Algorithmus bei der Betrachtung eines Knoten durch alle Iterationen immer die Vorgänger und Nachfolger berücksichtigen.

Beispiele:
a) Knoten 4 - 1. Iteration:
Du erreichst diesen Knoten via Knoten 5 mit folgenden Parametern:

[tex]i = 5, \quad j = 4, \quad\epsilon_5 = 3, \quad\phi_{54} = 0, \quad\kappa_{54} = 8 [/tex]

Nun wendest Du die Markierungsvorschrift aus Tabelle 4.1 an. Dann ergibt sich:

[tex]\epsilon_4 = min (\epsilon_5, \quad\kappa_{54} - \phi_{54}) = 3[/tex]

b) Knoten 4 - 2. Iteration:
Analog:

[tex]i = 5, \quad j = 4, \quad\epsilon_5 = 2, \quad\phi_{54} = 3, \quad\kappa_{54} = 8 [/tex]

Dann ergibt sich:

[tex]\epsilon_4 = min (\epsilon_5, \quad\kappa_{54} - \phi_{54}) = 2[/tex]

OK?

Gruß Franz 🙂
Zum Vergrößern anklicken....
Hallo Franz,
aber woher kommt denn das epsilon 5=3 bzw. epsilon 5=2?
Wenn ich den Knoten 2 als Vorgaenger nehmen wuerde, haette ich gar ein kappa von 7.
Sorry, aber ich verstehe schon die Basis nicht.😕😕
Danke,
Ulrike
 
Positive Stimme 0 Negative Stimme
Du fängst mit der Quelle an und bedenkst, das von ihr etwas "heraus kommt" und sie "unerschöpflich" ist, markierst sie also mit (+ ; unendlich)
jetzt schaust du im ersten Schritt, welche "Bäche" (Kanten) zu neuen "Zusammenflüssen" (Knoten) führen
Erreichbar ist als erstes Knoten 3 und zwar können da maximal 6 Einheiten"Wasser" hinfließen, die Markierung des Knoten ist (1+;6) was bedeutet, dass von knoten 1 kommend 6 Einheiten Wasser hinfließen. Der Knoten 1 hat aber auch einen Vorgänger, nämlich Knoten 2, allerdings fließt auf der Kante <1;2> noch nichts, damit kann ich dort den Fluß auch nicht verringern, also keine Markierung.
Knoten 1 ist damit im ersten Iterationsschritt abgeschlossen.

Nun schaust Dir Knoten 3 an
Vorgänger wäre Knoten1, der ist aber schon markiert, also erstmal ignorieren
Nachfolger sind 2 und 5
Zu Knoten 2 dürfen 2 Einheiten fließen, 6 haben wir in Knoten 3 da => es fließen 2 (das ist dieses min{epsilon; kappa-phi})
daraus folgt die Markierung (3+;2) was wieder bedeutet von 3 kommen 2 Einheiten,
analog Knoten5 mit (3+;3) => von K3 kommend mit maximal 3 ME erreichbar
Knoten 3 fertig

So gehst immer weiter, bis du die Quelle erreicht hast, hier wird die Quelle mit (5+;3) markiert ("Durchbruch" zu Quelle). In die Quelle fließen also von K5 3ME. und nun gehst quasi rückwärts. Die Markierung in 5 sagte dir, dass die 3 ME von 3 kamen und bei 3 steht, dass sie von 1 kamen. Damit ist die Flussvergrößerung über 1-3-5-6 mit 3 ME erfolgt.

nun kommt der 2. Iterationsschritt, alle markierungen werden gelöscht und es geht wieder von vorne los. Jetzt könntest du allerdings auch Flüsse von Vorgängern verkleinern, was dann mit dem - dargestellt wird. Außerdem ist nun phi nicht mehr Null:

Quelle wieder (+,unendlich)
Der Bach zu See Nummer 3 fasst 6 Liter Wasser (Kappa=6), aber drei Liter fließen schon (Phi=3) verbleibt ein möglicher Fluß von Kappa-phi=3 Litern Wasser und die sind auch vorhanden, denn
min {unendlich; 3} = 3; jetzt sind also in See Nummer drei zusätzlich 3Liter Wasser von der Quelle 1 (=epsilon) angekommen => Markierung von Knoten 3 mit (1+;3)
usw.

MfG
Thomas
 
Positive Stimme 0 Negative Stimme
Thomas W. schrieb:
du fängst mit der Quelle an und bedenkst, das von ihr etwas "heraus kommt" und sie "unerschöpflich" ist, markierst sie also mit (+ ; unendlich)
jetzt schaust du im ersten Schritt, welche "Bäche" (Kanten) zu neuen "Zusammenflüssen" (Knoten) führen
Erreichbar ist als erstes Knoten 3 und zwar können da maximal 6 Einheiten"Wasser" hinfließen, die Markierung des Knoten ist (1+;6) was bedeutet, dass von knoten 1 kommend 6 Einheiten Wasser hinfließen. Der Knoten 1 hat aber auch einen Vorgänger, nämlich Knoten 2, allerdings fließt auf der Kante <1;2> noch nichts, damit kann ich dort den Fluß auch nicht verringern, also keine Markierung.
Knoten 1 ist damit im ersten Iterationsschritt abgeschlossen.

Nun schaust Dir Knoten 3 an
Vorgänger wäre Knoten1, der ist aber schon markiert, also erstmal ignorieren
Nachfolger sind 2 und 5
Zu Knoten 2 dürfen 2 Einheiten fließen, 6 haben wir in Knoten 3 da => es fließen 2 (das ist dieses min{epsilon; kappa-phi})
daraus folgt die Markierung (3+;2) was wieder bedeutet von 3 kommen 2 Einheiten,
analog Knoten5 mit (3+;3) => von K3 kommend mit maximal 3 ME erreichbar
Knoten 3 fertig

So gehst immer weiter, bis du die Quelle erreicht hast, hier wird die Quelle mit (5+;3) markiert ("Durchbruch" zu Quelle). In die Quelle fließen also von K5 3ME. und nun gehst quasi rückwärts. Die Markierung in 5 sagte dir, dass die 3 ME von 3 kamen und bei 3 steht, dass sie von 1 kamen. Damit ist die Flussvergrößerung über 1-3-5-6 mit 3 ME erfolgt.

nun kommt der 2. Iterationsschritt, alle markierungen werden gelöscht und es geht wieder von vorne los. Jetzt könntest du allerdings auch Flüsse von Vorgängern verkleinern, was dann mit dem - dargestellt wird. Außerdem ist nun phi nicht mehr Null:

Quelle wieder (+,unendlich)
Der Bach zu See Nummer 3 fasst 6 Liter Wasser (Kappa=6), aber drei Liter fließen schon (Phi=3) verbleibt ein möglicher Fluß von Kappa-phi=3 Litern Wasser und die sind auch vorhanden, denn
min {unendlich; 3} = 3; jetzt sind also in See Nummer drei zusätzlich 3Liter Wasser von der Quelle 1 (=epsilon) angekommen => Markierung von Knoten 3 mit (1+;3)
usw.

MfG
Thomas
Zum Vergrößern anklicken....
Hallo Thomas,
Danke fuer Deine ausfuehrliche Erklaerung.
Das heisst dann fuer Knoten 5, dass 3 von Knoten 3 reinfliessen. Da ich aber noch 2 in Knoten 2 habe, kann ich bei der 2. Iteration den Knoten 5 mit (2+,2) markieren. In der 3. Iteration kann ich zwar noch Knoten 3 markieren, da er noch 1 Menge aufnehmen koennte, doch weil die nirgendwo abfliessen koennen, kann ich auch die Senke nicht damit erreichen. Ist das korrekt?
Gruss,
Ulrike
 
Positive Stimme 0 Negative Stimme
Genau, die Markierung von Knoten 5 mit (2+;2) in der zweiten Iteration bedeutet: es fließen zusätzliche 2 Einheiten von Knoten 2 kommend in Knoten 5 hinein. Auch hier gelingt der Durchbruch bis zur Senke (nämlich über Knoten 4)

In der dritten Iteration gibt es dann keinen Durchbruch mehr, weil die Bäche alle verstopft sind. *g*

Eine passende Übungsaufgabe findet sich übrigens in der Klausur von März 2006, Aufgabe 6. Dort geht es darum den Mitarbeiterfluß im Brandfall so zu leiten, dass keine Wege (Türen) verstopft sind. Hier sieht man dann auch sehr schön, dass kürzester Weg und Maximaler Fluß nicht zu identischen Lösungen führen. Ein Teil der Mitarbeiter muss nämlich einen längeren Weg nehmen, um das Gebäude zu verlassen. Wie man in der Praxis das dann den MA vermittelt, ist (glücklicherweise) eine Aufgabe von Orga/Personal und nicht mehr die von uns ORlern *sfg* Ich stelle mir gerade die Rundschreiben vor: ... die Mitarbeiter der Gehaltsstufen X,Y und Z nutzen bitte folgenden Weg .... Qualm und Lichtschein aus angrenzenden Räumen können sie ignorieren. *böse böse*

Thomas
 
Positive Stimme 0 Negative Stimme
Antworten
Oben