Auswahl Aktion im Forum Suche Kontakt Für Mitglieder Mathematisch für Anfänger Wer ist Online | |
| Autor |
  Algorithmus von Ford-Fulkerson |
|
Chris311
Aktiv 
Dabei seit: 23.01.2008
Mitteilungen: 6525
Aus: Karlsruhe
 |      Themenstart: 2012-07-06 14:40
|
  
\ Hallo, spricht man bei dem Algorithmus von Ford-Fulkerson von einem primal dualen Algorithmus? Wir haben in der Vorlesung einen Algorithmus kennen gelernt, den wir primal dualer Algorithmus genannt haben. In einer Übungsaufgabe gilt es dann ein Max-Cost-Flow-Problem zu lösen, wobei in jeder Iteration der Inkrementgraph und Augmentationsweg anzugeben sind. Das klingt ja nach Ford-Fulkerson. Allerdings steht dort (edit: in der Übungsaufgabe), dass man das mit dem primal dualen Algorithmus machen soll. Kann jemand helfen? Liebe Grüße Chris
-----------------
Ich höre, und vergesse.
Ich sehe, und erinnere.
Ich handle, und verstehe.
Konfuzius
[ Nachricht wurde editiert von fed am 06.07.2012 14:40:37 ]
|
 Profil
 Quote
 Link |
Skrodde
Aktiv 
Dabei seit: 22.12.2008
Mitteilungen: 114
Aus: Gelsenkirchen
 | Beitrag No.1, eingetragen 2012-07-06 15:53
|
Hallo Chris,
wo genau liegt denn dein Problem? Wenn ihr in der Vorlesung einen Algorithmus mit "Primal Dual Algorithmus" benannt habt und diesen nun anwenden sollt, was ist dir dann unklar?
Viele Graphenalgorithmen arbeiten auf dem Residualgraphen, nicht nur Ford und Fulkerson. Die reine Aufgabe, dass man auf dem Residualgraphen arbeiten und die Augmentationswege angeben soll deutet also noch nicht eindeutig auf einen Algorithmus hin.
Zum grundsätzlichen Thema Primal/Dual: Es gibt in recht vielen Anwendungen zum "Primalen" Problem auch ein "Duales" Problem. So lässt sich solch ein duales Problem zum Beispiel für Lineare Programme formulieren und im Simplex Algorithmus nutzen. Graphentheoretisch gibt es auch viele Beispiele, so ist zum Beispiel das Problem der "Maximalen Clique" dual zum Problem der "Maximalen Unabhängigen Menge".
Gruß, Skrodde
|
Profil
Quote
Link |
xycolon
Senior 
Dabei seit: 11.11.2004
Mitteilungen: 2632
Aus: Herten
 | Beitrag No.2, eingetragen 2012-07-06 16:47
|
Der Ford-Fulkeronson-Algorithmus ist eigentlich nicht Primal-Dual, weil er nur auf dem primalen Problem arbeitet (und während der Laufzeit immer primal feasible bleibt).
Der Beweis der Korrektheit und das Max-Flow-Min-Cut-Problem sind natürlich Dualitätsbeweise und die beiden Primal-Dualen Probleme sind halt Max Flow und Min Cut.
Im Gegensatz dazu ist z.B. der Preflow-Push-Algorithmus primal infeasible aber dual feasible, in dem Sinne ist er ein Dualer Algorithmus.
Man kann natürlich den Ford-Fulkerson-Algorithmus in einem Primal-Dualen Framework benutzen.
gruß,
xycolon
-----------------
"Dieses Lied ist leider nicht verfügbar in ihrem Land. Unsere Antwort kennt ihr sicher: sie heißt Widerstand.
6 Milliarden Terabyte, die Leitung brennt wie nie. Das hier ist kein Klingelstreich, das ist Anarchie."
|
Profil
 www
Quote
Link |
Chris311
Aktiv 
Dabei seit: 23.01.2008
Mitteilungen: 6525
Aus: Karlsruhe
| Beitrag No.3, vom Themenstarter, eingetragen 2012-07-07 14:10
|
Oh, wir hatten doch einen primal-dualen Algorithmus für MFP -.-
-----------------
Ich höre, und vergesse.
Ich sehe, und erinnere.
Ich handle, und verstehe.
Konfuzius
[ Nachricht wurde editiert von Chris311 am 07.07.2012 15:13:17 ]
|
Profil
Quote
Link |
|
Wie unterstütze ich den Matheplaneten mit Geld?
[Neues Thema]