Ungarische Methode

Grundidee und Ziel

Die Ungarische Methode, auch Kuhn-Munkres-Algorithmus genannt, ist ein Algorithmus zum Lösen gewichteter Zuordnungsprobleme auf bipartiten Graphen. Ein bipartiter Graph besteht hier aus zwei Gruppen von Knoten, zum Beispiel Quellen und Ziele; zulässige Zuordnungen werden durch Kanten dargestellt, und jede Kante hat ein Gewicht, also einen Preis, Gewinn, Zeitaufwand oder eine Bewertung.

Das Ziel ist, eine eineindeutige Zuordnung mit möglichst vielen Paaren zu finden: Jede Quelle wird höchstens einem Ziel zugeordnet und jedes Ziel höchstens einer Quelle. Je nach Problem soll die Summe der Einzelpreise minimiert oder die Summe der Einzelgewinne maximiert werden. Die Problemklasse kann als Spezialfall der Linearen Optimierung formuliert werden; die Ungarische Methode ist dann eine angepasste primal-duale Lösungsmethode.

Die ursprüngliche Implementierung hatte eine Komplexität von O(n^4). Durch geeignete Datenstrukturen und optimierte Unterroutinen kann sie auf O(n^3) gesenkt werden. Entwickelt wurde die Methode 1955 von Harold W. Kuhn unter Einbeziehung vorheriger Ideen der ungarischen Mathematiker Dénes Kőnig und Jenő Egerváry; James Munkres verbesserte sie 1957 nach einer Laufzeitanalyse.

Problemdarstellung

Das Zuordnungsproblem kann auf zwei gleichwertige Arten dargestellt werden. In der graphentheoretischen Darstellung sind Quellen und Ziele die beiden Knotenmengen eines bipartiten Graphen. Die Kanten stehen für zulässige Zuordnungen, und jede Kante ist mit der Bewertung dieser Zuordnung gewichtet.

In der Matrixdarstellung werden die Daten in einer quadratischen Matrix gesammelt. Jede Zeile entspricht einer Quelle, jede Spalte einem Ziel oder umgekehrt. Jede Matrixkomponente enthält die Bewertung der Zuordnung zwischen der zugehörigen Quelle und dem zugehörigen Ziel. Diese Matrix ist zugleich eine gewichtete Adjazenzmatrix des kantengewichteten bipartiten Graphen. Fehlende Kanten, also unzulässige Zuordnungen, werden durch sehr kleine negative Zahlen oder durch den künstlichen Wert -∞ dargestellt.

Nichtquadratische Fälle und Transversalen

Nicht jedes Ausgangsproblem besitzt von Anfang an quadratische Form. Wenn zum Beispiel n Mitarbeiter k Eignungstests für k zu besetzende Positionen machen und k < n gilt, kann man entweder die graphentheoretische Version der Ungarischen Methode verwenden oder die Matrix künstlich quadratisch machen. Dazu werden n - k Dummy-Positionen eingeführt, also Positionen wie „keine Position“. Dummy-Positionen werden üblicherweise mit der größten vorhandenen Zahl aus der Matrix besetzt.

Wenn eine maximale Zuordnung, also ein maximales Matching, gefunden ist, steht in jeder Zeile und jeder Spalte der Matrix genau ein Element, das zur optimalen Lösung gehört. Eine solche Gruppe von Positionen heißt Transversale der Matrix. Entsprechend kann man das Problem auch so formulieren: Ordne Zeilen- oder Spaltenvektoren so um, dass die Summe der Elemente in der Hauptdiagonale maximal wird.

In einer n×n-Matrix gibt es so viele mögliche Anordnungen wie Permutationen von n Elementen, also n!. Deshalb ist vollständiges Ausprobieren nur bei sehr kleinen Matrizen realistisch. Schon bei einer 10×10-Matrix gibt es 3.628.800 mögliche Permutationen.

Rechenverfahren ohne Formeln

Bei einem Minimierungsproblem beginnt man mit Spalten- und Zeilenreduktionen. Zuerst wird in jeder Spalte das Spaltenminimum bestimmt und von allen Elementen dieser Spalte subtrahiert. Danach werden die neuen Zeilenminima bestimmt und von allen Elementen der jeweiligen Zeile subtrahiert. Aus Symmetriegründen können dabei Zeilen und Spalten auch vertauscht werden.

Anschließend sucht man eine Kombination von Nullen, bei der in jeder Zeile und jeder Spalte genau eine Null ausgewählt ist. Gibt es eine solche Kombination, geben die Positionen dieser Nullen die optimalen Zuordnungen an, und das Verfahren ist beendet. Steht in einer Zeile oder Spalte nur eine einzige Null, gehört sie naheliegenderweise zur Lösungskandidatur.

Wenn keine passende Nullkombination vorhanden ist, werden alle Nullen mit einer minimalen Anzahl horizontaler und vertikaler Linien gestrichen. Sind in einer n×n-Matrix mindestens n Linien nötig, liegt bereits eine optimale Lösung vor. Andernfalls bestimmt man das Minimum der nicht gestrichenen Koeffizienten. Von allen nicht gestrichenen Einträgen wird dieses Minimum subtrahiert, zu allen doppelt gestrichenen Einträgen wird es addiert, und einfach gestrichene Einträge bleiben unverändert. Danach sucht man erneut eine zulässige Kombination von Nullen.

