Die ungarische Methode (auch Kuhn-Munkres-Algorithmus) ist ein exakter Algorithmus zur Lösung des Assignment-Problems: n Aufgaben sollen so auf n Bearbeiter verteilt werden, dass jede Aufgabe genau einmal bearbeitet wird und die Gesamtkosten minimal sind. Der Algorithmus stammt von Harold Kuhn (1955) und ist nach Vorarbeiten der ungarischen Mathematiker Dénes Kőnig und Jenő Egerváry benannt; James Munkres (1957) verbesserte die Implementierung auf eine Laufzeit von O(n3), ausgedrückt in der Big-O-Notation.
Ablauf
Ausgangspunkt ist eine quadratische Kostenmatrix. Der Algorithmus arbeitet in vier Schritten:
- Zeilenreduktion: in jeder Zeile das kleinste Element von allen Elementen der Zeile subtrahieren.
- Spaltenreduktion: in jeder Spalte das kleinste Element von allen Elementen der Spalte subtrahieren.
- Minimale Linienüberdeckung: alle Nullen mit möglichst wenigen waagerechten und senkrechten Linien überdecken. Der Satz von Kőnig besagt: die minimale Linienzahl entspricht der maximalen Anzahl unabhängiger Nullen.
- Verbesserung: werden weniger als n Linien benötigt, subtrahiert man das kleinste nicht überdeckte Element von allen nicht überdeckten Elementen und addiert es zu den doppelt überdeckten — dann beginnt Schritt 3 erneut. Werden n Linien benötigt, ist die optimale Zuordnung gefunden.
Eigenschaften
- Der Algorithmus ist exakt: er findet immer die global optimale Zuordnung — keine Heuristik mit ungewisser Güte.
- Die Laufzeit ist polynomial (O(n3)), selbst für große Zuordnungsinstanzen praktikabel.
- Graphentheoretisch entspricht das Assignment-Problem einem perfekten Matching in einem bipartiten Graphen.
- Es ist ein Spezialfall des Transportproblems — alle Angebots- und Nachfragemengen sind 1 — und lässt sich auch als lineare Optimierung modellieren.
Anwendungen: Aufgaben- und Maschinenzuordnung, Personalplanung, Standortwahl, aber auch Datenassoziation etwa bei der Objektverfolgung in der Bildverarbeitung.