Algorithmus - Wertauswahl in Spalten (max 1 Wert pro Zeile) -> Kriterium: kleinste Maximumfunktion d. ausgewählten We

[Borkert]

Hi!

Ich habe eine Matrix mit beliebig vielen Spalten und beliebig vielen Zeilen (Anzahl der Spalten =< Anzahl der Zeilen; Also meist gibt es um ein Vielfaches mehr Zeilen als Spalten).

Ich soll durch einen Rechenvorgang aus jeder Spalte einen Zellenwert berechnen, der ein bestimmtes Kriterium erfüllt, wobei ich aus jeder Zeile nur einen Wert auswählen darf (logischerweise gibt es meistens auch Zeilen, in denen gar kein Wert ausgewählt wurde).

Das Kriterium ist, dass die Maximum-Funktion der ausgewählten Werte minimal sein sollte.

Für ein ähliches Kriterium kenne ich bereits einen Algorithmus, nämlich die Ungarische Methode oder die Munkres Methoden. Nur ist bei diesen Funktionen das Kriterium nicht, dass die Maximum-Funktion der ausgewählten Werte minimal sein soll, sondern die Summen-Funktion der ausgewählten Werte sollten minimal sein.

Bei meiner Fragestellung macht die Summenfunktion aber weniger Sinn als die Maximum-Funktion, weil es um Entfernungen geht. Und die Lösung gewählt werden soll, die mit der kleinsten Entfernung auskommt.

Habe es schon mit Brute-Force-Methoden probiert, nur leider kommt mein Computer bald ans Ende seiner Kapazitäte, weil bei größeren Matritzen extrem viele Rechenoperationen nötig werden.

Hier eine Beispielmatrix mit Bruteforce:

11-21-32
45-23-46
12-67-43
36-86-49

Alle möglichen Maximum-Funktionen (in jeder Spalte der optimalste Wert ausgewählt, mit der Vorgabe, dass in jeder Zeile nur ein Wert ausgewählt werden darf.

max(11,23,43) = 43
max(11,23,49) = 49
max(11,67,46) = 67
max(11,67,49) = 67
max(11,86,46) = 86
max(11,86,43) = 86
max(45,86,32) = 86
max(45,86,43) = 86
max(45,21,43) = 45
max(45,21,49) = 49
max(45,67,32) = 67
max(45,67,49) = 67
max(12,21,46) = 46
max(12,21,49) = 49
max(12,23,32) = 32
max(12,23,49) = 49
max(12,86,32) = 86
max(12,86,46) = 86
max(36,21,46) = 46
max(36,21,43) = 43
max(36,23,32) = 36
max(36,23,43) = 43
max(36,67,32) = 67
max(36,67,46) = 67

Hier gibt es eine eindeutige Lösung, da das kleinste Maximum (32) nur bei einer Kombination rauskommt:
max(12,23,32) = 32

Es gibt bei solchen Aufgabenstellungen aber nicht immer eine eindeutige Lösung, gerade wenn die Matrix viele Spalten bzw. und Zeilen hat.
Da spielt es auch keine Rolle, dass die Zahlen in meinen Matrizen meist 8 Dezimalstellen haben (bei den Summen führt dies meist zu eindeutigen Ergebnissen), da bei den Maximumfunktionen ja die gleiche Zahl mehrmals ausgegeben werden kann.

Falls mehrere Kombinationen das gleiche, minimale Maximum haben, sollte die Funktion trotzdem die optimalste Kombination ausgeben:

max(12,23,32) = 32
max(10,23,32) = 32
max(10,30,32) = 32
max(12,22,32) = 32
max(13,22,32) = 32

Um dies leichter zu gestalten, könnte man hier wieder die kleinstmögliche Summe (Munkres, Ungarische Methode) wählen.

sum(12,23,32) = 67
sum(10,23,32) = 65
sum(10,30,32) = 72
sum(12,22,32) = 66
sum(13,22,32) = 67

Das optimalste Ergebnis mit der Summe 65 wäre hier also sum(10,23,32).

Die von mir gesuchte, optimalste Lösung ist aber auch hier wieder nicht die kleinstmögliche Summe, sondern weiterhin das kleinstmögliche Maximum (Erklärung folgt).

Dabei soll das vorherige kleinstmögliche Maximum (32) ignoriert werden und von den restlichen Werten das kleinstmögliche Maximum genommen werden.

max(12,23) = 23
max(10,23) = 23
max(10,30) = 30
max(12,22) = 22
max(13,22) = 22

Kommen wieder mehrere optimale Ergebnisse heraus (hier max(12,22) und max(13,22) ), solle wiederum das kleinstmögliche Maximum als Kriterium genommen werden.
Auch hier soll das vorherige kleinstmögliche Maximum (22) ignoriert werden.

max(12) = 12
max(13) = 13

Jetzt haben wir ein eindeutiges Ergebnis:

12,22,32

Hoffe, ihr könnt verstehen, was ich meine.

Lg, Borkert

[Jester]

Borkert schrieb:

Ich soll durch einen Rechenvorgang aus jeder Spalte einen Zellenwert berechnen, der ein bestimmtes Kriterium erfüllt, wobei ich aus jeder Zeile nur einen Wert auswählen darf (logischerweise gibt es meistens auch Zeilen, in denen gar kein Wert ausgewählt wurde).

Nein, das ist nicht logisch. Oder wählst Du auch in jeder Spalte höchstens einen Wert aus?

[Borkert]

Borkert schrieb:

Ich soll durch einen Rechenvorgang aus jeder Spalte einen Zellenwert berechnen, der ein bestimmtes Kriterium erfüllt, wobei ich aus jeder Zeile nur einen Wert auswählen darf (logischerweise gibt es meistens auch Zeilen, in denen gar kein Wert ausgewählt wurde).

Ja, stimmt, aus jeder Spalte muss (bzw. darf nur) ein Wert ausgewählt werden.
Hätt ich oben besser formulieren können.
Mfg,
Borkert

P.S.: Wenn euch der Munkres-Algorithmus interessiert, könnt ihr gerne hier nachschauen: http://www.office-loesung.de/ftopic258149_0_0_asc.php

[Borkert]

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

[Jester]

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.

[Jester]

btw. du willst das nicht wirklich in excel machen, oder?

[Borkert]

@ 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

[Jester]

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.

[Borkert]

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

[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

[Jester]

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...

[Borkert]

@Jester
Danke für den Link.

[Borkert]

Danke für eure Hilfe! Ich habs probiert, mich einzuarbeiten, aber ich habe im Moment leier nicht die erforderlichen Ressourcen.
Sehr schade!
Lg, Borkert