Algorithmus - Wertauswahl in Spalten (max 1 Wert pro Zeile) -> Kriterium: kleinste Maximumfunktion d. ausgewählten We
-
Wie seht ihr die Chancen, dass man diese Aufgabe mit einem Programm in halbwegs ansehnlicher Zeit meistern kann?
Glaubt ihr, dass für sowas bereits ein Algorithmus existiert?
Wenn nein, kommt ein gewifter Programmierer auf sowas drauf, oder muss man da schon Mathematikgenie sein?
Lg, Borkert
-
Ja, ich denke schon, dass sich das machen lässt. Vermutlich auch mit einem ähnlichen Vorgehen. Das Problem lässt sich nämlich als Matching-Problem formulieren, indem man für jede Zeile und jede Spalte einen Knoten anlegt, diese paarweise miteinander verbindet, dabei bekommt die Kante ij, die den Knoten von Zeile i mit dem Knoten von Spalte j verbindet als Gewicht den Wert, der an der Stelle in der Matrix steht.
Die Bedingung, dass Du in jeder Spalte genau einen Eintrag auswählen willst und in jeder Zeile maximal einen, bedeutet genau, dass Du ein kardinalitätsmaximales Matching suchst. siehe hier
Allerdings ist das Gewicht, das Du optimieren möchtest nicht die Summe der Gewichte der Matching-Kanten, sondern deren Maximum. Sowas nennt sich Bottleneck-Matching. Anscheinend funktioniert die ungarische Methode dort auch: http://www.springerlink.com/content/701x4v30rw4065kp/, zumindest kann man das dem preview entnehmen. Könnte ich aber ggf. auch morgen noch nachschauen.
Achja, falls es beim googlen hilft: Matchings-Probleme heißen manchmal auch Assignment problems.
Eine ganz einfache Möglichkeit das ganze zu lösen geht wie folgt:
Du sortierst die Kantengewichte aufsteigend (ich nehme mal an, die sind alle größer als 0). Dann fügst Du solange von der leichtesten bis zur schwersten die Kanten hinzu, bis es ein Matching gibt, bei dem alle Deine Spalten-Knoten gematcht werden. Das Gewicht der letzten hinzugefügten Kante ist dann gleich auch der Wert des Bottlenecks. Das Matching-Problem an sich ist dann ungewichtet und kann entweder mit den Standard-Algorithmen dafür oder auch mit der ungarischen Methode gelöst werden. Die Laufzeit ist nicht super, aber immerhin polynomiell. Mit Tricks wie das bereits berechnete Matching beibehalten und nur schaun ob sichs vergrößeren lässt etc. dürfest Du bei ner Laufzeit von O(mn+m log m) rauskommen. Dabei ist n die Anzahl der Knoten, m die Anzahl der Kanten. Bei Dir also: n: Anzahl Zeilen + Anzahl Spalten, m: Anzahl Zeilen * Anzahl Spalten.
-
btw. du willst das nicht wirklich in excel machen, oder?
-
@ Jester
Wow, vielen Dank für deine Antwort. Für mich als Laie ist das erst mal ziemlich harter Tobak, da ich eine vielzahl der von dir verwendeten Begriffe gar nicht kenne. Ich werde aber versuchen, die von dir geposteten Links zu lesen und soweit wie möglich zu verstehen.
Bzgl. Excel:
Nun, da ich den Algorithmus hauptsächlich mit Daten aus Excel-Tabellen anwenden muss, liegt es nahe, VBA-Makros zu verwenden. Aber ich bin auch für alle anderen Möglichkeiten offen!Lg, Borkert
-
Ich würde Dir empfehlen das mit Hilfe einer externen Bibliothek zu lösen. Das gibt's sicher für viele Sprachen. Mit C++ sollte es jedenfalls recht einfach sein. Die boost::graph-library enthält ein fertiges Paket für Matchings. Damit sparst Du Dir die komplette-Matching-Implementierung... letztlich müßtest Du also nur noch die Zahlen sortieren, eine nach der anderen als Kante eintragen und die fertige Matching-Funktion aufrufen. Abbrechen, sobald die Matching-Größe das erste mal die Spaltenanzahl erreicht. Dann das gefundene Matching ausgeben.
Wenn Du nämlich den Matching-Algorithmus auch noch selbst implementieren willst wirds ein bißchen aufwendiger... nicht, dass das nicht zu schaffen wäre, aber es kostet sicher ne Menge Zeit.
-
Danke für die Tipps!!
Leider habe ich nicht wirklich viel Programmiererfahrung...
Habe mein Wissen in den letzten Wochen um ein Mehrfaches gesteigert, doch wird es für deinen Vorschlag wohl nicht ausreichen. Aber ich werde dran bleiben!Lg, Borkert
-
Jester schrieb:
Allerdings ist das Gewicht, das Du optimieren möchtest nicht die Summe der Gewichte der Matching-Kanten, sondern deren Maximum. Sowas nennt sich Bottleneck-Matching. Anscheinend funktioniert die ungarische Methode dort auch: http://www.springerlink.com/content/701x4v30rw4065kp/, zumindest kann man das dem preview entnehmen. Könnte ich aber ggf. auch morgen noch nachschauen.
Das wäre sehr nett!
Lg, Borkert
-
Hm, von hier aus komm ich leider auch nicht dran. Aber was großartig anderes als das was ich oben vorgeschlagen habe werden die auch nicht machen. Allerdings wirst Du ohne Programmierkenntnisse wohl wirklich nicht weit kommen.
boost bietet immerhin http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/maximum_matching.html als Subroutine, damit erschlägst Du das halbe Problem. Andererseits ist natürlich der Einarbeitungsaufwand von C++ und boost::graph auch nicht zu verachten...
-
@Jester
Danke für den Link.
-
Danke für eure Hilfe! Ich habs probiert, mich einzuarbeiten, aber ich habe im Moment leier nicht die erforderlichen Ressourcen.
Sehr schade!
Lg, Borkert