Klausur 17.09.2012 Aufgabe 2a

Hallo,

in der Klausur vom 17.09.2012 ist in Aufgabe 2a der Ford-Fulkerson-Algorithmus durchzuführen.
Es gibt laut Aufgabenstellung eine Quelle und zwei Senken.
Dementsprechend muß man doch eine gemeinsame (letzte) Senke hinzufügen.
Aber welche Kapazitäten hätten dann die von den beiden ursprünglichen Senken zu der nun neu eingeführten Senke führenden Kanten?

Wär die Aufgabenstellung derart, daß es zwei Quellen gibt, so müßte man davor eine gemeinsame Quelle einführen. Die Kapazitäten an den dann von dieser neuen Quell zu den beiden ursprünglichen Quellen führenden Kanten wäre jeweils unendlich.

Gruß.
 
Hi Monique,

ich glaube, darum gehts bei der Aufgabe nicht.
Hier geht es darum zu zeigen, daß es hier einen negativen Zyklus gibt, der dann irgendwann die Kosten gegen NULL tendieren läßt und deswegen für diese Aufgabe nicht taugt... Da aber FF-Algo in unserer EA dran kam, hoffe ich sehr, daß er uns in der Klausur erspart bleibt ;)

Gruß

PS: Hi Monique,
im Parallel-Universum ist das Posten einfacher und wird u.U. sofort beantwortet.
 
Bevor hier etwas schief läuft: es geht nicht um den Ford-Fulkerson-Algorithmus, sondern um den Ford-Algorithmus für kürzeste Wege. Wo sind außerdem Quelle und 2 Senken? Ansonsten alles wie Ottokarotto schon sagte...
 
Anbei mein Vorschlag. Was meint ihr dazu? Ich finde dies schon schwer, einen Alghorimus auf eine Aufgbabe anzuwenden, wenn vorher klar ist, dass dieser nicht funktioniert... IMAG0942.jpg
 
S

Sus_Scrofa

Hi Reschi, klar ist es Ford:

- Voraussetzung für die Anwendung ist ein beliebiges Netzwerk, also auch mit Zyklen
- Es dürfen jedoch keine Zyklen neg. Länge auftreten => sonst läuft der Solver im Kreis

- Ansonsten muss man da systematisch die Nachfolgerknoten suchen => wie im Bsp. 3.4 im Skript. Dein Lösungsansatz ist falsch
 
wie genau sieht der Lösungsansatz dieser Aufgabe denn dann aus? Habe nämlich ein ähnliches Ergebnis und habe ansonsten keine Ahnung, wie ich diese Aufgabe andes angehen sollte
 
S

Sus_Scrofa

Hallo,
sorry => es klappt bei mir irgendwie nicht mit dem Hochladen.

Mit einem Satz zu dieser Logik => suche immer wieder die kürzesten Wege vom Startknoten 0 zu dem jeweiligen Knoten (= also zum 1,2,3,4,5).

Du läufst dann irgendwann mal im Kreis (1,2,3) und machst Erträge. So, und so läuft der Solver-Algo im Kreis und das ist das Problem.

Das ist genau das, was der Lehrstuhl sehen möchte => beim Ford dürfen keine negativen Zyklen vorkommen, sonst: :eek: :eek: :eek:
 
hmm.....diese Problematik bei dieser Aufgabe ist mir irgendwie klar. Werde mal versuchen in den nächsten Tagen meine Lösung hochzuladen. Die kürzesten Wege werden durch den Zyklus immer geringer, auch das ist mir klar. Naja ich probiere mich nochmals an dieser Aufgabe und schau mal, ob ich doch nochmal was anderes herausbekomme ;) Danke für deine Erläuterung
 
Ich hatte es bisher so verstanden, dass man beim negativen Zyklus nicht weiter machen kann, weil man immer im Kreis läuft.
In den Lösungshinweisen steht aber "Die Bewertung des Knotens 2 in der 5. Iteration und der Knoten 3 und 4 wird weiter reduziert, was durch den negativen Zyklus erklärt ist. Das Verfahren bricht also nicht ab" Ich kann also doch im Kreis laufen und mich unendlich verbessern?
Ergibt für mich keinen Sinn.
 
Hi blue85,

das tatsächlich so, daher heißt es in der Aufgabe auch wann man aufhören soll, ansonsten würde man sich weiter verbessern:)

Glg Aida
 
Top