Seite 1 von 1

Alle möglichen maximalen Flüsse berechnen

Verfasst: 23. Sep 2015 11:55
von ToKaM
Ich versuche für ein dem Heiratsproblem ähnlichen Problem bei dem ein perfektes Matching der Kardinalität 1:n berechnet wird auf eine Formel hin zu optimieren.

Die Summe der Abweichungen eines Wertes für jeden Knoten auf der linken Seite (also 1:) von einem Eingabewert (einem Mean), soll minimiert werden. Diese Summe ist der Mittelwert der Matchings des Knotens, wobei für jeden Knoten auf der rechten Seite ein Score besteht.

Ich gehe davon aus, dass die Anzahl der Möglichkeiten einen maximalen Fluss zu berechnen gering sein wird.

Daher tendiere ich dazu das perfekte Matching zu optimieren, indem ich die Formel auflöse für alle möglichen Zuordnungen.

Die Frage ist nun, wie finde ich alle möglichen Zuordnungen?
Lässt sich das über die Menge aller Zyklen im Graphen mit maximalem Fluss finden? Gibt es hierzu Algorithmen? Ich würde gern zum Einen die Anzahl der Möglichkeiten einen maximalen Fluss zu erhalten nach Berechnung eines maximalen Flusses abschätzen, zum anderen diese dann iterativ generieren.


Mich interessiert außerdem ob es bekannte Algorithmen gibt, bei denen Flussnetzwerke zur Laufzeit verändert werden, zum Beispiel durch aktivieren / deaktivieren von Kanten, anpassen von Kapazitäten oder sogar das dynamische aktualisieren von Kosten oder Kapazitäten in Abhängigkeit zum bestehenden Fluss.

Vielen Dank für eventuelle Antworten.

Re: Alle möglichen maximalen Flüsse berechnen

Verfasst: 25. Sep 2015 19:27
von Prof. Karsten Weihe
ToKaM hat geschrieben:Iein perfektes Matching der Kardinalität 1:n
Was ist "Kardinalität 1:n" :?:

KW