Soll statt eines Minimums ein Maximum gesucht werden, wird zunächst die größte Zahl der Matrix bestimmt. Dann bildet man eine neue Matrix aus den Differenzen zwischen dieser größten Zahl und den alten Matrixelementen. Dadurch wird das Maximierungsproblem in ein Minimierungsproblem überführt.

Formale Methode und maschinelle Lösung

Formal ist eine quadratische Matrix C = (c_ij) der Größe n×n gegeben. Gesucht wird ohne Beschränkung der Allgemeinheit eine Zuordnung j → s_j für j = 1, …, n mit minimaler Gesamtsumme ∑{j=1}^{n} c{s_j,j}, wobei die s_j eine Permutation von {1, …, n} sind. Soll maximiert werden, kann C durch -C ersetzt werden.

Die Methode nutzt die Tatsache, dass bestimmte Änderungen der Matrix die optimale Zuordnung nicht verändern, sondern nur den Optimalwert. Dazu werden Knotenpotentiale beziehungsweise duale Variablen u_1, …, u_n für die Zeilen und v_1, …, v_n für die Spalten verwendet. Die reduzierte Matrix hat Komponenten c̃_{i,j} = c_{ij} - u_i - v_j. Ziel ist, in der reduzierten Matrix möglichst viele Nullen zu erzeugen und daraus die Zuordnung aufzubauen.

Bei der Handrechnung werden zunächst in jeder Zeile und Spalte Minima subtrahiert. Danach kennzeichnet man möglichst viele Nullen mit einem Stern, ohne dass zwei Sterne in derselben Zeile oder Spalte stehen. Wenn n Sterne gesetzt werden können, ist die optimale Zuordnung gefunden. Andernfalls arbeitet man mit Randmarkierungen, gestrichenen Nullen und einem Minimum h der nicht randmarkierten Elemente weiter. Bei jedem vollständigen Durchlauf, der zur erneuten Prüfung zurückführt, wird ein Gegenstand mehr zugeordnet. Wegen der aufwendigen Minimumsuche und Matrixänderungen hat dieses Verfahren die Komplexität O(n^4).

Für die maschinelle Lösung werden Vektoren s und z benutzt, um Sterne und Strich-Markierungen zu speichern. Zusätzlich verwendet man Vektoren u und v für Knotenpotentiale sowie einen Vektor m zur schnelleren Minimumsuche. Dadurch kann die Komplexität auf O(n^3) gesenkt werden.

Beispiele und Hilfsverfahren

Ein anschauliches Beispiel ist das Spielzeugproblem: Vier Kinder, Anna, Berta, Chiara und David, streiten um Eisenbahn, Kaufmannsladen, Puppe und Zoo. Aus den Rangordnungen ihrer Vorlieben wird eine 4×4-Matrix erstellt, wobei 1 die höchste und 4 die geringste Vorliebe bedeutet. Die Ungarische Methode minimiert die „Summe der Tränen“. Die optimale Zuordnung lautet: Anna bekommt den Zoo, Berta die Eisenbahn, Chiara die Puppe, David den Kaufmannsladen. Die minimale Rangsumme beträgt 6; die ideale Rangsumme 4 wäre nur möglich, wenn jedes Kind sein Lieblingsspielzeug bekäme.

Ein weiteres Beispiel ordnet vier Maschinen M_1, M_2, M_3, M_4 vier Aufträgen A_1, A_2, A_3, A_4 zu. Die Matrix enthält Zeitaufwände. Nach den Reduktions- und Anpassungsschritten ergibt sich die optimale Zuordnung (M_1, A_2), (M_2, A_4), (M_3, A_3), (M_4, A_1). Die Gesamtzeit beträgt 5 + 5 + 3 + 2 = 15 und ist das gesuchte Minimum.

Für komplexere Aufgaben kann das händische Finden der n unabhängigen Nullen schwierig werden. Deshalb wird als Hilfsverfahren die Frequenzmethode nach Habr et al. genannt. Sie bewertet jeden Matrixwert nach Abweichungen von Zeilenmittelwert, Spaltenmittelwert und Gesamtmittelwert: y(ij) = x(ij) - μ(x(i.)) - μ(x(.j)) + μ(x(ij)). Die entstehende Matrix Y hat über Zeilen, Spalten und Gesamtmatrix jeweils Mittelwert Null. Je negativer ein Wert y(ij) ist, desto eher gehört er in der Einzelbetrachtung zum Optimum; trotzdem darf pro Zeile und Spalte nur ein Wert gewählt werden, und manchmal müssen auch positive Werte einbezogen werden. Diese Methode ist nicht an quadratische Matrizen gebunden, liefert aber als Hilfsverfahren nicht in derselben Weise die garantierte Vorgehensweise der Ungarischen Methode.