Alle möglichen maximalen Flüsse berechnen

Moderator: Effiziente Graphenalgorithmen

ToKaM
Windoof-User
Windoof-User
Beiträge: 33
Registriert: 17. Mär 2011 21:20
Kontaktdaten:

Alle möglichen maximalen Flüsse berechnen

Beitrag von ToKaM » 23. Sep 2015 11:55

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.
Hier geht es zu meinem Android Blog.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Alle möglichen maximalen Flüsse berechnen

Beitrag von Prof. Karsten Weihe » 25. Sep 2015 19:27

ToKaM hat geschrieben:Iein perfektes Matching der Kardinalität 1:n
Was ist "Kardinalität 1:n" :?:

KW

Antworten

Zurück zu „Effiziente Graphenalgorithmen“